省选备考小结(part 1)

12.27 CTT2020 day1

T1.术树数(count)

$Des:$ 初始有 $m$ 个城，接下来 $q$ 次操作：

​ $1.x\ v$ 将 $x$ 与 $m+1$ 连一条权值为 $v$ 的双向边 $(x\le m,v\le V)$

​ $2.x\ y\ v$ 在 $x$ 与 $y$ 之间连一条权值为 $v$ 的双向边 ($x,y\le m,v\le V$)

​ $3.x\ y$ 询问 $x$ 到 $y$ 的所有路径中，所有路径中权值 $k$ 进制异或和的最小值(可以存在重边)。($x,y\le m$)

​ ($V=k^m,q\le2e5;2\le k;m,V \le 5e7$)

$Sol:$ 高维线性基。

$Sum:$ 看到 $k$ 进制异或和，我就知道此题基本上不可做，甚至连暴力我都不会。

T2.树数术(skill)

$Sol:$ 首先，我们观察数据，我们会发现 $\sum k\le 7e5$ ，那么我们就很容易想到要基于将 $k$ 分开进行计算，事实上，我们的确要把每次询问里的每个 $k$ 都分开处理。这里我们定义一个点 $a_x$ 的后继 $nxt[x]$ 为大于在序列上位于 $x$ 之后的最小位置 $y$ 满足 $lca(a_x,…,a_y)=a_y$ ，而由于这个后继具有划分性质，所以我们可以通过单调队列求出所有的 $nxt[i]$。而当我们将 $k$ 分开之后，我们的问题就转化为：给定一个 $x$ (这里的 $x$ 指该次询问中前面所有区间的 $lca$ )，我们要在当前的 $[l,r]$ 中找到位置最小的 $y$ 满足 $lca(x,a_l,…,a_y)=a_y$ ，这个东西可以通过倍增求得，而当我们求出 $y$ 之后，再用倍增求出 $[y,r]$ 中有多少 $y$ 的后继，这就是当前这个区间的贡献。总复杂度 $O(nlogn)$ 。

$Sum:$ 考场上没想到用倍增进行优化，就整了一个分块，用 $O(n\sqrt n log n)$ 的复杂度写的。

T3.述树术(tree)

$Sol:$ 首先，对于一棵树，若存在两个以上的非根二度点，那么它就是非法的。接下来，我们考虑不存在非根二度点的情况，我们需要先求出所有的叶子节点，这里，我们在全集中剔除一个点来判断这个点是否是叶子节点，若是叶子节点，那么返回值将是 $n-2$ ，反之就是 $n-1$ ，这样，我们就用 $n$ 的询问次数求出了所有的叶子节点，接下来，我们需要做的就是如何判断某一个叶子节点 $a$ 它的父亲，我们将所有非叶节点取出来(同时也不能是非根二度点)均分成两部分 $x,y$，然后判断其父亲在哪个部分，具体的，我们将全部叶子节点剔除 $a$ 加上点集 $x$，询问其虚树大小，若为当前整棵树的大小 $-1$ 那么就说明其父亲节点存在于此部分内，若为整棵树的大小 $-2$ 则说明不在。当我们求出当前所有叶子节点的父亲节点之后，我们就把那些父亲节点取出来作为新的叶子节点求下去，直到求出整棵树的形态。这里一共用了 $n\log n$ 次询问。而现在我们存在的问题就是那些非根二度点，因为我们在求叶子节点的时候把非根二度点已经剔除了，所有我们之前的操作中是屏蔽了非根二度点的情况，而我们在该情况下求出的树的形态事实上应该是把非根二度点缩进边中之后的形态。对于每一个非根二度点，我们来思考如果将它插入到某条被我们缩掉的边里，这里我们直接在求出的树形态的 $dfs$ 序上二分，这里得注意，若一条边里缩了两个非根二度点，即为非法。这一步的询问次数也是 $n\log n$ 。总询问次数大概为 $n\log n$ 。

$Sum:$ 考场上时间实在是来不及了，只想出了如何判断非法和如何求出叶子节点。

1.1 UOJ 元旦赛

A.多线程计算

$Des:$ 给出一个 $nm$ 的网格，每个格子上有一个处理器，对于每一个处理器，其会在 $ [0,1)$ 中独立均匀随机地在某一个时刻亮(并一直保持亮着)，接下来给出 $h$ 组情况，对于每一种情况 $(x,y)$ ，当满足恰好 $x$ 行、$y$ 列处理器亮着，就说明当前状态是节能态(其他位置可以有处理器亮着，但是不能是一行或一列)。对于一个节能态，其每单位时间的贡献为 $fbi$ 。求对于所有情况，贡献的期望和是多少，答案对 $998244353$ 取模。($nm,h\le5e5$)

$Sol:$ 引理：$nm$ 个数随机均匀分布在 $[0,1)$ ，第 $k$ 大的数的期望大小为 $\frac{k}{nm+1}$ 。那么存在 $k$ 个处理器的期望时长为 $f(k)=\frac{1}{ (nm+1) \binom{nm}{k} }$ 。某种证明是 $\int_0^1 x^k(1-x)^{n-k} dx=\frac{1}{ (n+1) \binom{n}{k} }$ 。接下来我们分析这 $h$ 种状态，显然，各个状态相互独立，我们不妨考虑其中一个 $(x,y)$ 。其贡献为 $\sum \binom {n}{i} \binom{m}{j} \binom{i}{x} \binom{j}{y} (-1)^x(-1)^y\binom{nm-mj-ni+ij}{k-mj-ni+ij} f(k)$ 。至于这个东西，我们先考虑先把 $\binom{nm-mj-ni+ij}{k-mj-ni+ij}f(k)$ 这个东西提出了。设 $s=mj+ni-ij$ ，由于我们枚举的是 $k$ ， $k$ 与 $i,j$ 无关，所以我们先考虑将后面这个东西对于所有的 $s$ 的值 $g(s)=\sum \binom {nm-s}{k-s}f(k) $ 。 因为 $g(s)=(nm-s)!\sum \frac{1}{(k-s)!} \frac{f(k)}{(nm-k)!}$ ，这样，$g(s)$ 就能直接用卷积来求。这里的复杂度是 $O(nm\log nm)$ 。剩下的，我们需要将 $x,y$ 分离，$\sum \binom{n}{i}\binom{i}{x}(-1)^x \binom{m}{j}\binom{j}{y}(-1)^y$ 。考虑我们想将 $x$ 维服务于 $y$ 维的卷积，设 $F[i][j]$ 表示 $y=j$ 时，$x=1…i$ 对后一维的贡献 $F[i][j]=\sum \binom{n}{i} \binom{i}{x} (-1)^x cnt[x][j]$ ($cnt[i][j]$ 表示 $(i,j)$ 的数量)。这里我们枚举 $y$ ，然后 $F[i][j]=\binom{n}{i} i! \sum \frac{1}{(i-x)!} \frac{(-1)^xcnt[x][j]}{x!}$ ，这个依然可以卷积求。如此拆分之后，我们就只需要再卷积一次 $G[i][j]=\binom{m}{j}\binom{j}{y}(-1)^y F[i][j]g(s)$ ，像第一维一样进行卷积即可。时间复杂度 $O(nm \log nm)$ 。总时间复杂度 $O(nm \log nm)$ 。

$Sum:$ 元旦在家状态不是很好，当时在考场上连最基本的亮 $k$ 个处理器的期望贡献都不会算，连最基本的暴力都没打出来。这是一道非常优秀的多项式题，首先，本题的结论非常巧妙，通过积分求得一个非常舒适的式子(目前不会如何求解)；其次，本题有一个分离二维卷积的技巧非常值得学习。(某利用 $\Beta$ 函数做的方法暂时不会)

1.5 CTT2020 day2

T1.台阶(stairs)

$Sol:$ 首先是对于排列，然后使其尽可能优秀，这里易得，结果应该是：最小配最大、次小配最大、次大配最小，次小配次次大…以此类推，特别的，对于奇数点数时，我们最后得判断一下。将所有点扔到数轴上，再观察每个区间被取的次数，显然，从最外层的两个区间取 $2$ 次，依次向内为取 $2i$ 次，特别的，在中间可能存在要减 $1$ 的情况，这里我们最后特判一下减 $1$ 即可，在以下的情况中，我们一律取 $2i$ 处理。这时，我们觉得这个 $2$ 非常的烦人，那么，我们先把它除掉。再转换一下就是，左右各个点与中间点取差值。这个东西非常板的直接用主席树维护即可，在此不赘述。时间复杂度 $O(nlogn)$ 。

$Sum:$ 结论基本上是得出来了，但是我拿着这个结论却想歪了，差一步转换，复杂度怎么也优化不下来，不想浪费结论，想写个分块，但是由于 $subtask$ 的存在，以及这个恶心的 $7e5$ 最终是放弃了写分块，并成功在考试结束前 $30mins$ 左右想出正解，反复验证之后，开始码主席树，最后，理所当然的没调出来。

T2.随机游走(random)

$Sol:$

$Sum:$ 完全没有想法…

T3.基础图论练习题(graph)

$Des:$ 一个大小为 $n$ 的竞赛图，每次修改一条边的方向，求图中的极大连通分量的个数，答案为 $\displaystyle \sum_{i=1}^n \sum_{j=1}^{i-1} 2^{(i-2)(i-1)/2+j-1} ans_{ij}$，答案对 $1e9+7$ 取模。($n\le5000$)

$Sol:$ 首先一个关于竞赛图的强结论：将竞赛图按照出度排序之后，一个极大连通分量一定是连续的一块。关于此结论，我们考虑反证：若 $dx \le dy \le dz$ ， $x$ 和 $z$ 一个极大连通分量中，那么这 $3$ 个点到其他点的连边情况完全一致，只用考虑 $3$ 个点之内的情况，因为 $x,z$ 在一个极大连通分量中，那么 $dx=dz$ ，而 $z$ 与 $x,y$ 不在一个极大连通分量中，那么，必然是 $dx-2$ 或 $dx+2$ 与原命题不符。因此，原命题得证。接下来的问题就是，如何求两个极大连通分量的分割点，根据此前的强结论，我们任意归纳出另一个结论：当第$i$ 个点前的出度之和为 $i(i-1)/2$ 时作为一个块的结尾。接下来，我们在数列上操作，每次修改两个点，只影响两点区间之内的值，而我们先对度数求个前缀和，再减去 $i(i-1)/2$ ，统计 $0,-1,1$ 个数的前缀和，每次交换相当于统计 $1/-1$ 个数，减去区间内 $0$ 个数，这全部用前缀和差分即可。时间复杂度 $O(n^2)$ 。

$Sum:$ 考场上看到 $T1$ 只会分块， $T2$ 完全没有思路，看到 $T3$ 的时候就已经焦头烂额了，看到题面给了 $T\le1e4,n\le 5000$ ，我以为每次询问必须 $O(1)$ 来求，或者看到后面那个离谱的统计答案方式，在考虑有没有组合意义帮助我求解，就觉得这是大不可做题，直接弃题了。

1.8 CTT day3

T1.计数鸡(count)

$Des:$ 给一个 $n$ 的排列 $q$ ，以及一个长度为 $n$ 的序列 $h$ ，定义 $n$ 的排列 $p$ 的优美度为 $\displaystyle \sum_{i=1}^n \sum_{j=i+1}^n [p_i \ge p_j]+[p_i+h_i\ge q_j]$ ，求 $n$ 的所有排列 $p$ 中，优美度为偶数的个数，答案对 $998244353$ 取模。($n\le300$)

$Sol:$ 首先，求奇偶个数，大概率要反面求解，或求差值，本题正反几乎无差，所有为求差值。观察 $\displaystyle \sum_{i=1}^n \sum_{j=i+1}^n [p_i \ge p_j]$ ，这就是经典地求逆序对，而关于逆序对的奇偶，应联系到行列式。根据行列式 $A$ 的定义，其值等于 $\sum (-1)^{t(p)} \Pi a_{ip_i}$ ，这里 $p$ 为 $n$ 的排列，$t(p)$ 为排列 $p$ 的逆序对个数。我们只需要将 $a_{ij}$ 巧妙地赋值，让 $(-1)^{t(p)} \Pi a_{ip_i}$ 表示奇偶个数之差，而这个赋值也非常简单，用 $a_{ip_i}$ 表示排列第 $i$ 位为 $p_i$ 时，产生的贡献：$\Pi_{j=i+1}^n (-1)^{[p_i+h_i \ge q_j]}$ 即可。设计出行列式之后，用高斯消元求解即可。时间复杂度 $O(n^3)$ 。

$Sum:$ 这道题设计的非常巧妙，巧妙地把行列式的知识融入到题目中去了，转化后，基本上完全满足行列式的性质。

T2.排列(perotation)

$Des:$ 给定一个 $n$ 的排列 $a_i$ ，定义一次操作为：当 $i \in [2,n-1],a_{i-1}<a_i<a_{i+1}$ 时，将其变换为 $a_{i+1},a_{i-1},a_i$ 。接下来 $q$ 次询问，每次询问交换两个 $a_x$ 和 $a_y$ ，求最小的 $k$ ，使 $a_k…a_n$ 可以由单调上升序列通过若干次操作得到。($n,q\le1e5$)

$Sol:$ 首先是一个强结论：从最小的 $k$ 到 $n$ 间所有的位置 $x$ 以其为开头到 $n$ 的数中排名为奇数。根据这个结论，我们设计分块，先按照左边建立分块，再在各个块内依据值域开值域线段树，每次修改相当于在 $[x,y]$ 区间内的每个块内的线段树上的一个值域进行修改，块外暴力更新重构，至于交换的两个点，我们讨论一下是否变号即可，这里的复杂度就是 $O(n\sqrt n \log \sqrt n)$ 。至于查询，我们暴力从后往前暴力查询每个块内是否有非法的点，若存在，就加入将整个块的标记下放，然后暴力从后往前查询第一个变号的点。这一步的复杂度是 $O(n\sqrt n)$ 的。总时间复杂度 $O(n\sqrt n \log sqrt n)$ ，勉强卡过本题。

$Sum:$ 依靠优秀的 $O(n\sqrt n \log \sqrt n)$ 来卡过本题，正解的再分块摊复杂度 $upper_bound$ 实在是难写。

T3.树特卡克林(tree)

$Des:$ $n$ 个点的有根树森林，对于每一个条重链，其权值为重链上点的异或和，接下来 $2m$ 次操作：$1$. 加边 $(a,b)$，将 $b$ 转到当前树的根，然后连接 $(a,b)$ 。$2$. 删边$(a,b)$ ，在树上删去 $(a,b)$ 。$3$.查询 $k$ ，询问所有的 $N$ 条重链中，权值第 $(k-1) \mod N +1$ 小的权值。($n\le1e5,m\le5e5$)

$Sol:$

$Sum:$

1.10 CTT day4

T1.杏仁(almond)

$Des:$ 给定源点 $S$ 和汇点 $T$ ，定义合法的图为：从 $S$ 点出发可以到达所有点，$S$ 点入读为 $0$ ，$T$ 点的出度为 $0$ ，除 $S,T$ 外，每个点入度出度为 $1$ 。给定 $n$ 个点 $m$ 条边的有向图 $G$ 。接下来 $q$ 次询问，求 $G$ 有多少合法子图含有 $S->u$ 。答案对 $998244353$ 取模。($q\le n\le22,m\le10000$)

$Sol:$ 首先，我们从最近的情况入手，当图是条链的情况，$dp[u][s]$ 表示以 $u$ 为开头经过点集 $s$ 的方案数，这样，我们再设 $f[s]$ 表示经过点集 $s$ 的链情况，这个东西我们可以通过简单的 $dp$ 逐位加点来求出答案，具体的，我们先规定当前 $f[s][i]$ 为过点集 $s$ 的链且起点为 $i$ 的方案数，接下来逐个加点即可，时间复杂度 $O(n^22^n)$ 。至于整张图的合法情况，我们定义 $g[s]$ 表示点集为 $s$ 的合法图数量，设 $F(s),G(s)$ 分别表示其生成指数函数，我们会发现 $G(s)=e^{F(s)}$ ，这里的乘法定义为子集卷积 ，具体的，由于这里我们定义的乘法是子集卷积，那么，我们在将集合幂级数 $F(x)$ 转化形式幂级数时，必须类似于 $FST$ 先进行占位，因为在如此转化后的形式幂级数的卷积才满足我们原始定义的需求，此后，我们只需要求 $F(x)$ 的形式幂级数 $F`(x)$ 的 $EXP$ 即可，这里建议用分治求解，时间复杂度 $O(n^22^n)$。把这个求出来之后，我们考虑如何回复每次的询问，设全集为 $E$，我们利用 $dp[u][s]$ 再乘上 $\displaystyle \sum_{t\in (E-s)} g[t]$ ，这个用预处理一下就好了，如此法，时间复杂度 $(n2^n)$ 。总的时间复杂度为 $O(n^22^n)$ 。

$Sum:$ 目前为止，还是很明白这里的 $\exp$ 到底是怎么回事，不清楚它的定义，以及求法。$upd:2021.1.20$ 通过一段时间的理解之后，大概了解了这里 $exp$ 的含义。 这里简单总结一下集合幂级数的知识：对于一个集合幂级数，我们根据需求定义它的乘法卷积，一般的，当我们定义的为 $or$ 或 $and$ 或 $xor$ 时，这个就是我们常见的 $FMT$， 而 $FMT$ 的实质就是将我们定义的集合幂级数转化为形式幂级数，以保证，我们在集合幂级数下的卷积，在形式幂级数上为单纯的点乘，而一般的卷积直接卷即可，我们这里讨论集合幂级数的 $exp$ 和 $ln$ 在形式幂级数下如何完成。设 $G(x)=e^{F(x)} $根据求导可知： $F_i’=G_i’-\sum G_jF’{i-j}$，$G_i’=F_i’+\sum G_j F’{i-j}$ 。若这里的乘法定义为子集卷积，那么，我们只需要类似于 $FST$ 的，把各个位占位即可。 至于 $or$ 以及 $and$ 的 $FMT$ 的实质以及拓展，在此后的一次总结中给出。

T2.甩锅(dove)

$Des:$ $n$ 个点，每个人可以向其他人连边(可以选择不连，其权值为 $1$)，当他和他连边人距离为 $x$ 时，他自己的权值为 $w_x$ ，一种情况其合法，当且仅当图中不存在环，而一个合法图的权值为所有人权值之积。给定 $w_i$，求所有情况的权值之和。($m\le 20,n=2^m$)

$Sol:$ 显然，这个合法方案，它构成一个根向树森林，由于森林不利于求解，我们给它加一个超级源点 $0$ ，所有点都向 $0$ 连一条边权为 $1$ 的边。这样，我们的原问题就变成了，一张有向图，两点之间边条树为其权值 $w_i$ ，求这样的有向图，以 $0$ 点作为根的根向树有多少个。这样，我们就列出了一个 $nn$ 的行列式，现在我们需要做的事就是求解这个行列式。我们观察一下这个 $nn$ 的行列式，它是循环行列式，而这里的 $n=2^m$ ，刚好可以让我们取满 $w_n$ 的所有单位根。其结果就等于 $\Pi f(x)=\sum w_i x^i$ ，这里的 $x$ 取遍 $w_n$ 的所有单位根。时间复杂度 $O(n\log n)$ 。

$Sum:$ 这道题是真的巧妙，精巧地用到了矩阵树定理，同时，本题还用到很多很好的行列式知识：范德梅德行列式，循环行列式。以及，学习了循环行列式的求法：求其对应的单位根之积。

T3.同构判定鸡(graph)

$Des:$ $n$ 个点，求尽可能多的边 ($\ge m$)，其子图不存在 $K(3,3)$ 。($n=7^3,m=2350$)

$Sol:$

$Sum:$

1.13 THU 2016 day1

T1.玩游戏 (game)

$Des:$ 在森林里进行博弈，每次选择一个点，将其所有祖先删去，不能操作者判输，询问先手是否必胜。($n\le 1e5$)

$Sol:$ 根据博弈论那一套理论，本题的结论为：设 $mex$ 函数，一个状态的 $mex$ 函数，为其所有后继状态未出现的最小值，而一个后继状态的值，为其所有子状态的异或和。这里的后继状态为在子树中选一个点，将其连祖先全部删去，子状态为删去后剩下的其他子树。这里，我们考虑一个线段树合并的写法，首先，我们一定是要维护当前的后继状态出现了哪些值，而我们在考虑 $u$ 子树时，可以考虑从其子节点 $v$ 继承过来，这里就需要用到线段树合并了。现在我们唯一的问题就在于我们将儿子往父亲继承的时候，我们得异或一个值，而异或就破坏了线段树的状态，一个可行的做法是挂懒标记，时间复杂度 $O(n\log n)$。不过，这个算法比较难写，这里推荐用启发式合并，然后挂它现在应该异或哪个值。时间复杂度 $O(n\log n)$ 。

$Sum:$ 关于博弈论那一套 $mex$ 和异或的理论完全不会，一般如果不是我擅长的对抗博弈，我基本都是直接弃掉。这里简单总结一下 $mex$ 那套理论：设 $mex$ 函数，一个状态的 $mex$ 函数，为其所有后继状态未出现的最小值，而一个后继状态的值，为其所有子状态的异或和。

T2.魔法小程序 (magic)

$Des:$ 给出长度为 $n$ 特殊进制每一位的进制 $a_i$ ，长度为 $m$ 的 $c_i$ 是 $b_i$ 的特殊进制高维前缀和，已知 $c_i$ ，求 $b_i$。($n\le 1e4,m\le 1e6$)

$Sol:$ 高维前缀和的模板题。

$Sum:$ 考场上很容易就看出来它是高维前缀和了，但是，我明明可以不被卡空间，却认为自己递归的写法一定会被卡空间，所有就写烂了。由于最近很多关于 $FMT\& FWT$ 的知识，这里对 $or$ 或 $and$ 卷积的 $FMT$ 的实质进行总结：由于我们对集合幂级数转形式幂级数定义为 $f`(S)=\sum_{T\subseteq S} f(T)$ (对于 $and$ 的情况，就搞好相反)。而对于二维的情况，它的本质就是高维前缀和($and$ 为高维后缀和) ，特别的，我们对这个扩展到 $k$ 维的情况，其本质没有改变，我们依然可以通过类 $FMT$ 来求得高维前缀和，其反操作也类似，而本题只考察了其反操作。至于 $xor$ 的 $FWT$ 实质，我会在此后的某一次总结中给出。

T3.数据交互 (tree)

$Des:$ $n$ 个点的树，接下来 $m$ 次操作，每次操作为：$1.$ 在 $x$ 和 $y$ 的路径上挂一个权值为 $z$ 的连线。$2.$ 撤销第 $x$ 次连边。每次操作后，询问当前我们选两个点，删去其路径上所有点后，被阻断的连边的权值之和的最大值。($n,m\le 1e5$)

$Sol:$

$Sum:$

THU 2016 day4

T1.组合数问题 (problem)

$Des:$ 给定 $n,m,k$ ，求在有多少的 $i\le n,j\le m$ 满足 $\binom {i}{j} \equiv 0 (\mod k)$ ，答案对 $998244353$ 取模。($n,m\le 1e18,k\le100$ 且 $k\in prime$ )

$Sol:$ 首先，我们根据 $Lucas$ 定理：$\binom {i}{j} \equiv \binom {\lfloor \frac{i}{k}\rfloor}{\lfloor \frac{j}{k}\rfloor}\binom{i\mod k}{j\mod k} (\mod k)$ 。根据这个，我们发现，当 $\binom{i}{j}\equiv 0 (\mod k)$ 时，一定是在 $Lucas$ 定理递归到某一次时，上指标小于下指标。而在 $k$ 进制下，这个就是 $k$ 进制下 $j$ 的某一位比 $i$ 大。本题求合法的方案，而事实上，不合法的方案远比合法方案好求多了，而这里指的不合法方案指 $i$ 在 $k$ 进制下每一位都不比 $j$ 小。转化完后的结果就可以用数位 $dp$ 来求。这里推荐使用记忆化搜索，设 $f[p][0/1][0/1]$ 表示处理到第 $p$ 位，上指标是否有一位顶位，下指标是否有一位顶位。时间复杂度 $O(\log^3n)$ 。

$Sum:$ 考场上没有想到 $Lucas$ 定理，但是自己通过一些简单的数论知识推导出了相同的判定条件，但是当时没有想到要用 $k$ 进制数位 $dp$ 来求解，一直在想也没用办法对判定条件进行容斥。这里再简单总结一下使用数位 $dp$ 的情况，一般，当题目给出了几个值域范围(个数一般不会太多)，我们需要求所有落在这些值域范围的所有答案时，可能可以使用数位 $dp$；特别的，当题目的限制条件充分落在各个数位上的时候(这个时候就不能局限于常见的十进制了，可能需要向二进制或者 $k$ 进制扩展)，也可能可以使用数位 $dp$。这里补充一句，一般数位 $dp$ 写起来很折磨，有时可以改为记忆化搜索来降低代码难度。

T2.汽水 (soda)

$Des:$ 给定一个大小为 $n$ 的树，树边有边权，给定一个值 $K$ ，求一条路径，其路径权值平均值向下取整最接近 $K$ ，求这个值。($n\le 5e4,K\le 1e13$)

$Sol:$ 首先，我们考虑来二分这个答案 $cur$，至于 $check$ ，对于我们精准地检查某个值是否存在显然是不对的，而且这样也不具有二分性质了，这里我们相当于检查平均值在一个区间 $[K-cur,K+cur]$ 的路径是否存在，对于直接验证，我们不太好求，当然，这里也可以用 $KDT$ 硬求，但是，我们转化一下，我们求这个区间的值出现了多少次，而这个东西，我们可以用平均值小于等于 $K+cur$ 的减去小于 $K-cur$ 的。接下来，我们需要实现的是，求有多少条路径的平均值小于等于 $w$ ，我们先将所有的边减去 $w$ ，然后，统计有多少条路径之和小于等于 $0$ 。这个东西用 $des\ on\ tree$ 或点分树来求都行，时间复杂度 $O(n\log^2n)$ ~ $O(n\log^3n)$ 。

$Sum:$ 挺可做的一道题，就是很卡常，若用题解的 $O(n \log^3 n)$ 算法非常卡常，或者，可以使用 $des\ on\ tree$ 来做的话，复杂度是 $O(n\log^2n)$ 的。

T4.定向越野 (circle)

$Des:$ 一个平面，给定起点终点，路上有 $n$ 个圆，求最短路。($n\le500$)

$Sol:$

$Sum:$ 大计算几何题，看看就不想写。

THU 2016 day3

T1.石家庄的工人阶级比较坚强 (stein)

$Des:$ $3^m$ 个人玩 $K$ 轮石头剪刀布，每轮进行 $m$ 次，第 $i$ 个人他在一轮中的 $m$ 次中游戏中，他所出的恒定，即他出的是他编号的三进制数，具体的，$0$ 为剪刀，$1$ 为石头，$2$ 为布。我们定义 $b_{uv}$ 表示 $i$ 比 $j$ 赢 $u$ 次，输 $v$ 次的权值，给定 $f_{0i}$ ，之后的每轮的 $f_i(x)=\sum f_{i-1}(y)\ b_{uv}$ 。求最后的结果，答案对 $998244353$ 取模。($m\le 12$)

$Sol:$ 首先，我们观察石头剪刀布的游戏规则，我们会发现，其胜负平局的判断恰好为三进制不退位减(其逆操作为三进制不进位加)，接下来再来观察 $b$ 这个矩阵，由于这个矩阵的大小为 $3^m$ ，是我们完全无法接受的矩阵大小，可以推测，其必然不会直接考察原矩阵，也就是说，本题肯定不会是直接使用矩阵。而一个可观的想法就是将其转化为多项式卷积，而事实上，我们确实可以做到。我们用三进制不进位加和三进制不进位减重新定义 $b_{uv}$ ：$b_{bit1(x- y)\ bit2(x - y)}$ ，我们定义 $B_i=b_{bit1(i)\ bit2(i)}$ ，那么原式变为 $\displaystyle f_i(x)=\sum_{y+z=x} f_{i-1}(y)B(z)$ ，这样，我们就相当于把矩阵乘，压成了三进制卷积乘。而至于三进制卷积乘，我们效仿二进制 $FWT$ 来做。具体的，我们定义三进制 $FWT$ 的矩阵单位根矩阵 ${w^{ij}}$ ，其单位根为 $w_3^0,w_3^1,w_3^2$ ，而由于我们不好求非质数的单位根，其实依然可以用扩展 $BSGS$ 来求，所以最好扩域来求(定义 $\sqrt {-3}$ 为 $i$)。然后再做 $FWT$ 即可，其逆变化 $IFWT$ 的矩阵也就是 $\frac{1}{3^m} {w^{-ij}}$ 。时间复杂度 $O(m3^m)$ 。

$Sum:$ 本题考查了对三进制 $FWT$ 的掌握，这里简单的对沃尔什变换的 $FWT$ 进行总结。首先，是最基础的二进制 $xor$ 的 $FWT$ ，因为我们知道 $xor$ 的实质是二进制不进位加法，其定义为：$\displaystyle F(i)=\sum_{i\bigotimes j=1}f(j)-\sum_{i\bigotimes j=0}f(j)$ 这里的 $\bigotimes$ 定义为 $popcount(x\&y) \mod 2$ ，其性质为 $(i\bigotimes j)xor(i\bigotimes k)=i\bigotimes(j\ xor\ k)$ 。其矩阵为单位根 $w_2^0$ 的范德蒙德矩阵。推广至 $k$ 进制情况下，其矩阵为 $w_k^0$ 的范德梅德矩阵。

T2.你的生命已如风中残烛 (card)

$Des:$ $n$ 个数 $a_i$，和为 $m$ ，要求求出有多少个长度为 $m$ 序列，其中恰好有 $a_i$ ，且容易 $i$ 的前缀和大于等于 $i$ 。答案对 $998244353$ 取模。($n\le 40,a_i\le 1e5$)

$Sol:$ 首先转换题意：将 $a_i-1$ ，然后排在一个长度为 $m$ 的序列中，序列中其他位置为 $-1$ ，定义合法序列为，任意位置前缀和大于等于0，求合法方案数。我们从合法方案的形式入手进行分析，我们把序列变成一个环，企图通过环来进行统计答案，由于题目性质，任意一个环上必有一个地方断开可以形成合法序列。可是事实上，我们可以从环上若干个点断开能形成一个合法方案，这就导致我们不能直接从朴素的环入手。我们考虑如何区分一个环上不同点断开的合法方案，由于直接进行分析会被不同环状态的特性所阻挡，所以我们考虑改变这个环。具体的，我们在序列末尾再添加一个 $-1$ ，由此构造出来的任意环，依然必定存在且仅存在一组解：由于前缀和一定大于等于0(除最后一个点)，那么后缀和一定小于等于 $-1$ ，由此，任意其他位置为起点的序列，到我们现在钦定的这个答案点的前缀和必然小于0，所以仅存在一种合法方案。那么，合法答案就是 $\frac{m!}{m-n+1}$ 。时间复杂度 $O(m)$ 。

$Sum:$ 出题人的写法被更优秀的写法吊起来打了。

T3.温暖会指引我们前行 (move)

$Des:$ 给出 $n$ 个点，接下来 $m$ 次操作：1.加入一条连接 $(u,v)$ ，长度为 $len$ ，权值为 $w$ 的边。2.询问 $(u,v)$ 的所有路径中，权值升序排序后字典序最小的路径的长度和。3.修改某条边的长度。($n\le1e5,m\le3e5$)

$Sol:$ 模板的 $LCT$ ，我们以 $w$ 维护最小生成树，然后再维护链的 $len$ 和。时间复杂度 $O(m\log n)$ 。

$Sum:$ 对 $LCT$ 掌握不太熟练，考场上就是知道要用 $LCT$ ，也不敢轻易去写，使用其他数据结构拿了 $70pts$ 。

PKU 2018 day1

T1.多边形上天 (polygon)

$Des:$ 给出一个多边形，其在空中水平速度 $v$ ，角速度 $w$ ，求第一个落地点横坐标。($n\le2000,v,w\le1000,x,y\le 1e5$)

$Sol:$

$Sum:$

T2.esperar (esperar)

$Des:$ 给出 $n$ 个数 $a_i$ ，$b_i$ 是 $a_i$ 的因子，$c_i$ 是 $b_i$ 的因子，求 $\Pi c_i^2 \ge \Pi b_i$，答案对 $998244353$ 取模 。($n\le 100,a_i\le 1e9$)

$Sol: $ 观察 $\Pi c_i^2\ge \Pi b_i$ ，因为 $c_i$ 是 $b_i$ 的因子，我们定义 $c_i*d_i=b_i$ ，若 $\Pi c_i^2\ge \Pi b_i$ ，那么 $\Pi d_i^2\le \Pi b_i$ 。这样，我们就巧妙地将题目简化了很多，因为，我们免去了麻烦大小判断，同时还将两种极端情况一一对应了，而这一步对应后，我们求严格大于的情况，就只用求 $\Pi$ ($a_i$ 因子的因子个数)。剩下需要做的就是找到那些取等的情况即可，而这个取等情况也可以根据拆质因数 $dp$ 来做。总的复杂度大概为 $O(n^2log^2a)$ 。

$Sum:$ 考场上把题面要求的都求了，所以改起来特别快，当然，这也说明了我离正解其实已经差不多了，唯一缺乏就是那一步关键的转换，不过，事实上，这道题考查的也就是这一步关键的转换，这也反映出我思考得不够深入，观察力不够敏锐，没有从根本去思考问题，而这题的根本就在于这个大于等于的判定。这一步转换是至关重要，因为朴素的情况下，我们不可能对那么大的数进行对比，唯一可行的方案就是取对，但是，在这种数论类题面里，出现小数就几乎等价于想歪了。

T3.芒果冰加了空气 (mango)

$Des:$ 给出一个大小为 $n$ 的树，对其点分治(乱)，求不同的点分治方案，答案对 $1e9+7$ 取模。($n\le 5000$)

$Sol:$ 我们先考虑在点分树上合并原树中一条边 $(u,v)$， 其相当于取 $(u,v)$ 两个点所分割开的两个点集分别染色，然后在原点分树上按颜色向上连父亲边，可以发现这次操作之后，我们不会改变点分树的偏序关系。那么，我们正向思考题面所要求的断边操作，将两个原树上的点 $(u,v)$ 断掉相当于要把那两个点所在的点分树合并，由于逆向连边操作的情况，我们在合并过程中只关心 $(u,v)$ 所在的两个点集中相互之间的偏序关系，那么，我就可以将 $(u,v)$ 两点到点分树根之间的点任意顺序归并(不改变两个点集的偏序关系)。简单证明，由于我们断边后的情况被保证合法，那么我们现在合并出来的所有点分树一定全部合法。这样，我们对于树上一棵子树构成的点分树就只关心原子树上的根在点分树上的深度。设 $f[i][j]$ 表示在 $i$ 的子树构成的点分树中 $i$ 的深度为 $j$ 的方案数，那么，$\displaystyle f[u][i]=\sum_{j=1}^i\sum_{k=i-j}^n f[u][j]f[v][k]\binom{i-1}{j-1}$。预处理后缀和，然后 $dp$ 即可。时间复杂度 $O(n^2)$ 。

$Sum:$ 这道题真的是道好题，它划分方式是真的巧妙，目前还没有完全理解，日后补充，值得深究。这里简单总结一下本题的思考过程：逆向考虑连边对点分树拆分的影响，正向思考割边对点分树合并的影响(递归归纳这个影响)，总结点分树合并时所关心的量，设计 $dp$ 。

PKU 2018 day2

T1.宝石游戏 (gem)

$Des:$ 大小为 $n$ 的树，根节点为 $1$，节点有权值，接下来 $m$ 次操作：1.将城镇 $x$ 的权值修改为 $y$ 。2.询问 $x$ 下方深度 $y$ 以内所有深度相同的点的权值和的异或和。($n,m\le 1e5$)

$Sol:$ 首先，我们考虑没有修改的情况，我们使用长剖维护 $f[u][k]$ 表示当前 $u$ 子树内距离 $u$ 为 $k$ 的节点之后的后缀异或和，每当我们在长剖 $dp$ 时求出一个点 $u$ 的答案的时候，我们把挂在它上面的询问全部求出来即可，时间复杂度 $O(n)$。对于存在修改的情况，我们把操作分块，每到一块就把其前一块的修改全部更新，然后开始重构我们的长剖求的 $dp$ ，而当我们求 $u$ 的值的时候，就来处理挂在它身上的询问，在处理的时候，我们暂时把会把这个块内该询问前的修改的贡献算出来，并贡献入答案即可。时间复杂度 $O(n\sqrt n)$ 。

$Sum:$ 考场上依稀记得蒋队长去年省选的时候讲过对操作分块重构的写法，我看到这道题数据范围以及询问方式的时候其实是想到了要用那个方法的，但是，由于对线段树合并不熟悉，以及对长剖的理解出了问题，导致我完全没有想出优于暴力的写法。这里简单总结一下操作分块重构以及长剖：1.当我们的操作序列只存在修改和查询且每次修改可以在查询的时候在基于上一次修改进行 $O(1)$ ~ $O(\log n)$ 更新贡献的时候，我们就可以将操作序列分块，每过一个块才把之前的修改全部更新到我们手中维护的东西上，即重构手中维护的东西（对于重构的复杂度最好也在 $O(n)$ ~ $O(n\log n)$ ，且能一次性把所有修改都更新），对于查询，我们只用基于上次重构，在查询的时候把之前的修改的贡献算上即可。2.对于长剖，我们用长剖优化 $dp$ 的时候，只维护了当前的点的深度数组的正确性，对于之前求出的值，必须及时统计入答案。

T2.面国建设 (contribution)

$Des:$ 给出 $S,C$ ，有多少对 $(A,B)$ 满足 $A\le S,B\le C$ 使一个平面内能有若干个矩阵其面积和为 $A$ ，周长和为 $B$ 。($S\le2e5,C\le4e5$)

$Sol:$

$Sum：$

T3.Wechat (wechat)

$Des:$ 求第 $n$ 列的欧拉数的 $\frac{1}{n!}$ ，答案对 $998244353$ 取模。($n\le 1e5$)

$Sol:$ 方法一：$ \displaystyle \left< n \atop k \right>=\sum_{i=0}^k \binom{n+1}{i} (k+1-i)^n(-1)^i $ ，把这个式子拆成卷积使做卷积即可，挺简单的，这里不赘述。

方法二：我们设 $f(k)$ 表示至少 $k$ 个上升的个数，根据组合意义，它等于 $\displaystyle x^n^{n-k-1}$ （考虑拆分成若干非降的段，其等价于整数拆分的排列），设 $m=n-k-1$，把它拆开可得：$\displaystyle [x^n]\sum_{i=0}^m \binom{m}{i}(-1)^{m-i} \frac{i^n}{n!} $ 后面这个东西又可以用卷积来求，这里不赘述。随后，我们再设 $g(k)$ 为我们要求的值，我们会发现 $\displaystyle f(x)=\sum_{i=x}^n \binom{i}{x} g(i)$ ，可得 $\displaystyle g(x)=\sum_{i=x}^n \binom{i}{x} (-1)^{i-x} f(i) $ 。这个依然可以用卷积来求。两种方法的时间复杂度都是 $O(n\log n)$ ，但是由于方法二要卷积两次，所以常数会很大。

$Sum:$ 考场上完全忘记了自己曾经在一年写过这道题，只能说当时没有完全理解就水掉了，现在看来，我当时差点就水掉了一道好题，能有机会重新把这道题捡回来也挺好的，而且还学会了新的写法。这里对欧拉函数进行简单的总结：$ \displaystyle \left< n \atop k \right>=\sum_{i=0}^k \binom{n+1}{i} (k+1-i)^n(-1)^i $ 关于这个式子的理解待补充。$\displaystyle x^n=\sum_{k=0}^n \binom {x+k}{n}\left< n \atop k \right> $ 这个式子它将欧拉数与整次幂联系起来了。$ \displaystyle \left< n \atop m \right>=\sum_{k=0}^n k! \begin{Bmatrix} n \ k \ \end{Bmatrix} \binom{n-k}{m}(-1)^{n-k-m} $ 这个式子与式子 $1$ 等价，理解待补充。以上证明依靠归纳皆可。

THU 2016 day2

T1.优雅求和 (sum)

$Des:$ 给定 $n,m,x$ 以及长度为 $m$ 的 $f(x)$ 的点值，求 $\displaystyle \sum_{k=0}^nf(k)\binom{n}{k}x^k(1-x)^{n-k} $ 。($ n\le1e9,m\le 2e4 $)

$Sol:$ 首先，观察 $n$ 和 $m$ 的大小，发现 $n$ 非常大但是 $m$ 却非常小，因此，我们大概会基于 $m$ 来思考，而这种在求值中把组合数和多项式直接扔到 $\sum$ 里的，大概率要把 $f(x)$ 拆成下降幂再扔回去(类似于 $[$ 联合省选 $2020]\ d1t2$ 组合数问题 ) 。这里简单推导一下：设 $\displaystyle f(x)=\sum_{i=0}^m a_i x^{\underline {i}} $ ，那么原式子变为 $ \displaystyle \sum_{k=0}^n \sum_{i=0}^m a_i\frac{k!}{(k-i)!}\binom{n}{k}x^k(1-x)^{n-k}=\sum_{i=0}^ma_ii!\sum_{k=0}^n \binom{k}{i} \binom{n}{k} x^k(1-x)^{n-k} $ 。考虑三项式定理：$ \displaystyle \sum_{i=0}^m \binom{n}{i} a_i i! \sum_{k=0}^n \binom{n-i}{k-i} x^k(1-x)^{n-k} $ 。把 $x$ 提一部分出来，更换 $k$ 可得：$ \displaystyle \sum_{i=0}^m \binom{n}{i} a_i i! x^i $ 。这个式子极其优美，而我们剩下来该做的事就是求这个下降幂系数。这里给出结论：下降幂系数的 $OGF$ 卷上 $e$ 等于点值的 $EGF$ ，而点值的 $EGF$ 卷上 $e^{-1}$ 等于下降幂系数的 $OGF$ 。那么，我们只需要将题目给出的点值卷上 $e$ 即可得到下降幂系数，然后再求值即可。时间复杂度 $O(m\log m)$ 。

$Sum:$ 考前观星，把这道题直接给做了。这里简单总结一下关于下降幂 $OGF$ 与点值 $EGF$ 的关系：设下降幂多项式 $F(x)$ ，设其点值的 $\displaystyle EGF:F#=\sum_{i=0}^\infty \frac{F(i)}{i!}x^i$ 。 再设 $x^{\underline n}$ 点值的 $EGF$ ： $ \displaystyle \sum_{i=0}^{\infty}\frac{i^{\underline{n}}}{i!}x^i=\sum_{i=0}^{\infty}\frac{1}{(i-n)!}x^i=x^n\sum_{i=0}^\infty \frac{1}{i!}x^i=x^n e^x $ ，那么，$ \displaystyle F#=\sum_{i=0}^\infty \frac{1}{i!}x^i \sum_{j=0}^\infty a_j i^{\underline j}=\sum_{j=0}^\infty a_j \sum_{i=0}^\infty \frac{1}{i!} x^i i^{\underline j}=\sum_{j=0}^\infty a_j x^j e^x$ 。可证明我们的结论：下降幂系数的 $OGF$ 卷上 $e$ 等于点值的 $EGF$ ，而点值的 $EGF$ 卷上 $e^{-1}$ 等于下降幂系数的 $OGF$ 。

T2.工厂 (factory)

$Des:$ 给出两种特殊的处理器：1.接受字符串第一个字符 $x$，并以此字符进入 $trans[x]$ ，若无字符进入 $nxt$ ；2.在字符串末尾添加一个字符 $x$ ，并进入 $nxt$ 。我们要以这两个处理器构建自动机，完成对一系列字符串的接受与拒绝。（本题实在不好描述）

$Sol:$

$Sum:$

T3.连通子树 (connected)

$Des:$ 给出一个大小为 $n$ 的树，每个点有一个颜色，最多有 $ 5 $ 个点颜色相同。接下来 $m$ 次询问，每次询问为求出颜色为 $a,b,c$ 的个数为 $n_a,n_b,n_c$ 的联通子图个数。答案对 $1e9+7$ 取模。($n,m\le 1e5$)

$Sol:$

$Sum:$

1.26 WC2015

T1.k小割

$Des:$

$Sol:$

$Sum:$

T2.混淆与破译

T3.未来程序

1.28 WC2016考前欢乐赛

T1.string

$Sum:$ 对于这道题，我真的是一言难尽，我用最正确的思路拿了最低的分。

T2.graph

$Des:$ $n$ 个点 $m$ 条边的有向图，设其邻接矩阵为 $A$ ，显然，这个矩阵必然存在周期，我们设周期为 $d$ ，设 $A^k=A^{k+d}$ ， $k$ 为满足条件的最小值，接下来两种询问：若 $tp=1$ 时，询问 $d,k$ ；若 $tp=0$ 时，询问 $d$ ，答案对 $1e9+7$。($tp=1$ 时 $n\le 200,m\le 3000$；$tp=0$ 时 $n\le 1e5,m\le 2e5$)

$Sol:$ 首先，我们归纳得出结论：周期的大小为各个强连通分量的周期的 $lcm$ ，而一个强连通分量的周期为其所有环的 $gcd$ 。然后我们就可以通过莫比乌斯反演来求 $lcm$ 。至于 $tp=1$ 的情况，我们知道 $k$ 具有单调性，因为更大的 $k$ 一定在环里面，即乘上 $A^d$ 后复原，所以，我们二分求这个值，细节挺多的。（由于本人此时并未成功过掉此题，这里不展开讲。）

T3.shortpath

$Des:$ $n$ 个点 $m$ 条边的无向图，边权为 $2^x$，求 $s$ 到 $t$ 的最短路。($n,x\le 1e5,m\le2e5$)

$Sol:$ 线段树维护权值加， $hash$ 找第一个不同位置。

$Sum:$ 没什么想法还把 $dj$ 写挂了。

1.29 WC模拟

T1.雪中送温暖(warm)

$Des:$ $K$ 维空间中每个整点有一个信号灯，我们规定 $K$ 维数字全部都为 $1$ 的信号灯为红色；存在一维数字为 $0$ 的信号灯为绿色；对于其他的信号灯，定义它的 $K$ 个前驱为恰好有一维比其小 $1$ 的信号灯，其颜色由所有前驱中的红灯个数 $x$ 决定，若 $x$ 为偶数，则为绿色，反之为红色。接下来给出一个 $K$ 维矩阵 ${l_x},{r_x}$ ，求其中红灯个数，答案对 $998244353$ 取模。$(K\le 9,l_x,r_x\le1e18)$

$Sol:$ 首先，我们从 $2$ 维平面的情况开始思考，考虑他这个贡献方式：由前驱贡献，而前驱又相当于从起点到它的路径上最后结过的两个点，以此，我们可以认为，他的贡献就是路径条数的奇偶性，为了方便使用组合数，我们将横纵坐标减 $1$ 。而对于组合数的奇偶，我们用 $lucas$ 定理可知，$\binom{x+y}{x}=x\&y (\mod 2)$ 。扩展到 $k$ 维空间，$\frac{(\sum x_i)！}{\Pi x_i!}$ ，其为奇数的情况相当于所有的 $x_i \& x_j$ 都是 $0$ ，对于一个位置他是红灯的情况，当且仅当它的每一维在二进制下的每一位只有至多一维是 $1$。这样，对于前缀和的情况，我们只需要数位 $dp$ 表示二进制下第 $p$ 位的 $K$ 维中哪一维选 $1$ (可以存在全零)，当我们可以求出任意点的高维前缀和的时候，我们接下来就只需要进行容斥了，容斥系数 $(-1)^{cnt(l_i)}$ ，这里的 $cnt(l_i)$ 表示存在多少个 $l_i-1$ 。时间复杂度 $O(2^{2K}\log r_i)$ 。

$Sum:$ 考场上花了好久来找判断条件，我入手就从二进制以及位运算开始，还考虑过是否要减 $1$ ，同时，正解那种各个相互求 $\&$ 的判断方式我也考虑过，但是就是没有总结出正解的判定方式，明明已经非常接近正确了，却没有找出来。同时，这也说明了，一味的找规律对于解题是无意的，只有结合题意，合理推理，理智猜测，再小心验证才是正确的解题之道，盲目的找规律只是对题目的亵渎。

T2.水题嘉年华(water)

$Des:$ $2n$ 个人进行匹配，其中有部分已经匹配，而匹配的要求为在一个平面图里不存在匹配线相交，询问是否可能。($n\le50$)

$Sol:$

$Sum:$

T3.最假女选手(wyywyy)

$Des:$ 长度为 $n$ 的序列，进行 $m$ 次操作：$1.$ 区间 $[l,r]$ 加 $x$ 。$2.$ 区间 $[l,r]$ 小于 $x$ 的数变成 $x$ 。$3.$ 区间 $[l,r]$ 大于 $x$ 的数变成 $x$ 。$4.$ 询问区间 $[l,r]$ 的和。$5.$ 询问区间 $[l,r]$ 的最大值。$6.$ 询问区间 $[l,r]$ 的最小值。($n,m\le5e5$)

$Sol:$ 本题是个吉老师线段树的板子，这里简单讲解一下其做法： 操作 $2$ 与操作 $3$ 几乎等价，这里只以操作 $2$ 为例。对于操作 $2$ ，我们想将一个区间小于 $x$ 的数变成 $x$ ，这个时候我们维护区间最小值 $min$ 以及其数量 $t$ 和严格次小值 $sn$：考虑我们维护这些值的收益，我们每次在修改的时候，$1.$ 若 $x<min$ ，不处理；$2.$ 若 $min<x<sn$ ，只将 $min$ 修改为 $x$ ，同时修改 $sum$ ；$3.$ 若 $sn<x$ ，递归其左右子求解。可以证明以上一次操作的均摊复杂度是 $\log^2n$ 。而这里我们只需要同时维护最小值以及其数量和严格次小值、最大值以及其数量和严格次大值、区间和，由于这里存在一个加法操作，我们还需要维护一个懒标记，可以发现，只要我们把懒标记打好，对最大值最小值是没有影响的。这里需要注意的是，在第二种情况中修改 $min/max$ 的时候，若 $max/min$ 或 $sn/sx$ 与其相同，得同时修改。 时间复杂度 $O(n\log^2n)$ 。

$Sum:$ 之前见过这道题，知道这是吉老师线段树的板子，但是由于不熟悉(只给自己留了 $1h$ 来写)，在考场上啥都没写出来。下来之后订正的时候，也被吉老师线段树折磨了：当 我们修改最大值的时候，若最大值与最小值一样或最大值和次小值一样，我们需要一并修改，同理，修改最小值的时候亦然。同时，由于本题过于痛苦的线段树，我决定修改自己的线段树写法。这里简单总结一下吉老师线段树：其 $min/max$ 在线段树的操作中相当于一个标记，而一个点的值其实等于它自己本身的值与往父亲走的路径上第一个遇到的 $min/max$ 标记取 $max/min$ ，而往左右子递归的过程相当于回收其路径上失效的标记，这样就能保证其答案的正确性(只要标记回收的合理，就保证了答案的正确)。

1.30 WC模拟

T1.string

$Sol:$

$Sum:$

T2.fountain

$Des:$ 给出 $n$ 个物品，我们要将其放置一条长度为 $S$ 的线段上，而每个物品有一个 $r_i$ 表示其最近的相邻物品与其距离不能低于 $r_i$ ，求合法的方案数，答案对 $1e9+7$ 取模。($n,r_i\le 40,S\le 1e5$)

$Sol:$ 首先根据 $d=\sum \max(p_i,p_{i+1})$ ， $\binom{S-d+n-1}{n}$ 可以求得答案，接下来，我们就会发现，现在我们只关心每个 $d$ 出现了多少次，我们先将 $a_i$ 排序，这样就保证了在我们后面加点的时候一定取后一个数的 $r_i$，设 $dp[i][j][k]$ 表示用到第 $i$ 个数，还剩 $j$ 个空区间，当前的 $d=k$ 的方案数，按照定义来转移即可。时间复杂度 $O(n^4)$ 。

$Sum:$ 考场上只知道 $d=\sum \max(p_i,p_{i+1})$ ，用 $\binom{S-d+n-1}{n}$ 求答案。考场上没有把那个 $dp$ 式子想明白，不知道怎么消除两个点产生空区间的情况，我知道现在只关心其 $d$ 值，也就相当于只关心其相对取值，不应该关心原本的 $S$ 线段，但是考场上想的时候一直没把这两者的关系弄明白，对于 $d$ 的处理拖泥带水不干净利落，导致最终没有构造出 $dp$ 。

t3.picture

$Des:$ 给出 $n$ 个数的一个排列 ${a_i}$ ，定义图形 $A$ 为 $i1<i2<i3<i4\&a_{i1}<a_{i3}<a_{i2}<a_{i4}$ ，图形 $B$ 为 $i1<i2<i3<i4\&a_{i1}<a_{i2}<a_{i4}<a_{i3}$，图形 $C$ 为 $i1<i2<i3<i4\&a_{i1}<a_{i4}<a_{i3}<a_{i2}$ ，设 $cnt(X)$ 为图形 $X$ 在排列中的个数，求 $cnt(A)-cnt(B)-cnt(C)$ ，答案对 $16777216$ 取模。($n\le2e5$)

$Sol:$ 为了简单地描述这些图形(由于我们第一位都是最小值，这里直接忽视)，定义这些图形：$A:213,B:132,C:321$ ，$A-B-C=(x1x-312)-(1xx-123)-(3xx-312)=x1x+123-xxx+2xx$ 。接下来，我们按排列的大小顺序加点，用线段树维护 $x1x$ 和 $2xx$ ，用树状数组维护 $xxx,123$ 。这里仅简单描述一下：$1.$ 对于 $x1x$ ，我们维护 $s1$ 表示某个位置是否加入点，$s2$ 维护以 $i$ 点开头的 $x1x$ 型数量，每次加点询问其后的 $s2$ 的后缀和后，询问此点 $s1$ 的后缀和，求出此点构造的 $12$ 型的个数，而这个个数加到此点 $s1$ 的前缀上。$2.$ 对于 $2xx$ ，我们依然维护 $s1$ 表示某个位置是否加入点，用 $s2$ 维护以 $i$ 开头的 $2xx$ 型，具体的，每次加入一个点询问其 $s2$ 后缀和加入贡献，接下来询问 $s1$ 的后缀和算出此时其后的点数，作为其 $s2$ ，然后再将其前缀全部加上各自的 $s2$ 。时间复杂度 $O(n\log n)$ 。

$Sum:$ 考场上一直想想如何拆这几种图形，我把 $A$ 和 $B$ 都拆成了题解中的形式，但是我由于 $C$ 我可以求出来，我就没有拆 $C$ ，从而导致我 $A,B$ 拆出来的图形不够优美，没办法维护(考场上一直在想怎么维护)。

1.31 WC 模拟

T1.拓扑学入门

$Des:$ 长度为 $n$ 的序列，上面有 $m$ 个区间，定义其运算为求交和求并，要求其形成的一个封闭类的大小。($n\le2e5,m\le1e6$)

$Sol:$

$Sum:$

T2.嵌入

$Sol:$

$Sum:$

T3.求值

$Des:$ 给定 $n,b,c,d,e$ ，$ x_k=bc^{4k}+dc^{2k}+e $，第二行 $n$ 个整数 $a_i$ ， $\displaystyle f(x)=\sum_{i=0}^{n-1} a_ix^i$ ，答案对 $1000006$ 取模。($n\le 1e5$)

$Sol:$ 本题分两部分，第一个部分为第二个部分的弱化版。对于 $b=0$ ，$ \displaystyle f(x_k)=\sum_{i=0}^{n-1}a_i(dc^{2k}+e)^i=\sum_{i=0}^{n-1}a_i\sum_{j=0}^i \binom{i}{j}d^jc^{2jk}e^{i-j}=\sum_{j=0}^{n-1} c^{2jk} d^j j!^{-1} \sum_{i=j}^{n-1}i!(i-j)!^{-1}e^{i-j} $ ，对于后式我们规定 $\displaystyle g(j)=d^jj!^{-1}\sum_{i=j}^{n-1}i!(i-j)!^{-1}e^{i-j} $ ，于是 $g$ 是一个减法卷积，对于减法卷积，我们的做法事实是类似于加法卷积的，只要更换枚举方式就能转化成加法卷积，而对于加法卷积，我们就可以轻松地进行 $NTT$ 了，接下来原式变为 $\displaystyle f(x_k)=\sum_{i=0}^{n-1}c^{2ik}g(i)=c^{k^2}\sum_{i=0}^{n-1}c^{-(k-i)^2}c^{i^2}g(i)$，至于这个，我们做一个 $n2n$ 的卷积即可。对于 $b \neq 0$ ，设 $ d=\frac{d}{2b},e=e-b(\frac{d}{2b})^2 $ ，那么 $x_k=b(c^{2k}+d)^2+e$，$ \displaystyle f(x_k)=\sum_{i=0}^{n-1}a_i(b(c^{2k}+d)^2+e)^i=\sum_{i=0}^{n-1} a_i\sum_{j=0}^i \binom{i}{j}b^j(c^{2k}+d)^{2j}e^{i-j}=\sum_{j=0}^{n-1} (c^{2k}+d)^{2j} b^j j!^{-1}\sum_{i=j}^{n-1}a_i i! (i-j)!^{-1}e^{i-j} $ ，同理，我们设 $\displaystyle g(j)=\sum_{j=0}^{n-1} (c^{2k}+d)^{2j} b^j j!^{-1}\sum_{i=j}^{n-1}a_i i! (i-j)!^{-1}e^{i-j}$ ，对于后式我们依然使用减法卷积。

$Sum:$ 首先，我被这个模数给吓到了，不敢用 $NTT$，以及不懂减法卷积，考场上一直在想怎么处理那个玩意，然后就在往斯特林数上想，一直绕在里面了，最后啥都没写出来。

2.20 fuyuki

T1.线性基 (basis)

$Des:$ 求 $n$ 阶本质不同的线性基有多少。($n\le 1e5$)

$Sol:$ $n$ 阶本质不同的线性基等价于 $n$ 维 $2$ 进制超空间的子空间个数，而一个线性基的所有异或结果等价于 $n$ 维 $2$ 进制超空间的子空间内的向量 。而根据高斯系数，$n$ 维 $p$ 进制超空间的 $m$ 阶子空间个数为 $ \displaystyle \begin{bmatrix} n \ m \ \end{bmatrix}p=\frac{\Pi{i=n-m+1}^n (p^i-1)}{\Pi_{i=0}^m (p^i-1)}=[x^m]\Pi_{i=1}^{m}\frac{1}{1-p^i x}=[x^n]\Pi_{i=1}^m\frac{x}{1-p^ix} $ ，那么，我们要求的答案就是 $\displaystyle [x^n] \sum_{k=0}^n\Pi_{i=0}^k \frac{x}{1-2^ix}$，然后分治 $NTT$ 来做。这里简单解释一下如何分治 $NTT$ ：我们对于每个区间维护 $\displaystyle f(x)=\Pi_{i=l}^r x$ ，$ \displaystyle g(x)=\Pi_{i=l}^r (1-2^ix) $ ， $ \displaystyle h(x)/g(x)=\sum_{k=l}^r \Pi_{i=l}^k \frac{x}{1-2^ix}$ 。递归求这个即可。时间复杂度 $O(n\log ^2n)$

$Sum:$ 考场上只会 $n^2$ 递推。

T2.笛卡尔树 (cartesian)

$Des:$ 定义序列中一个元素的权值为以这个元素作为最大值的区间的最大长度。定义一个序列的权值为这个序列中每个元素的权值之和。给定长度为 $n$ 的序列 $a_i$ (为 $n$ 的排列)，分别对于 $k=1,2…n$ 求由 $a_i\le k$ 的元素构成的子序列的权值。($n\le1e5$)

$Sol:$ 关于维护每个值取到的左右端点显然可以吉老师线段树来处理，用吉老师线段树来维护每个点作为左端点或右端点出现了多少次 $sizl[i],sizr[i]$，同时，我们再用线段树维护前缀 $i$ 出现了 $cnt[i]$ 个数，那么最后的答案就是 $\sum sizr[i]cnt[i]-\sum sizl[i]cnt[i]$ ，答案的修改只在使用吉老师线段树的时候才会产生，所以只要在吉老师线段树进行修改的时候以及对前缀和进行修改的时候更改。时间复杂度 $O(n\log^2 n)$ 。

$Sum:$ 考场上有想过用吉老师线段树，但是由于没要想清楚求值如何处理，就写了一发暴力笛卡尔树。

T3.最短路 (spfa)

$Des:$ 给出一张无向图，边的长度为 $d_i$ ，每增加该边的长度代价 $c_i$ ，求在花费代价不超过 $s$ 的情况下 $1$ 到 $n$ 的最短路的最大值为多少。($n\le 100,m\le 500$)

$Sol:$ 对于原问题，我们总结以下几条结论：1.修改最短路长度时，我们一定是修改前 $k$ 短的路径，将其修改到同一值。2.若两条需要修改的路径上代价最小边相同，则修改该边。根据以上两条结论，我们会发现，当我们想修改一条路径的时候，我们一定是以路径上代价最小的开始修改，即我们的修改一定是在以代价 $c_i$ 构建的网络流上的某条割上修改。而根据这个我们可以列出线性规划，对偶后就是最小费用流。当然，我们还可以换一种角度思考，当我们的以 $d_i$ 为费用流的费用的时候，由于我们的 $spfa$ 每次是找出当前的一条长度最短(费用最少)的割，而第 $k$ 轮找出的最小割刚好就是与前 $k-1$ 条路无交集第 $k$ 短路(交集指割边的交)，也正好满足题面要求。这里的我们每轮跑出来的最小费用 $cost=flow(dis_t-dis_s)-s$ 。枚举一下到哪一轮即可。而这个函数又是个凸函数，可以使用三分。时间复杂度 $O(mincost_flo(n,m)+q\log n)$ 。

$Sum:$ 由于最近在看线性规划对偶的论文，考场上立刻想到了线性规划对偶问题，但由于水平有限，没有成功把原问题对偶成费用流。

2.21 yurzhang

T1.圣代桥 冰织 (kori)

$Des:$ 给定 $n,K$ ，求 $\displaystyle \sum_{i=0}^n i^K$。($n\le 1e9,K\le 1e7$)

$Sol:$ 易得原式 $\displaystyle =\sum_{j=0}^K \begin{Bmatrix} K \ j \ \end{Bmatrix} \binom{n}{j} j! 2^{n-j} $ ，将斯特林数展开：$\displaystyle \sum_{j=0}^k \binom{n}{i} i^K 2^{n-i} \sum_{j=0}^{K-i} \binom{n-i}{j} (-\frac{1}{2})^j $ 。我们设 $\displaystyle f(i)=\sum_{j=0}^{K-i} \binom{n-i}{j}(-\frac{1}{2})^j $ ，而我们又会发现 $f(i)=\frac{1}{2} f(i+1)+\binom{n-i-1}{K-i}(-\frac{1}{2})^{K+i} $ ，$i^K$ 用线性筛求出即可。时间复杂度 $O(n)$ 。

$Sum:$ 线性的做法我曾经做过，但由于推导的时候，我把斯特林数给展开错了，导致没有推出来。

T2.古仓 芽瑠(meru)

$Des:$ 给定 $n,m$ ，求 $\displaystyle \sum_{i=0}^m\binom{n}{i}$ 。

$Sol:$ 快速阶乘。

$Sum:$

T3.巧可拉 · 尼居(chocolat)

$Des:$ 给出 $n$ 个数，接下来进行 $m$ 次操作：1.区间加。2.区间最大与。($n,m\le1e5$)

$Sol:$ 一个强结论：任意一个区间只有前 $\log V$ 个数有贡献，我们只需要维护每个区间的前 $\log V$ 的数即可。

$Sum:$ 这个题的套路我们之前在学军的考试中遇到过，可是当时没认真做。

2.22 zeven

T1.数星星 (star)

$Des:$ 给定一个 $n$ 个点的多边形，求对称轴个数。$(n\le 1e5)$

$Sol:$ 给出几个显然的结论：1.对于所有的对称轴，其一定过几何中心；2.记所有与中心距离相同的点为一个类，对于原图的每一条对称轴，也一定是每个类中点构成的正多边形的对称轴。根据这两点，我们只需要找出最小的一个类，然后询问这个类构成的正多边形的对称轴。询问我们只需要在每个类中做字符串匹配。时间复杂度 $O(n\log n)$ 。

$Sum:$ 对于计算几何不够熟悉，导致 $atan2$ 函数的了解不够，函数写错了。 然后还爆精度了。

T2.守卫 (guard)

$Des:$ 一个网格上有 $n$ 个村庄，有 $m$ 个守卫，每个守卫守他路径构成的封闭多边形里的村庄，每个人至少守一个，代价为走过的路径，求最少代价。($n,m\le 1e6$)

$Sol:$

$Sum:$

T3.治疗 (cure)

$Des:$ 有 $n$ 个物品，我们要让他们全部消失，具体的，每轮若有 $x$ 个物品，则要花费 $a[x]$ 的代价让每个物品 $p$ 的概率消失，求全部消失的期望。($n\le5e5$)

$Sol:$ 这里只有一个 $ O(n\log ^2n) $ 的分治 $NTT$ 。显然可得一个式子 $f[i]=a[i]+\sum_{j=1}^i \binom{i}{j} p^j (1-p)^{i-j} f_{i-j}$ 对这个式子分治即可。

$Sum:$ 样例有误，导致一直不过。

2.23 ydykzwjj

T1.全军突击 (yyds)

$Des:$ 给定 $n,k,tp$ ，求 $\displaystyle \sum_{i=1}^n\sum_{j=1}^n\mu^tp(gcd(i,j))[gcd(gcd(i,j),k)=1]$ ，答案对 $20031219$ 取模。($n,k\le 1e10,tp={1,2}$)

$Sol:$

$Sum:$

T2.锦囊妙计 (trick)

$Des:$ 给定 $n$ 个数 $a_i$，这些数会变化，每个时刻 $a_i=max(a_i,a_{i-1})$ ，接下来 $m$ 次询问，每次询问一个区间 $[l,r]$ 在时刻 $t$ 的和。($n,m\le 2e5$)

$Sol:$ 本题仅给出 $O(n\sqrt n)$ 的算法。简化题意，对一个区间进行询问的时候，每个点的值变为 $\max(i,i-t)$。我们将区间分块，可以发现，每个点可能会在某个块中先出现若干次然后再全部消失，我们将出现和消失拆开，可以发现这两个东西都是个一次函数，其有可加性，求的时候只需要差分挂 $tag$ 。注意，出现时间和消失时间跟 $pr[i],nx[i]$ 相关，这里的 $pr[i]$ 为上一个大于等于 $a_i$ 的位置，$nx[i]$ 为下一个大于 $a_i$ 的位置，特别注意这里一个是大于另一个是大于等于。整体的时间复杂度 $O(n\sqrt n)$ 。

$Sum:$ 考场上写的 $n\sqrt n$ 的算法写挂了。

T3.乐善好施 (give)

$Des:$ 给出一张 $n$ 个点 $m$ 条边的图，求 $\max(\max_{i=1}^na_i,\max_{i=1}^m(a_{u_i}+a_{v_i}))$ 的期望，答案对 $998244353$ 取模。($n\le 25,m\le \frac{n*(n-1)}{2}$)

$Sol:$

$Sum:$

2.24 sinner

T1.序列 (sequence)

$Des:$ 给出长度为 $n$ 的序列，接下来 $m$ 次操作：1.$[l,r]$ 改为 $x$；2.$[l,r]$ 加上 $x$；3.$[l,r]$ 从小到大排序；4.$[l,r]$ 开方；5. 询问 $[l,r]$ 的 $x$ 次方膜 $y$ 之和。最后输出最终序列。随机数据。($n,m\le1e5$)

$Sol:$ 珂朵莉树。

$Sum:$ 珂朵莉树板子。

T2.区间 (segment)

$Des:$ 长度为 $n$ 的序列，接下来 $m$ 次操作：1.$[l,r]$ 加上 $x$；2.$[l,r]$ 改为 $x$；3. 将 $[l1,r1]$ 复制到 $[l2,r2]$ ；4.将 $[l1,r1]$ 与 $[l2,r2]$ 互换；5.询问 $[l,r]$ 之和。($n,m\le 3e5$)

$Sol:$ 可持久化平衡树。

$Sum:$

T3.排序 (sorting)

$Des:$ $1e8$ 个数 $2s$ 排序。($n\le 1e8$)

$Sol:$ $4$ 次基排卡寄存器。

$Sum:$ $WC$ 挑战原题。

2.25

T1.机械们的时间 (desirantes)

$Des:$ $n$ 堆石子，两个人进行博弈，每个人可以取某一堆的 $p^k$ 个石子，不能取者失败。接下来 $m$ 次操作：1.给区间 $[l,r]$ 加上 $x$ ；2.询问区间 $[l,r]$ 构成的游戏，先手是否必胜。($n\le 1e5$)

$Sol:$ 显然的结论：1.若 $p$ 为奇数，一堆石子的 $SG$ 函数为 $x\%(p+1)$ ；2.若 $p$ 为偶数，一堆石子的 $SG$ 函数为： 1.$x\%(p+1)=p$ 时，$SG(x)=2$ ；2.$x\%(p+1)\&1$ 时，$SG(x)=1$ ；3.其他情况，$SG(x)=0$ ；分块用树状数组分别处理块内 $1$ 和 $2$ 个数前缀和，修改时打标记记录 $0$ 移动到的位置，用树状数组更新答案，小块暴力重构。总时间复杂度 $O(n\sqrt n \log n)$ 。

$Sum:$ 常数怎么都卡不进去。

T2.心的破绽 (ag2o)

$Des:$ 对于一个大小为 $n$ 的排列，我们每次取相邻三个数的中位数，使它变成一个大小为 $n-2$ 的序列，直到最后只剩下一个数。求出所有大小为 $n$ 的排列最后剩下的数为 $k$ 的方案有多少。答案对 $998244353$ 取模。($n\le 1e6,n=2k+1$)

$Sol:$ 一个显然的套路：我们设结果为前 $k$ 小的情况，将前 $k$ 小的设为 $0$ ，其他值设为 $1$ 。现在我们需要考虑最终点为 $0$ 的情况，一个显然的结论：若有连续两个相同的点，那么他们将会持续到结束。那么情况也就很好考虑了：1.中点处存在连续两个以上的 $0$；2.中点一端存在连续的 $0$ ，一端也有连续的 $0$ ，中间用 $101$ 连接；3.中点一端存在连续的 $0$ ，另一端存在连续的 $1$ ，中间用 $01$ 连接，且连续 $0$ 离中点更近；4.中点一段存在连续的 $0$ ，另一端用 $10$ 连接；5.全部是连续的 $01$ ，且 $0$ 比 $1$ 多 $1$ 。枚举两个连续段之间距离即可。时间复杂度 $O(n)$ 。

$Sum:$ 好像做过类似的题，题目挺套路的。

T3.适合在密林航路的日子 (curise)

$Des:$ 给定一个序列，序列两点之间用边相连，到达一个点可以获得该点的值，过一条边，要减去边的值，求最长的一段区间，使其从起点到终点以及从终点到起点的路上，不会存在某一时刻值为负数。($n\le3e5$)

$Sol:$

$Sum:$