省选备考小结(part 2)

2.26 xzx34

T1.写意胜形 (dusk)

$Des:$ 长度为 $n$ 的序列，进行 $m$ 次操作：1.单点修改；2.询问两个区间排列后，是否存在 $k$ ，使其排列各位置之差为 $k$ 。($n,m\le1e6$)

$Sol:$ $hash$ 即可，用线段树维护一个区间的哈希值即可，时间复杂度 $O(n\log n)$。

$Sum:$ $T1$ 没有想清楚，直接拖垮整场考试。

T2.白色相簿 (watwo)

$Des:$ $n$ 个点的树，树上有 $m$ 种边，每种边有一个权值，求一条长度在 $[l,r]$ 之间的路径其权值和最大。这里的权值和定义为：路径上边权和，边种类相同的连续一段只贡献一次边权。($n,m,l,r\le1e5$)

$Sol:$ 按边排序后点分套线段树。时间复杂度 $O(n\log^2n)$ 。

$Sum:$ 这题除了码量极其之大，没什么思维难度，但是确实没时间做这题了。

T3.进击的魔法少女 (attack)

$Des:$ 给定 $A$ 矩阵，构造一个 $B$ 矩阵满足 $B$ 矩阵所有的值均在 $[l,r]$ 之间。使 $A,B$ 之间行差之和以及列差之和的最大值最小。($n,m\le200,l,r\le1000$)

$Sol:$ 二分差值，然后上下界可行流验证。

$Sum:$ 由于 $T1$ 拖累，没时间对题目进行过多分析，只列出了线性规划方程，准备二分然后单纯性检查(事实上后面这个过程和正解无异)。

2.27 Yukikaze

T1.藏弓待用 (easy)

$Des:$ 给定一段区间， $m$ 次操作：1.单点修改。2.区间查询最大权值。这里的权值定义为：一个区间选若干个点，不能出现三个连续的点。空间要求线性。$(n\le 1e6,m\le2e5)$

$Sol:$ 首先是模板的动态 $dp$ ，然后对序列按 $\frac{n}{3\log n}$ 分块，这样空间复杂度就被降下来了，然后对于所有询问跑 $\log n$ 次，时间复杂度不变。

$Sum:$ 单纯的卡科技题。

T2.山泽麟迹 (normal)

$Des:$ 最初离终点有 $n$ 的距离，有 $m$ 种机关，遇到第 $i$ 种机关会让距离减少 $a_i$ ，而下一次能遇到机关的 $a_j\le a_i$ ，每次等概率会遇到能遇到的机关，同时，还有 $p$ 的概率回到上一步。($n,m\le50$)

$Sum:$ 没有想到情况非常之少，一种在思考设计确切的状态。

T3.降众天华 (hard)

$Des:$ 树的大小为 $n$ ，题目分 $3$ 问：1.$y$ 的两棵树边的并集的连通块个数次方；2.给定一棵树，求所有问题 $1$ 的答案和；3.求所有情况下，问题 $2$ 的答案和。($n\le 1e5$)

$Sum:$ $WC2019$ 数树。

2.28 Aly

T1.另一道无名签到题 (eavsfyk)

$Des:$ 两个人进行博弈，他们分别有 $n,m$ 张牌，桌上还有一张牌，接下来他们轮流进行操作，每次还有选择直接猜桌上的牌或者询问对方是否有某张牌，对方必须如实回答。求先手获胜和后手获胜的概率。($n,m\le5000$)

$Sol:$ 首先，我们的决策可以分三种：1.猜牌；2.询问自己没有的牌；3.询问自己有的牌。对手有两种应对方式：1.对于对方询问的自己不存在的牌认为它是桌上的牌；2.对于对方询问的自己不存在的牌不认为它是桌上的牌。而猜牌在最终情况之前都是不优的，所有不予考虑。接下来就是个经典的 $nash$ 均衡，找到所有决策的均衡点即可。其中某些状态会降低当前的问题规模，而总的状态数只有 $nm$ 个。时间复杂度 $O(nm)$ 。

$Sum:$ 考场上知道怎么决策，但是不知道 $nash$ 均衡，我单纯地认为决策是确定的。

T2.发条城市 (city)

$Des:$ $n$ 个超市，$m$ 次操作，每次操作为：1.超市 $s$ 在 $t$ 天加入物品 $v$ ；2.超市 $s$ 删除在 $t$ 天加入的物品 $v$ ；3.询问 $[l,r]$ 区间的超市中在 $[t-x+1,t]$ 的时间内操作的物品和 $v$ 的异或最大值。这里的 $t$ 单调。($n,m\le 1e5$)

$Sol:$ 显然要用线段树套 $0/1trie$，由于 $t$ 是单调的，所以我每颗 $0/1trie$ 中只用维护当前节点子树中 $t$ 最大为多少，而删除则只用在最下面一层的节点维护一个堆即可。时间复杂度 $O(n\log^2n)$ ，空间复杂度 $O(n\log ^2n)$ 。

$Sum:$ 考场上没看到 $t$ 是单调的，硬是在二维的情况下做。

T3.五彩斑斓的世界 (colorful)

$Des:$ 给出 $n$ 个 $a_i$，求 $i=[l,r]$ 所有的 $\displaystyle \sum_{j=1}^{i-1}\binom{a_x}{j} \binom{a_y}{i-j} $ ，答案对 $998244353$ 取模。($n\le 1e5,R\le 5000$ 或 $R-L\le 500,R\le1e5$)

$Sol:$

$Sum:$

3.2 CTT 2019 day1

T1.递增树列 (tree)

$Des:$ 给定 $n$ 个点的树，求 $n$ 的所有排列中满足相邻两点的 $lca$ 深度非严格递增的个数，答案对 $1e9+7$ 取模。($n\le 80$)

$Sol:$ 首先，从根往叶子转移是不现实的，那么我们从下往上转移，设 $dp[i][j]$ 表示下一个点在 $i$ 的子树中，该子树选了 $j$ 个，接下来就是往父亲转移。此时就相当于给你若干堆物品进行排列，相邻两个物品不能出自同一堆。我们设 $dp[i][j][k]$ 表示处理到了第 $i$ 堆一共处理了 $j$ 个点其中有 $k$ 个非法相邻。然后各种枚举转移。时间复杂度 $O(poly(n))$ 。

$Sum:$ 经典 $dp$ 不会。

T2.文章 (article)

$Sum:$ 题目出的很巧妙，同时也反映了我对 $SAM$ 的了解不够深入，题目很简单的结论我却不知道。

T3.旅行 (travel)

$Des:$ $n$ 个国家，第 $i$ 个国家有 $a_i$ 个景点，每个景点一个美妙度 $b_{ij}$ ，进行 $k$ 次旅行，每次经过若干个景点：1.每个国家最多去一个景点；2.不能经过之前去过的国家；3.每次只能去奇数个国家；4.$k$ 次旅行后经过所有国家。定义一次旅行的收益为景点环上的最小权值，定义总收益为全局最小值。求最大收益。($n\le 100,a_i\le 5$)

$Sol:$

$Sum:$ 一般图最大匹配.

3.3 CTT2019 day2

T1.序列 (array)

$Des:$ 有一个从 $0$ 开始，无限长的序列 $a_i$ ，定义变换为：将所有 $a_i$ 赋值为 $a_i+a_{i+1}$ ，接下来 $q$ 次询问，每次给出 $n,m,K,x,v,mo$ ，求将 $pos \equiv x(\mod n)$ 的位置设置为 $v$ 后，经过 $K$ 次变换位置 $m$ 的值对 $mo$ 取模后的结果。($\sum n\le 1e6$)

$Sol:$ 显然，这个东西就是在一个环上变换，我们直接将 $x$ 和 $m$ 都扔到环上。而这个变换规则特别的组合数，环上第 $m$ 个位置的值就是：$\displaystyle \sum_{i=0}^K \binom{K}{i} [i\equiv m(\mod n)]$ 。而位置 $m$ 不太好求，我们先求位置 $0$ ，根据单位根反演：$\displaystyle \sum_{i=0}^K\binom{K}{i} \frac{1}{n} \sum_{s=0}^{n-1}W_n^{is} $ 。设 $\displaystyle f(k,s)=\frac{1}{n}\sum_{i=0}^k \binom{k}{i} W_n^{is} $ ，那么 $f(k,s)=(1+W_n^s)f(k-1,s) $ ，用快速幂就可以求出所有的 $f(n,s)$ 。接下来考虑第 $m$ 个位置，这个时候我们进行差分，可以发现最后的结果就是 $f(k,s,m)=W_n^s f(k,s,m-1)$ ，所以，每次再乘一个 $(W_n^s)^m$ 即可。时间复杂度 $ O(n\log n) $ 。

$Sum:$ 原根求法常数过大，同时数组开小了（每天一个爆零小技巧）。

T2.矩阵 (matrix)

$Des:$ 定义置换矩阵：每行每列有且仅有一个 $1$ 。给出一个矩阵 $B$，求一组线性无关的置换矩阵 $A_i$ 使其乘上相应系数使：$\displaystyle \sum_{i}^m \lambda_i A_i=B$ 。($n\le 50$)

$Sol:$ 首先是充分性的证明，由于我们每次贡献是每行每列都有的，所有行和与列和应该都相等。接下来是必要性的论证，我们将行与列建二分图，根据 $Hall$ 定理，若合法则一定可以有匹配。而每次匹配后都会选择最小的值将其删去，这样就会使原图少一个点，同时也使各个方案之间线性无关。时间复杂度 $O(n^4)$ 。

$Sum:$ 这道题是真的设计的特别巧妙。

T3.杀蚂蚁简单版 (ant)

$Des:$ 给出一棵树，一号节点只与二号节点相连，同时每个节点有权值 $a_i$，在节点 $u$ ，会以 $\frac{a[v]}{\sum a[son[u]]}$ 的概率走向 $v$，接下来 $m$ 次询问，求从 $z$ 出发随机游走，到一号节点停止，经过 $x$ 到 $y$ 的路径上的点的期望次数，答案对 $1e9+7$ 取模。($n,m\le 1e5$)

$Sol:$ 将询问按 $z$ 的 $dfs$ 排序， 然后线段树维护区间乘，将乘的次数降到 $2n$ ，再用树剖求答案。时间复杂度 $O(n\log n) $ 。

$Sum:$ 此题暂时未解。

3.4 FWT 专题

T1.最大公约数 (gcd)

$Des:$ $n$ 个数 $a_1,a_2,…,a_n$ ，求所有的 $x$ 满足能被这些数 $gcd$ 出来。求所有的 $x$ 的异或和。($n\le 1e6,a_i\le 2e7$)

$Sol:$ 我们将卷积定义为 $\displaystyle \sum_{gcd(i,j)=k} 1$ ，由于每次 $gcd$ 可以削一半，所以只需要将原数组 $f$ 自卷 $\log V$ 次即可。而取 $gcd$ 就相当于在以质因数分解的维度上取 $min$ ，类似于取交，也即高维后缀和。将 $FMT$ 扩展到 $K$ 维即可。时间复杂度 $O(V \log \ln V) $ 。

$Sum:$ 考场上发动我的数论知识，整了个很优秀的筛法，时间复杂度大概是 $k V\ln V$ ，下来之后对它进行了进一步的优化，将复杂度降到了直逼 $V \ln V+V\log V$ 的水平。

T2.企鹅物流 (delivery)

$Des:$ $n$ 个点树，边有边权，每个点可能有 $K$ 种颜色，有 $m$ 个点，每种颜色可以选这 $m$ 个点中其中一个作为起点，经过所有该颜色的点，求经过所有颜色中经过边的边权和（重复经过也算）最大值最小为多少。($n\le 1e5,m,K\le 20$)

$Sol:$ 一个显然的事实是，如果没有可选点的限制，我们可以一遍换根 $dp$ 求出所有点作为颜色 $k$ 的起点的最少费用，这个复杂度是 $O(Kn)$ 的。但是由于有选点的限制，所以就不能单纯的认为这些就是答案。由于答案显然具有单调性，所以我们可以二分，接下来需要做的就是验证合法性。观察到 $m,K$ 的大小都很小，一个初始的想法是跑网络流，但事实上网络流并不能处理这个问题。我们从选点的角度进行思考，会发现：每次我们选点就相当于在取并集，这个东西用 $FMT$ 跑 $m$ 遍即可。时间复杂度 $O(Kn\log V)$ 。

$Sum:$ 本题除了卡常以外其他都好说。

T3.内卷 (involution)

$Des:$ 给定一个 $n=2^k$ 的可重集合 ${a_0,a_1,…,a_{n-1}}$ ，求对于 $k$ ，求出集合 $a$ 中所有下标异或和为 $k$ 的子集的各元素乘积之和。答案对 $998244353$ 取模。($n\le 2^{21}$)

$Sol:$ 先考虑如何统计答案，这个东西就相当于我们对每一个 $a_i$ 做一遍 $FWT$ （$0$ 位补 $1$） ，然后再乘起来。这个复杂度是 $n^2$ 的，不能接受，那么我们考虑每个 $a_i$ 对它的 $FWT$ 贡献了什么，就可以得到卷起来之后的 $FWT$ 系数表达式：$\displaystyle [x^i]B(x)=\prod 1+(-1)^{popcount(i\&j)} a_j $ ，我们观察一下原 $FWT$ 的式子：$\displaystyle [x^i]B(x)=\sum (-1)^{popcount(i\&j)}a_j$ ，这里就相当于把 $+$ 重定义为 $*$ ，还有就是正负的差别。我们就分别把正负两个都提出来 $F(x),G(x)$ ，初始时表示只考虑前 $0$ 维的 $popcount$ 的影响，类似于 $FWT$，这两个幂级数之间又能继续往后转移，用类似 $FWT$ 的算法做即可，再 $IFWT$ 回来就是答案。时间复杂度 $O(n\log n)$ 。

$Sum:$ 本题是道非常好的题。

3.7 P_Y_Y

T1.巴士 (bus)

$Des:$ $n$ 个人分别在 $t_i$ 时刻开始等待，巴士往返一次需要时间 $m$ ，求所有人等车时间之和的最小值。($n\le 1e5,m\le 100$)

$Sol:$ 每个人往后维护 $m$ 个点，时间复杂度 $O(nm)$ 。

$Sum:$

T2.随机数 (rand)

$Des:$ $n$ 个数，每个数独立随机地从 $[1,m]$ 中选，接下来 $q$ 次询问，每次询问一个区间，求所有区间最小值的最大值的期望，对 $20040803$ 取模。($n,m,q\le 2000$)

$Sol:$ 对于包含其他区间的区间，没有意义，直接去除。接下来考虑 $minmax$ 容斥，接下来我们就只需要考虑所求区间并的最小值，维护 $dp[0/1][i][j]$ 表示选奇或偶个区间，选到第 $i$ 个点，长度并为 $j$ 的区间个数，用两个辅助数组辅助 $dp$ 即可，时间复杂度 $O(n^2)$ 。

$Sum:$ 这道题实在是由于我疏忽大意，我认为 $PYY$ 不会 $minmax$ 容斥，所以否认 $minmax$ 容斥。

T3.最小生成树 (mst)

$Des:$ $n$ 个点 $m$ 条边，边有 $a,b$ 两个边权，一个生成树的权值为 $\sum a*\sum b$，求最小生成树。($n\le 250,m\le 1e4,a,b\le 250$)

$Sol:$

$Sum:$

3.8 THU2017 day3

T1.简单数据结构 (dsa)

$Des:$ 给出一个长度为 $n$ 的序列 $a_i$，$m$ 次操作：支持左端加，左端删，右端加，右端删，且一个元素在序列中始终唯一，一个元素加入次数不超过 $10$，求最长倍数序列，以及不同开头个数 。($n\le 1e5,a_i\le1e6,m\le1e5$)

$Sol:$ 由于每个元素只会加入 $10$ 次，且最长倍数序列长度不超过 $\log V$ ，$n$ 个数中的因子个数级别为 $n\ln n$ ，所以暴力维护 $dp$ 即可。时间复杂度 $O(Cn\log V)$ 。

$Sum:$ 乱搞题。

T2.福若格斯 (frogs)

$Des:$ $5$ 个格子，左右两个各有相对着的两对青蛙，每次移动将一个青蛙前进一格，或者跳过前方一个不同朝向的青蛙到空格处，不能动为止，给出 $m$ 种初始状态，但每个状态有 $\frac{1}{2}$ 被杀掉，求所有情况下后手必胜的概率，对 $998244353$ 取模。($m\le 1e5$)

$Sol:$

$Sum:$ 不平等博弈。

T3.避难所 (hafen)

$Des:$ 设 $F(s4s3s2s1,p)=s4s3s2*s1$ ，在 $p$ 进制下的值 $x$ ，我们要求它最小的原值，这里贪心的从 $p-1$ 到 $2$ 试商，但是事实上这样做会出问题，我们求在 $p$ 进制下是否存在反例，若存在则输出一个解，反正输出 $-1$ 。($T\le 100,p\le 100000$)

$Sol:$ 若存在反例，则一定可以表述为 $3$ 位数，$p\le 100$ 可以暴力枚举，更大的数，我们可以输出 三个 $f(p^{\frac{1}{3}})*g(p^{\frac{1}{2}})$，$f(x)$ 表示大于等于 $x$ 的最小质数，$g(x)$ 表示小于等于 $x$ 的最大质数。

$Sum:$

3.9 THU 2017 day4

T1.我的生命已如风中残烛 (game)

$Des:$ 给定 $n$ 个钉子 $m$ 条绳子，绳子有长度 $L_i$，初始时绳子以某一个点作为圆心另一个点作为起点做圆周运动，遇到钉子就以该钉子为圆心做圆周运动，求所有绳子一共会改变多少次圆心。($n,m\le 500,L\le 1e9$)

$Sol:$ 将每条绳子周围的钉子极角排序，然后模拟圆周运动，若在两点加入循环就枚举最终分开的点。时间复杂度 $O(n\log L)$ 。

$Sum:$ 大计算几何题。

T2.榕树之心 (core)

$Des:$ 给出一棵大小为 $n$ 的树，初始只有根节点 $1$ 且中心在节点 $1$ ，之后开始从根节点生成这棵树，每生成一个节点，中心会往该节点方向移动一格，求最终可能留在哪些节点。($n\le 1e5$)

$Sol:$ 由于一个树内可以在不同的子树之间反复横跳，所以若一个子树内没有儿子的子树大小大于总节点数的一半，且总节点数为偶数就一定能留在原地。若存在，就递归进该子树进行反复横跳删点，再返回判断是否可行。注意到该转移可以换根做，时间复杂度 $O(n)$ 。

$Sum:$ 这是道非常巧妙的题面，考场上却并没有花时间去想。

T3.歌姬的故事 (rmq)

$Des:$ 长度为 $n$ 的区间，值域为 $[1,X]$，求满足 $m$ 种限制的区间个数，一种限制描述为： $[l,r]$ 存在最大值为 $x$ 。答案对 $998244353$ 取模。($n,X\le9e8,m\le 500,T\le 20,$)

$Sol:$ 首先对于每组值 $x$ ，我们把它的区间取出来，把比它要求小的区间挖去，再把剩下的区间拼起来，剩下的就是一个典型的 $dp$ 问题：给定一个区间其值域为 $[1,x]$ ，其中若干个区间必须出现值 $x$ 。时间复杂度 $O(Tm^2)$ 。

$Sum:$ 好想难写。

3.10 THU 2017 day2

T1.小 Y 和地铁

$Des:$ 一段区间上 $n$ 个点，最多有两个相同的点，相同的点要连起来，求最少会产生多少个交点。($n\le 44$)

$Sol:$ 一共有 $4$ 种情况，而这 $4$ 种情况本质上只有两种，考虑到这个之后使用搜索，时间复杂度 $O(2^{n/2})$ 。

$Sum:$

T2.小 Y 和二叉树

$Des:$ 给出一个二叉树，求最小中序遍历。($n\le 1e6$)

$Sol:$ 首先可以知道，当一个点度数 $\le 2$ ，我们称它为自由元，因为它可以选择是否立即加入遍历序列，所以，我们对于每个点的出边求出其子树的最小自由元，然后从最小的自由元可以建树。时间复杂度 $O(n)$ 。

$Sum:$ 考场上想歪了。

T3.小 Y 和奴隶主

$Des:$ 初始时有一个 $BOSS$ 和一个仆从，仆从血量为 $m$，你等概率地攻击其中一个，若攻击到仆从，此时仆从血量大于 $0$ 且仆从树小于 $K$ 即可以召唤一个血量为 $m$ 的仆从，接下来你依然是等概率地攻击所有敌人中的一个。求进行 $n$ 次攻击，攻击到 $BOSS$ 的期望次数。($T\le1000,n\le1e18,m\le 3,K\le 8$)

$Sol:$ 我们设还要攻击 $i$ 次的状态下的期望，它由攻击 $i+1$ 次且它能到达的状态转移过，同时还得加上攻击到一次的期望。由于并不是所有状态都会使用，我们只需要从初始状态能到达的状态即可。由于结果是个行向量，所以我们先倍增预处理出 $2$ 的整数次幂的情况，然后回复询问。时间复杂度 $O(T\log n A^2),A=120$ 。

$Sum:$ 很明显的矩阵快速幂，但是我的矩阵乘的重载写错了，导致 $RE$ 。

3.11

T1.迷宫 (maze)

$Des:$ $n$ 个点的树，每个点有 $p_i$ 的概率为入口以及 $q_i$ 的概概率为出口，求从出口进行 $dfs$ 到出口的期望转移次数。($n\le 1e5$)

$Sol:$ 我们先考虑每个点作为入口时的贡献，这个时候我们将它视为根，设 $f[x]$ 表示走完子树 $x$ 的期望转移次数，这个东西和我们要求的根节点的贡献类似，都是先考虑某个子树作为出口子树，然后同时统计进入其他子树的贡献。而我们观察这个转移，它可以做到换根，于是我们就可以用 $O(n)$ 的时间过掉本题。

$Sum:$ 简单的概率换根 $dp$ ，概率转移的设计还有点不熟悉，考场上凭借直觉写的转移。

T2.道路修复 (mst)

$Des:$ $n$ 个点 $m$ 条边的图，求与 $1$ 号节点相连边上为 $k$ 的最小生成树。($n\le 5000,m\le 1e5$)

$Sol:$ 由于最小生成树关于连边数 $k$ 是个凸包，所以我们可以使用 $wqs$ 二分。唯一的问题在于，若有多个值和与 $1$ 相连的边权值相同，则可能会使答案错误，一种解决方法是在排序的时候尽可能将与 $1$ 相连的边排在前面，当选的个数大于等于 $k$ 的时候再判定恰好选 $k$ 个是否和原答案相同。时间复杂度 $O(m\log V)$ 。

$Sum:$ 考场上使用断环算法。

T3.迷你高尔夫 (secret)

$Des:$ $n$ 个人每个人有 $m$ 个分数 $a_{ij}$，有一个未知值 $x$ ，所有大于 $x$ 的分数都变成 $x$ ，在任意 $x$ 的情况下，每个人的排名最低是多少，排名为小于等于自己分数的人数。($n\le500,m\le50,a_{ij}\le1e9$)

$Sol:$

$Sum:$

3.13 zsw

T1.管理 (position )

$Des:$ $n$ 个居住区在一条水平线上，第 $i$ 个居住区在 $D_i$，在这些居住区中建立不超过 $K$ 个避难所，在第 $i$ 个点建立避难所消耗 $C_i$，若距离第 $i$ 个居住区不超过 $S_i$ 的区域内都没有避难所则消耗 $W_i$ 。($K\le 100,n,C_i,W_i\le 1e4,D_i,S_i\le 1e9$)

$Sol:$

$Sum:$

T2.花火 (firework)

$Des:$ $n$ 个白点在一条水平线上，第 $i$ 个点在位置 $D_i$，初始时只有第 $K$ 个点是黑点，接下来所有点都开始运动，当黑点遇到白点时，白点将变黑，但每个黑点会在 $T$ 时间后变回白点，求所有的点的最大速度至少为多少时所有的点都能变过黑点。($n\le1e5,T,D_i\le 1e9$)

$Sol:$

$Sum:$

T3.博弈 (game)

$Des:$ 给定一个长度为 $n$ 的字符串，字符集大小为 $K$ ，两个人进行博弈，每个人可以选择删去字符集中某一个字符或者将字符串重排，每次操作后不能出现相同的字符串，不能操作者失败。求所有 $k^n$ 个字符串中先手必胜的有多少个，答案对 $998244353$ 取模。($n\le 3e5,K\le 1e8$)

$Sol:$

$Sum:$

3.14 Yukikaze

T1.黑暗普通市民 (special )

$Des:$ 一个大小为 $n$ 的树，点权为 $0/1$ ，每次删去一个父亲已删去的点，将其权值加入序列，求最后序列逆序对个数最少是多少。($n\le 1e5$)

$Sol:$ 正面考虑删点不易求解，我们考虑反面求合并，由于逆序对的性质，当我们合并两个子树的时候，若 $a_ub_v<a_vb_u$ ，那么显然选子树 $u$ 更优，根据这个，我们就能钦定每次应该选择合并哪些子树，把这个作为权值扔到堆里即可。时间复杂度 $O(n\log n)$ 。

$Sum:$ 对于删点的题，若正面做很难满足条件，那么我们就反过来思考，从结果往初始条件推。不过这题就算我想回推也发现回推特别难。

T2.暑假最后一天 (expert)

$Des:$ $n$ 个值 $0/1$，每次有 $ p_i$ 的概率对第 $i$ 个值进行修改，求最后达到 $s_i$ 的期望次数，答案对 $998244353$ 取模。($n\le 100,\sum p\le 1e5$)

$Sol:$ 设 $f_S$ 表示到达状态 $S$ 所需要的期望次数，显然可以得到 $\displaystyle f_S=\sum_{i}f_{S\bigotimes i} p_i +1$ ，可以发现这个式子是个异或卷积式，设 $F(x)$ 为 $F_S$ 的生成函数，$G(x)$ 为 $p_i$ 的生成函数，那么 $\displaystyle F=F*G+\sum x^i+c$ 。

​ 由于零次项未定义，所以带一个常数 $c$ 。我们将其 $FWT$ ，$\displaystyle [x^S]\hat F=\hat F*\hat G +\sum(-1)^{i\in S}+c $ ， 在零处可得：$c=2^n$ 。带回 $\hat F$ 可得 $\displaystyle \hat F=\frac{c}{1-\hat G}$ 。

$Sum:$ 这道题真的是非常考察选手对 $FWT$ 的理解和使用，深入探究了 $FWT$ 的内涵，以及对于一个多项式，当我们不知道其常数项时，我们通常带入特值（如 $0$） 来求解，此题更是将这种方式运用到了极致。

T3.四季轮转与吸血鬼 (lunatic)

$Des:$ $n*n$ 的矩阵，$m$ 次区间加，$q$ 次区间询问最大值，修改的询问全部离线。($n,m\le5e4,q\le5e5$)

$Sol:$

$Sum:$

3.15 CTT2019 day3

T1.投影对称 (projection)

$Des:$ 给定若干个点，求有多少条互不平行的直线使这些点关于它们投影对称。($n\le 2000$)

$Sol:$ 考虑质心，对于合法的直线，这 $n$ 个点投影后的对称中心一定是质心，删去与质心重合的点以及关于质心对称的点，剩下的点枚举 $a,b$ 以其中心与质心的连线，判断是否合法。时间复杂度 $O(n^2 \log n)$ 。

$Sum:$

T2.数圈 (circle)

$Des:$ 给定 $n$ 个数 $a_i$ ，它们构成一个环，每次选环上一个值 $a_i$ 使：

​ $a_{i-1}’=a_{i-1}+a_i,a_i’=-a_i,a_{i+1}’=a_{i+1}+a_i $

​ 求最少需要多少次才能将所有数变成非负，无解输出 $-1$。($n\le 1e5$)

$Sol:$ 我们定义广义前缀和：$S_i=S_{i-1}+a_{i\mod n}$ ，发现我们每次操作只交换了两个前缀和位置，而我们的目标状态是不存在逆序对，因此，我们相当于统计这个广义前缀和上的逆序对个数。

1. $sum<0$ 一定无解。

2. $sum=0$ 只有 $a_i$ 全 $0$ 才有解。

3. $sum>0$ 才统计答案。

   考虑如何统计答案，我们将每个值拆为 $a*sum+b$ ，我们要求的就是以 $(a,b)$ 为坐标的二维数点，按照 $a$ 排序后维护一个树状数组即可。时间复杂度 $O(n\log n)$ 。

$Sum:$ 由于序列的权值和未变以及位置变化后只有几个单点的值改变了，应该能从这个地方想到要使用前缀和。

T3.查找 (search)

$Des:$ 给定一个 $n*n$ 的矩阵以及一个值 $X$，其权值各不相同，且权值为单调：

​ $a[i][j-1]< a[i][j],a[i-1][j]<a[i][j] $ 。

​ 每次你可以调用交互库的询问 $ask1(x1,y1,x2,y2)$ 以比较矩阵中两点的权值大小，或调用 $ask2(x,y)$ 以比较 $X$ 与矩阵中某点的权值大小，求矩阵中小于 $X$ 的点个数。($n\le 2000,k1\le 50000,k2\le 64$)

$Sol:$

$Sum:$

3.16 CTT2019 day4

T1.异或 (xor)

$Des:$ $\displaystyle \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \sum_{k=0}^{n-1}(i\bigotimes j\bigotimes k)^d $ 。($n\le 2^{30},d\le 1e5$)

$Sol:$ 分析数据，我们会发现不同的异或值取值只有 $\log n$ 个，而对于这个 $\log n$ 的取值，我们要求的就是一个 $d$ 次方前缀和， 而我们知道 $d$ 次方的前缀和是一个 $d+1$ 次多项式，因此我们可以通过快速插值求得。时间复杂度 $O(d\log n)$ 。

$Sum:$ 考场上在写拉格朗日插值，时间复杂度 $O(n\log^2 n)$ 平添了一个 $\log n$ 。

T2.N门问题 (door)

$Des:$ $n$ 个门，其中一个门后面有奖励，$A$ 等概率的固定一个门，而 $B$ 开一个非固定门的空门，但是 $A$ 认为 $B$ 是等概率地开非固定门，求 $B$ 在最优策略下，$A$ 得奖的概率。($n$ 由 $excrt$ 获取)

$Sol:$ $n>10$ 概率为 $0$ ，$n\le 10 $ 打表得出。由于每次固定一个门后，该门会变成唯一的最小概率，所以原问题相当于初始时， $n$ 个物品同时在队首，有一个是关键物品， $A$ 每次等概率地将队首某物品丢到对尾，而 $B$ 可以选择将某个物品除外，求 $A$ 最后拿到关键物品的概率。

$Sum:$ $excrt$ 中注意使用快速乘防溢出。

T3.区间匹配 (match)

$Des:$ 两个长度为 $n$ 的序列 $a,b$ ，给定参数 $l_a,l_b$ ，求一个 $n$ 的排列 $p$ ，使：

​ 1. $∀i, ai ≤ bpi ≤ ai + la$ ；2.$bpi + lb ≤ ai + la$ 的 $i$ 尽可能多。若不存在，输出 $-1$ 。($n,a_i,b_i,l_a,l_b\le 5e5$)

$Sol:$ 原问题等价于：两个区间长度固定的区间序列进行匹配，$B$ 的左端点必须在 $A$ 的区间内，若 $A$ 完全包含 $B$ 则参生 $1$ 的贡献。我们贪心地从右往左匹配，每次手上拿着第一个未匹配的无贡献 $B$ 区间 $x$ 和第一个未匹配的有贡献 $B$ 区间 $y$ ，若 $y$ 右方存在 $A$ 的右端点数和 $B$ 的左端点相同的情况，则说明现在必须选 $x$ ，反之选 $y$ 不会变劣，证明类似于找增广路。

$Sum:$

3.17 THU2017 day1

T1.生成树计数 (tree)

$Des:$ $n$ 个连通块，第 $i$ 个连通块有 $a_i$ 个点，设第 $i$ 个连通块连出 $d_i$ 条边，$ \displaystyle val(T)=\prod_{i=1}^n d_i^m \sum_{i=1}^n d_i^m $ 。($n\le3e4,m\le30$)

$Sol:$ 根据 $prufer$ 序列，答案为：

​ $\displaystyle \sum \prod a_i^{di+1} \prod \frac{(n-2)!}{d_i!} \prod (d_i+1)^m\sum (d_i+1)^m $

​ 我们将常数项提出，并更换枚举方式：

​ $\displaystyle (n-2)! \prod a_i \sum \sum_i \frac{(d_i+1)^{2m}a_i^{d_i}}{d_i!}\prod_{i\neq j}\frac{(d_j+1)^m a_j^{d_j}}{d_j!} $

​ 考虑后面两项，其形式非常整齐，所以我们设

​ $\displaystyle F(x)=\sum \frac{(i+1)^m}{i!}x^i $ ，$\displaystyle G(x)=\sum \frac{(i+1)^{2m}}{i!}x^i$

​ 那么原式变为（忽略常数项）： $ \displaystyle \sum \frac{G(a_ix)}{F(a_ix)}\prod F(a_jx) $

​ 由于后式是多个多项式卷积，所以我们考虑使用 $\ln+\exp$ ，那么原式就被拆成两个多项式卷积。

​ 设 $A(x)=\displaystyle \sum_i (\sum_k a_k^i) x=\sum \frac{1}{1-a_ix}$ ，使用分治求得即可。

​ 前式先求出 $\displaystyle \sum\frac{G(x)}{F(x)} \circ A(x) $，后式为 $e^{H(x)}$ ，$H(x)=ln F(x) \circ A(x) $

​ 将两式卷起来即可，时间复杂度 $O(n\log ^2 n)$

$Sum:$

T2.无限之环 (infinityloop)

$Des:$ $nm$ 的网格有 $16$ 个水管，其开口对应其二进制，每次可以将一个管子转 $90$ °，求最少需要多少次使水管开口相互对应。($nm\le 2000$)

$Sol:$ 黑白染色，将每个点拆成 $4$ 个，然后用费用流求解，建图有点 $trick$。

$Sum:$

T3.Hello World! (helloworld)

$Des:$ 给出一颗大小为 $n$ 的树，每个点有点权，接下来 $m$ 次操作：1.在 $u$ 到 $v$ 的路径上走，每隔 $k$ 的距离将该位置的值开方向下取整。2.在 $u$ 到 $v$ 的路径上走，每隔 $k$ 的距离取该位置的值。（首尾一定操作）。($n\le5e4,m\le4e5$)

$Sol:$

$Sum:$ 大数据结构题，不过可以通过奇怪的写法通过。

3.18 CEOI2019

T1.amusement

$Des:$ $n$ 个节点 $m$ 条边的有向图，每次可以选择若干条边进行翻转，求所有翻转后为有向无环图的情况中翻转边的数量之和。($n\le 20,m\le \frac{m*(m-1)}{2} $)

​ 由于一个独立集 $S$ (各点之间没有连线) 对于已有图 $T$ 的连边是固定的，所以可以考虑从独立集出发，但由于这个答案是会被重复计算的，所以使用容斥，那么答案的形式就是：

​ 该式为子集卷积，套用子集卷积求逆即可（先转站位形式幂级数，再 $n^2$ 求逆），时间复杂度 $O(n^22^n)$ 。

$Sum:$

T2.diameter

$Des:$ $n$ 个点的树，动态维护直径，保证每次修改为正值。($n\le2e5,m\le1e5$)

$Sol:$ 设 $dis[a]$ 为 $a$ 到根距离，一条路径的权值为 $ dis[a]+dis[b]-2*dis[lca(a,b)] $ ，由于 $lca(a,b)$ 在欧拉序上为 $a,b$ 区间内的最小 $dfn$ 值，而其 $dis$ 也为最小，所以我们就是要求区间左右两端减区间最小值，这个用线段树维护。分别维护 $mx,mn,lmx,rmx,res$ 分别表示区间最大值、区间最小值，区间最最大值减最小值，区间右最大值减最小值，区间答案。时间复杂度 $O(n\log n)$ 。

$Sum:$ 曾经见过这个做法，但是考场上没想起来。

T3.magic

$Des:$ $n$ 个节点的树，有 $m$ 个果实，在第 $v_i$ 个节点有一个会在 $d_i$ 天成熟价值为 $w_i$ 的果实，只有刚好在第 $d_i$ 天将节点 $v_i$ 从原树分离出来才能获得这个价值，求最后的价值和。($n,m\le1e5$)

$Sol:$ 考虑 $O(n^2)$ 的暴力，$f[i][j]$ 表示节点 $i$ 在时刻 $j$ 的最大值，可以发现这个函数是单调的且拐点很少，所以我们使用启发式合并即可。时间复杂度 $O(n\log^2n)$ 。

$Sum:$

3.20 省选模拟

T1.颜色 (color)

$Des:$ 给定一个长度为 $n$ 的序列 $a_i$ ，接下来 $m$ 次操作：1.将 $a_i$ 修改为 $w$ ；2.询问长度为 $k$ 的区间内不同值个数之和。($n,m\le 3e5$)

$Sol:$ 考虑对颜色建线段树，修改就变成了区间加一个平行四边形，使用线段树维护等差数列。时间复杂度 $O((n+m)\log n) $ 。

$Sum:$ 卡常真折磨。

T2.断章取义 (garble)

$Des:$ 给定 $m$ 个字符串，将这个字符串里所有子串全部拉出来，求最小需要多少次覆盖，能覆盖所有子串，并且使子串之间不存在包含关系。($\sum s\le 1e5$)

$Sol:$ 一个经典的结论：最小偏序覆盖等于最长反链。建广义后缀自动机，在自动机上 $dp$ 跑最长链即可（这里的偏序关系定义为包含），时间复杂度 $O(n)$ 。

$Sum:$ 刚学 $oi$ 时学的一个结论，现在都忘了。

T3.序列 (sequence)

$Des:$ 给定一次长度为 $n$ 的序列 $a_i$ 和参数 $m$ ，接下来 $q$ 次操作：1.$[l,r]$ 每个数加 $x$ 对 $m$ 取模；2.询问 $[l,r]$ 数之和。($n,m,q\le1.5e5$)

$Sol:$ 将序列分块，树状数组维护下标 $m$ 的区间和，修改为下标平移，时间复杂度 $O(n\sqrt n\log n)$ ，使用归并排序或基排会更优秀。

$Sum:$ 曾经做过一道相同方法的题，同样是用 $n\sqrt n \log n$ 卡过了，但是今天在考场上没想 $T3$ ，导致没有分。

3.21 Aly

T1.你的生命已经过加强 (candle)

$Des:$ 给定 $n$ 个数 $a_i$，表示一个长度为 $a_i$ 的左括号序列，该序列不能被拆分，将这些左括号序列组合起来，并配上右括号（不能在一个完整的左括号序列之间）保证其合法，定义其权值为所有相邻的完整左括号序列 $(a_i*a_j+1)$ 之积，求本质不同的所有情况的权值之和，这里的本质相同定义为：可以通过交换两个完整且合法的一段括号序列（左括号序列不能被拆分）。($n\le 5e6$)

$Sol:$ 考虑原题面的含义：相当于一棵树，$a_i$ 为长度为 $a_i$ 的链，相邻链之间两点之间相互连边，求该无向图构成的有根树个数。

$Sum:$

T2.木与 (tnt)

$Des:$ $n$ 个点的树，指定 $m$ 条路径，求多少树上路径不是这些路径的子路径。($n,m\le2e5$)

$Sol:$ 考虑点分，在每一层的分治中，我们每次只处理一个子树，在 $dfs$ 这个子树的时候，我们每次处理当前点过点分中心的链，并查询自己上一次更新答案的位置，和该位置一并更新答案，然后给外子树染色，接下来每次多染一个点就将当前点到点分中心路径上所有点对新增的外子树染色点的贡献加上，回溯的时候要去掉对于外子树的染色。由于染色是链染色，而查询也是链查询，所以应该是只能使用树剖。树剖时间复杂度最劣是 $O(n \log^2n)$ ，而由于是在点分中，所以根据主定理，时间复杂度应该还是 $O(n\log ^2n)$ 。

$Sum:$ 考场上想出一个无比麻烦的写法，由于偷懒没写树剖，最后发现自己转 $dfn$ 序做的链加和点查询写假了。

T3.Pretests Passed(data)

$Des:$ 给出两个程序，构成输入，使其输出相同。

$Sol:$

$Sum:$

3.22 ceoi

T1.bridges

$Sol:$ 设 $dp[i]$ 表示以 $i$ 为桥的最小费用，$s_i$ 为 $w_i$ 的前缀和，那么有

​ \(dp[i]=\min (dp[j]+(h_i-h_j)^2+s[i-1]-s[j])\)

​ 我们移项可得：

​ \(dp[i]-h_i^2-s[i-1]+2*h_i*h_j=dp[j]+h_j^2-s[j]\)

​ 这是经典的斜率优化式子，动态维护凸包即可。时间复杂度 $O(n\log n)$ 。

$Sum:$ 在我使用 $vector$ 模拟平衡树的时候，忘记去重了，导致 $vector$ 变得非常劣。

T2.matching

$Des:$ 给定一个长度为 $m$ 个序列 $h_i$ （元素各不相同），再给定一个长度为 $n$ 的排列 $ p_i$，求 $h_i$ 中有多少个长度为 $n$ 的区间 $a_i$ 满足：将其排序后得到 $a_{p_i}$ ，输出首项下标。($n,m\le 1e6$)

$Sol:$ 首先想到的是哈希，然后我们顺序做，每次移动删除一个数加入一个数，这会改变排名的形式以及一段排名之内的哈希值之和，这个可以用平衡树来维护，排序键值维护序列有序，再维护子树的哈希值之和。时间复杂度 $O(n\log n)$ 。

$Sum:$ 很套路的题，考场上十几分钟想出来，但是由于 $T1$ 卡太久，导致我没时间写了。

T3.trap

$Des:$ 一棵树，有一个起点一个终点，一只老鼠在起点处，每次会走一条没走过的边，每次它走之前你可以选择一种操作：1.删去一条边；2.让老鼠又能走某条走过的边。你希望尽可能少的操作使老鼠到达终点，老鼠希望你尽可能多的操作使它到达终点，求最优决策下，你最少需要多少次操作。$(n\le 1e6)$

$Sol:$ 我们将终点视为根，那么我们就是要把老鼠往根节点逼。我们考虑它往子树中钻的情况，它一定是走到叶子，然后到根的路径上的其他子树全部被堵死，只能走到根。设 $f_i$ 表示 $i$ 节点到叶子节点再回来的最多操作次数，那么显然它每次会选择最大 $f_i$ 子树转移，或者，它往上走几格再往一个子树里钻，由于操作过多，我们无法很好地处理，所以我们选择二分答案。接下来只需要确认这个答案是否合法。若老鼠往某个子树里钻会导致我们无法在规定答案内回到根，那么我们就要在它到达之前把这个子树给封起来，每次检查只用检查是否能按照这个策略完成即可。时间复杂度 $O(n\log V)$ 。

$Sum:$ 这是道非常好的二分答案题，当我们的策略无法被很好的评估的时候，我们可以采取二分答案来对我们的策略进行评估。

3.23 lk 1

T1.随机关卡 (game)

$Des:$ $n$ 个游戏，第 $i$ 个游戏有 $p_i$ 的概率获得 $1$ 分，$A,B$ 两人分别进行 $A,B$ 次游戏，每次等概率选一个游戏，求最后 $B $ 的分数严格大于 $A$ 的概率，答案对 $1e7+19$ 取模。($n,A\le5e6,B\le 1e18$)

$Sol:$ 显然，这 $n$ 个数几乎就是废的，相当于一个 $p$。我们要求的式子是

​ \(\displaystyle \sum_{k=0}^A \binom{A}{k} p^k(1-p)^{A-k} (1-\sum_{i=0}^k\binom{B}{i}p^i(1-p)^{B-i})\)

​ 观察发现模数不是很大，那么我们就不能预处理阶乘，只能使用卢卡斯定理， 用欧拉筛求出所有数的逆元然后线性求这个式子即可。时间复杂度 $O(1e7+19)$ 。

$Sum:$ 预处理阶乘只能预处理到 $\frac{mod}{2}$ 。

T2.企鹅物流 (logistic)

$Des:$ 给出一列数 $a_i$ ，我们定义一段区间的权值为：拿 $s=0$ 和若干数依次取均值后的最大值。求所有区间的权值之和，答案对 $998244353$ 取模。($n\le 5e5 $)

$Sol:$ 我们考虑每个点的贡献，对于点 $k$ ，考虑左边的权值：点 $i$ 到点 $k$ 路径上大于等于 $a_k$ 的个数 $cur$ ，其贡献 $\frac{1}{2}^{cur}$ ，右边的权值：点 $i$ 到点 $k$ 路径上大于 $a_k$ 的个数 $cur$ ，其贡献 $\frac{1}{2}^{cur}$ 。设左权值 $ls$ ，右权值 $rs$ ，该点贡献为 $a_kls(rs+1)$ 。该值可用线段树维护区间加区间乘来实现（每次全局 $+1$ ，大于等于(右权值为大于)自己的值乘上 $\frac{1}{2} $） ，查询为单点查询。时间复杂度 $O(n\log n)$ 。

$Sum:$

T3.神秘代码 (magic)

$Sol:$ 本题可以用 $SAM$ 或 $SA$ 。考虑使用容斥统计答案：先对于全局取相互之间的 $lcp$ 之和，再逐个减去每个串同时为正面与反面的贡献，最后再加上每个串仅为正面或反面的贡献。至于每一次的贡献，我们可以使用 $SAM$ 或 $SA$ 。对于 $SA$ ，由于 $SA$ 上求 $lcp$ 就是求区间最小值，那么我们可以用单调栈来模拟这个过程，统计答案的时间复杂度 $O(n)$ 。由于建 $SA$ 的时间复杂度 $O(n\log n)$ ，所以总的时间复杂度 $O(n\log n)$ 。

$Sum:$ $SA$ 的常数太大了，过不了 $1e6$ 的数据。

3.24 lk 2

T1.90-degree Rotations

$Des:$ 给定一个 $n*m$ 的网格图，其中有 $K $ 个格子上有金币，你控制一个机器人从任意一个由金币的点开始，按一个方向走任意步，到达另一个有金币的格子，再向左或右转 $90°$ 继续收集金币。若无法到达有金币的格子则停止。询问是否能收集完所有金币（金币收集后就消失了）。($n,m\le 2000$)

$Sol:$ 考虑原问题就相当于一笔画问题，但是由于我们必须旋转，所以我们得转换模型。我们将行列拆成点，每有一个金币就将该金币所在的行列点连边，接下来再考虑一笔画问题即可。一笔画问题：对于无向图，$0/2$ 个度数为奇数的点；对于有向图，存在一个入度比出度大 $1$ 的起点，一个长度比入度大 $1$ 的终点。时间复杂度 $O(n+m)$ 。

$Sum:$ 非常好的一笔画建模问题。

T2.Multisets

$Des:$ 定义两个可重集合的大小为：若可重集合 $A$ 与 $B$ 出现次数不同的最小元素的出现次数。若出现次数更多，则说明该集合更小。给定一个大小为 $n$ 的序列 $a$ ，求由该序列的连续子序列构成的可重集合中第 $K$ 小的集合。($n\le 1e5,K\le \frac{n(n+1)}{2}$)

$Sol:$ 若通过枚举所有集合来求第 $K$ 小的集合显然是不现实的，一个可行的思路是去判断一个集合的排名，即判断有多少集合小/大于它。事实上，判断有多少集合大于它更方便，我们可以通过顺序枚举每个左端点来求有多少集合大于当前集合，由于序列的单调性，这个可以用值域线段树 $O(n\log n)$ 的求出一个集合的排名，同时还能求出哪些范围的集合比它小。根据每次查排名可获得的信息，我们设计算法。由于集合的单调性特殊，若使用正常的二分无法获得答案，那我们就规定左端点，设置其右边界（初始全为 $n$） ，如何随机一个左端点再在该左端点所限制的区域内随机二分一次，通过反馈的信息，调整所有左端点的右边界，求得答案的期望次数为 $O(n\log^2 n)$ 。

$Sum:$ 考场上写了 $O(n\log n)$ 的查排名，但是由于我对随机一无所知，所以没有设计出该算法。

T3.Fibonacci’s Nightmare

$Des:$ 设 $a_0=1$ ，对于其后每一个 $n$ ，等概率从 $[0,n-1]$ 中选 $K$ 个数 $i_1,i_2…i_K $ ，令 $\displaystyle a_n=\sum a_{i} $ 。求 $\mathbb E(a_n^K)$ 对 $998244353$ 取模。($n\le1e5,K\le 10$)

$Sol:$ 考虑 $\mathbb E(a_n)$ 的组合意义：点 $n$ 对于 $[0,n-1]$ 随机连 $K$ 条边， $0$ 点向外流 $K$ 条流量的方案数。那么同理 $\mathbb E(a_n^K)$ 的组合意义就是将 $K$ 条边和 $K$ 条流量打上标记，求方案数。接下来讲与正解无关的 $K=2$ 的情况下的写法：

​ \(\displaystyle \mathbb E(a_n^2)=\frac{1}{n^2} \mathbb E(\sum \sum (a_i+a_j)^2)= \frac{2 }{n}\sum \mathbb E( a_i^2) +\frac{2}{n^2} \mathbb E(\sum \sum a_i*a_j)\)

​ 前式为递推，考虑后式的求法：

​ \(\displaystyle \mathbb E(\sum \sum a_i*a_j)=\mathbb E((\sum a_i)^2)=\mathbb E((\sum a_j)^2 +2\sum a_j *a_i +a_i^2 )\)

​ 由于 $\displaystyle \mathbb E(a_n)=\frac{1}{n}\mathbb E(\sum a_j+a_k) $ ，所以上式又等于：

​ \(\displaystyle \mathbb E(\sum \sum a_i*a_j)=\mathbb E((\sum a_j)^2) +\frac{4}{n} \mathbb E ((\sum a_j)^2) + \mathbb E (a_i^2 )\)

​ 然后就可以 $O(n)$ 递推求解 $K=2$ 的情况。

$Sum:$ 我对期望简直是一无所知。

3.25 zlt

T1.矩阵填数 (matrix)

$Des:$ 给定一个 $n*m$ 的矩阵，在其中填入 $ [1,S] $ 中的数，接下来 $K$ 个限制：$[x1,y1]$ 到 $[x2，y2]$ 矩阵之内的最大值为 $v_i$ ，求总方案数，答案对 $998244353$ 取模。($n,m,S\le 1e4,K\le 20$)

$Sol:$ 考虑使用容斥：设当前最大值为 $x$ 的总方案数，将限制值为 $x$ 的矩阵给掏出来，求在这些矩形内填 $[1,x]$ 但不满足这些条件的方案数，用总方案减去即可。时间复杂度 $O(n^3\log S 2^n)$ ，这里的 $O(\log S)$ 可以进行优化使复杂度降低。

$Sum:$

T2.回文子串 (palindrome)

$Des:$ 给定一个长度为 $n$ 的字符串 $S$ 和一个参数 $K$ 以及 $m$ 个操作：1.将 $[l,r]$ 的字符替换为 $c$ ；2.询问 $[l,r]$ 中有多少对长度不超过 $K$ 的回文串。($n\le 5e4,m\le 3e4,K\le 50$)

$Sol:$ 由于 $K$ 很小，我们先预处理出每个字符为中心的长度不超过 $K$ 的回文串个数，对于所有的询问，我们左右 $K$ 之内用暴力统计，中间就是求一个区间内每个点为中心的长度不超过 $K$ 的回文串个数，该问题可以用线段树维护。因为修改是将区间推平，那么左右 $K$ 个位置的长度不超过 $K$ 的贡献用暴力统计，中心的值全部推平成一个定值。时间复杂度 $O(mK^2+m\log n)$ ，用 $manachar$ 可以优化到 $O(mK\log n)$ 。

$Sum:$

T3.优化 (inaugurate)

$Des:$ 给定一个长度为 $n$ 的序列 $a_i$ ，接下来 $m$ 次询问：将在区间 $[l,r]$ 选出恰好 $k$ 段不交的连续子序列，求这些序列之和的最大值。($n,m\le 1e5,a_i\le 1e4$)

$Sol:$

$Sum:$

3.29 lk3

T1.前缀 (prefix)

$Des:$ 给定一个大小为 $n$ 个非空字符串集合 $ S={S_1,S_2…S_n } $ ，考虑一个 $m$ 个非空字符串组成的集合 $P={P_1,P_2,…,P_m}$ 将 $S$ 根据 $P$ 作为前缀分割成互相不交的集合。($n,m\le 2000$)

$Sol:$ 按字典序排序，然后做 $dp$ ，由于转移固定，所以时间复杂度 $O(n^2)$ 。建字典树乱 $dp$ 也可过。

$Sum:$

T2.快速排序 (qsort)

$Des:$ 给定 $n$ 个随机种子，求对 $n$ 的排序进行快排时每次递归区间之和的最大值，特别的，若某次随机种子出的结果超过区间返回值为 $0$ 。($n\le 50$)

$Sol:$ 由于每次排序的区间必须包括这区间所以值，所以可以设计区间 $dp$ （记忆化搜索）

​ \(f[i][j][k][l]=\max(f[i][p-1][q][l+1]+f[p+1][j][k-q-1][l+1+1])+j-i\)

$Sum:$

T3.果实摘取 (garden)

$Des:$ 给定一个二维平面，横纵坐标绝对值在 $n$ 以内的所有整点有树，初始时，朝向 $(1,0)$ ，每次将逆时针能看到的一排树全部拔掉，并继续进行该操作。求最后被拔掉的树的坐标。($n,k\le 1e5$)

$Sol:$ 关于约瑟夫环问题，一个简单的递推式 $ j(n)=(j(n-1)-1+K)\%i+1 $ （$i$ 为当前状态的数量），可以优化到 $O(K)$ 。然后二分斜率，使用容斥求解即可。时间复杂度 $O(n\log n\ln n)$ 。

$Sum:$ 考场上被约瑟夫问题折磨了，一直没想明白。二分斜率也是真的折磨。

3.30 lk4

T1.字符串 (string)

$Des:$ 给定一个字符串 $s$ ，接下来进行 $n$ 次操作，每次选择两个整数 $[l_i,r_i]$ ，将 $[l_i,r_i]$ 区间所有奇数下标字符取出来再把偶数下标字符取出来，依次插入 $r_i$ 后，求最后字符串的前 $k$ 位。($n\le 5000,k\le3e6$)

$Sol:$ 可以发现最终答案涉及到的字符可能并不多，所以我们考虑将操作反过来考虑，然后用平衡树模拟这个过程即可。时间复杂度 $O(n\log k+k\log k)$ ，这个复杂度是卡不满的，特别是后面的 $O(k\log k)$ 几乎就是 $O(k)$。

$Sum:$ 由于我忘记了 $string$ 的函数，导致我被迫写平衡树。

T2.机器人 (robot)

$Des:$ $nn$ 的网格中有 $2n$ 个垃圾，而在边缘有 $2*n$ 个机器人（$(0,1),(0,2)…(0,n)$ 以及 $(1,0),(2,0)…(n,0)$） ，当我们使用一个机器人时，那个机器人会选择它正对的方向上第一个垃圾捡起。求随机某一使用机器人的顺序，能将垃圾捡完的概率。($n\le 1e5$)

$Sol:$ 由于一个垃圾只能被两个机器人捡起，所以我们考虑按照垃圾将两个边缘上的点连接起来。这个相当于一个二分图，而由于网格图的性质，我们要有解，那么答案必然是基环树森林，各个基环树之间互不影响，我们分开考虑。对于每一个基环树，我们钦定其为基环外向树，边的指向为该边的归属，显然，一个基环树只有两个方向，加和即可。而当我们钦定边的指向后，我们需要求解满足该条件的答案数，由于我们钦定的边之间存在一定的拓扑关系，同时一些边之间又是相互独立的，所以我们将其按照点值分开再做 $dp$ 求方案即可。时间复杂度 $O(n)$ 。

$Sum:$ 考场上建出二分图之后就没有深入挖掘其性质了，导致完全没做出来。

T3.欧几里得 (gcd)

$Des:$ 设 $f(a,b)$ 表示 $(a,b)$ 进行辗转相除法的次数，接下来 $T$ 组询问，每次询问一个 $tp,x,y$ ，若 $tp=1$ ，询问 $a\le x,b\le y$ 中 $f(a,b)$ 的最大值以及个数；若 $tp=2$ ，询问 $a\le x,b\le y$ 中 $f(a,b)$ 能作为某种第一问的最大值的个数。($x,y\le 1e18,T\le 1e5$)

$Sol:$ 显然，最大值跟 $ fib$ 数列有关，而我们规定能产生贡献的点为好点对，而生成这些点对的点对为极好点对，可以发现，当最大值为 $k$ 时有 $k+1$ 个极好点对，而这些点对的生成关系为：对于第 $k$ 级，$k-1$ 个按照 $fib$ 数列递增，第 $k$ （$fib$ 数列的那个）个极好点对按照常规生成一个 $k+1$ 级极好点对后，再按照二倍的后一个值加上前一个值生成一个 $k+1$ 级极好点对。预处理出这些极好点对，然后对于每组询问求即可。时间复杂度 $O(T\log V)$ 以及 $O(T\log^2 V)$ 。

$Sum:$ 极其离谱的打表题。

3.31 纪中

T1.续命大战(extension)

$Des:$ 有 $n$ 个砖块，长度为 $i$ 的砖块有 $a[i]$ ，接下来双方进行博弈，每个人选择一个操作进行：1.选一个长度，将其删去长度个数个砖块（若不足就只删去一个）；2.选择一个砖块，将其分成长度之和等于它的两个砖块(保证其中有一个为奇数)，求判断先手/后手必胜。($n\le 1e6$)

$Sol:$ 首先，观察长度全为偶数，我们只需要考虑它其砖块数的奇偶即可(若先手进行删去操作，则后手可以通过同样的操作，不改变其奇偶，而若进行拆分操作，则长度为奇数的砖块奇偶不变，而后手依然进行同样操作即可)；若只有奇数，我们考虑其 $\% (x+1)$ ，若余 $n$ 则 $SG=2$ ，反之由其奇偶决定其 $SG$，各个游戏的 $SG$ 异或即可（各个游戏之间独立），再与偶数游戏的 $SG$ 异或。

$Sum:$

T2.树精(tree)

$Des:$ 一个大小为 $n$ 的树，接下来 $m$ 次操作：1.$x\ y$ ，将 $x$ 父亲边 $(x,fa_x)$ 删掉，并连边 $(x,y)$ ；2.$x$ ，将 $x$ 的所有儿子的儿子与其父亲断边，并与 $x$ 相连；3. $x$ ，将根换为 $x$ 。求每次操作之后，所有子树大小之和。($n,m\le3e5$)

$Sol:$

$Sum:$

T3.松活弹抖闪电鞭（eeswes）

$Des:$ 求 $\displaystyle \sum_{i}^n\sum_{j}^n\sum_{k}^n\phi(ij)\mu(ik)\sigma(jk) $ ，答案对 $998244353$ 取模。($n\le 50000$)

$Sol:$

$Sum:$ 化式子后再建出图求其中的三元环。

4.1 lk

T1.最小生成链 (msc)

$Des:$ 一个 $n$ 个点的完全图，求其生成链中最小的，这里的权值定义为一条链相邻两个点权值的异或和的最大值。($n\le2e5,a_i\le2^{60}$)

$Sol:$ 显然，由于是完全图且求生成链，那么本题就跟图论没有关系了。这是一个序列上的问题，而最大值一定由最高位不同（若最高位相同就顺延）的两个数贡献，建两颗子典树，然后在字典树上跑就可以了。时间复杂度 $O(n\log V)$ 。

$Sum:$

T2.穿越 (across)

$Des:$ $n+1$ 个点（编号从 $0$ 到 $n$），每个点有一条连向 $0$ 的边，还有另外一条连向非 $0$ 的边，求走 $m$ 次最终走回自己的方案数。($n,m\le 1e6$)

$Sol:$ 先不考虑连向 $0$ 的边，那么原图就是个基环树森林，再判定一下当前能否回到自己。接下来再考虑 $0$ 边，我们会发现只有一个基环树会被考虑进去，我们把这个基环树拉出来，然后考虑贡献。可以发现，对于从 $0$ 点走 $i$ 步的贡献相当于从 $0$ 点走出去 $m-i$ 步，然后在每个位置贡献一次自己当前的值，而第 $i$ 轮的值是 $2^i$ 。在环的序列上挂一个 $tag$ 即可，时间复杂度 $O(n+m)$ 。

$Sum:$

T3.树统计 (count)

$Des:$ 一个大小为 $n$ 的树，以 $1$ 为根，每个点有点权 $m$ 次操作，每次修改一个点的点权，求每次修改后的树，能否通过若干变换使所有的点权非负，这里的变换指将 $u$ 的父亲节点减去一个正整数 $w$ ，再给 $u$ 加上 $w$ 。$(n,m\le 1e5)$

$Sol:$ 我们设 $f[i]$ 表示它需要向上借多少值，列出转移式然后用动态 $dp$ 求即可。时间复杂度 $O(n\log n)$ 。

$Sum:$

4.2 Yukikaze

T1.big fun of HSY (table)

$Des:$ 给出一个 $n*n$ 的矩阵，求是否存在每行每列以及所有斜线个数为 $3$ 倍数的对角线中 $1,2,3$ 出现次数全相同，若存在，输出方案。($n\le 2000$)

$Sol:$ 可以证明 $n=9*k$ 时才能有解，且可以容易构造。

$Sum:$

T2.怎样更有力气 (run)

$Des:$ $n$ 个人在数轴上有一个坐标，初始速度为 $0$ ，接下来进行 $m$ 次事件：1.某个时刻将某个人的速度改为 $k$ ；2.询问某个时刻离原点最远的点的距离。（时间不降给出）($n\le 1e5,m\le 5e5,t\le 1e9$)

$Sol:$ 维护李超树即可，时间复杂度 $O(n\log^2 n+m\log n)$ 。

$Sum:$

T3.机器人大赛 (robot)

$Des:$ $n$ 个点的树，给出 $m$ 个条件，$u$ 到 $v$ 的路径上两两之间可以连边且边权为 $w$ ，接下来 $k$ 条限制表示 $u$ 和 $v$ 不能相连，求将所有点连通的最小费用。($n,m\le3e5$)

$Sol:$

$Sum:$

4.3 省选模拟

T1.隔离 (isolation)

$Des:$ $n$ 个城市位置 $(x_i,y_i)$ ，$m$ 条道路连接城市 $(u_i,v_i)$ 保证道路之间在城市之外的不存在交点，接下来 $q$ 次询问，每次询问一个矩形区域有多少个连通块(仅靠矩阵中的点和边构成的连通块)。($n,q\le1e5$)

$Sol:$ 由于题目给出的是平面图，而平面图的结论：点数-边数+面数=连通块个数，面数先用极角排序全部求出，再用四维排序求即可。

$Sum:$

T2.匹配 (match)

$Des:$ 给定 $a_i$，对于所有 $n-1$ 的排列 $p$ ，求 $ \displaystyle sgn(p)\prod_{i=0}^{n-1}a_{i\&p_i} $ 之和，这里的 $sgn(p)$ 定义为将 $p$ 变为升序的最少交换相邻位置次数。答案对 $998244353$ 取模。($n\le 3e5$)

$Sol:$ 首先，这个东西显然就是个行列式，然后我们观察这个行列式，发现答案的贡献就是 $FMT$ ，直接做 $FMT$ 即可，时间复杂度 $O(n\log n)$ 。

$Sum:$

T3.氪金手游 (arknights)

$Des:$ 给出 $p_i,w_i$ ，定义 $ \displaystyle f(l,r)=w(x)*\prod_{i=l}^{r}(1-p_i+p_ix) $ ，求对于所有的 $k=1,2…n$ ，$ \displaystyle \sum_{i=1}^kf(i,k) $ 。答案对 $998244353$ 取模。($n\le 1e5$)

$Sol:$ 由于两个向量的点乘结果等于减法卷积后的常数项，分治求出待求一次函数的后缀积和后缀和，可以发现他们可以互相转化，接下来就是分治做减法卷积，时间复杂度 $O(n\log^2n)$。

$Sum:$

4.4 P_Y_Y

T1.泡沫 (bubble)

$Des:$ $n$ 个值 $a_i$ ，将其连成一棵树，边权为 $a_i⊕ a_j$ ，求最小的权值。($n\le2e5,a_i\le 2^{30}$)

$Sol:$ 分治建 $01trie$ 然后合并即可。时间复杂度 $O(n\log^2n)$ 。

$Sum:$

T2.芒种 (grain)

​ 假设我们当前右端点从 $r$ 移动到了 $r+1$ ，那么我们就要在线段树上包含 $[1,r]$ 的所有区间进行修改。在线段树上进行修改的时候，我们每次优先进入右儿子，若左儿子被插入节点更新后没有右儿子更新后的结果优秀，那么我们就不进入左儿子。考虑这么做为什么是对的，由于我们每次的询问一定是一个后缀，若一个询问包含线段树上某个区间的左儿子，其必然包含右儿子，那么我们在询问的时候也一定会询问到右儿子，这个时候再更新左儿子更底层的答案显得格外多余。

​ 考虑这么做的时间复杂度，由于每次插入一个点，其在线段树上每个包含它的区间刚好插入其前驱和后继之间，所以一定使值域减半。所以总的时间复杂度是 $O(n\log^2n)$ .

$Sum:$ 本题提供了一个非常好的思路：把单点询问拆成区间询问，并在区间修改时根据性质减少修改。

T3.小跳蛙 (leapfrog)

$Des:$ $n$ 个点构成一棵树，给定 $1$ 号点的点权 $x$，定义一个合法方案为：将树含根划分为一个连通块，该连通块中父亲节点的点权大于等于其儿子点权之和。求方案数，答案对 $998244353$ 取模。($n\le 1e5,x\le 1e9$)

$Sol:$ 我们将每个点和其儿子差分，$x$ 的限制就消失了，问题就转化为把树拆成大小为 $i$ 的连通块大小个数。重剖，链上用分治 $FFT$ ，时间复杂度 $O(n\log^3n)$ 。

$Sum:$

4.5 xzx34

T1.矩阵 (flow)

$Des:$ 给定一个 $n*n$ 的矩阵，在其中填 $[1,K]$ 中的数，要求每行每列的最小值为 $1$ 。($n\le1e5,K\le1e9$)

$Sol:$ 分析题目给出的限制条件：每行每列的最小值为 $1$ 。由于同时涉及到行列，就不太好用正常的方式来描述该限制条件。那么，我们就来思考一下比较暴力的想法：或卷积。

​ 对于 $n$ 很小的时候，首先我们将逐行拆开成 $n$ 个向量，由于每个值的选择只有 $1$ 或者非 $1$ 两种选择，我们不妨设每行的选择情况为 $i$ (一个二进制数)，其中第 $i$ 位为 $1$ 表示在向量中第 $i$ 个位置填上 $1$ ，为 $0$ 则表示填上其他数。那么，我们可以写出它的集合幂级数（卷积定义为或卷积）：

​ \(\displaystyle f(x)=\sum(K-1)^{n-pop(i)} x^i\)

​ 其中 $pop(i)$ 表示二进制数 $i$ 中 $1$ 的个数。有了该式之后，我们将其自卷 $n$ 次后的最高项系数就是答案。具体的，将 $f(x)$ 进行 $FMT$ 后再将每一项都取 $n$ 次幂再 $IFMT$ 回来即可。即（设 $T$ 为最高次项）：

​ \(ans=[x^{T}] f^n(x)\)

​ 但是，当 $n$ 略大的时候，由于该集合幂级数是指数级别增长的，这个做法似乎就裂开了。

​ 其实不然，当我们深入分析该式子后，发现当 $pop(i)$ 相同的项其系数也相同，那么我们就不必将各个项分开考虑，只需按 $pop(i)$ 分类即可。 重新分好类之后，我们还得考虑在当前情况下如何做 $FMT$ ，根据或卷积的 $FMT$ 的定义（即 $\hat f(x)$ 为 $f(x)$ 莫比乌斯变换之后的结果）：

​ \(\displaystyle \hat f(x)=\sum_{T}\sum_{S\subseteq T} [x^{S}]f(x) x^{T}\)

​ 我们同理可以得到幂次定义为 $pop(i)$ 的多项式类似的进行 $FMT$ 的结果：

​ \(\displaystyle \hat f(x)=\sum _i \sum_{j=1}^i \binom{i}{j}(K-1)^{n-j} x^i\)

​ 你也许想对其做卷积，但是模数 $1e9+7$ 要写任意模就会把我们劝退。事实上，后式就是个二项式定理的形式，简单化一下式子就可得到：

​ \(\displaystyle \hat f(x)=\sum_i (K-1)^n*((\frac{K}{K-1})^i-1) x^i\)

​ 将每一项系数取 $n$ 次幂后就得考虑如何做 $IFMT$ 变回来，不过剩下的工作和以上基本相同。还是先给出 $IFMT$ 的定义：

​ 由于我们只需要求最高次项系数，即 $pop(i)=n$ 的情况，以下也就只给出第 $n$ 位做 $IFMT$ 后的结果：

​ \(\displaystyle ans=\sum_{i=1}^n \binom{n}{i} (-1)^{n-i} [x^i]\hat f(x)\)

​ 各部分时间复杂度基本都是 $O(n)$ ，仅自乘处复杂度为 $O(n\log n)$ ，所以总时间复杂度 $O(n\log n)$ 。

$Sum:$ 考场上推出该式子后只有不到 $20 min$ ，当时太过慌张，没有写清楚。

T2.计数 (fwt)

$Des:$ $4$ 维大小为 $m$ 的空间中有 $n$ 个点，点有点权，求权值最大的一条满足偏序关系的链，以及链的方案数。($n\le1e5,m\le1e9$)

$Sol:$ 4维偏序。

$Sum:$

T3.贪吃的老鼠 (travel)

$Des:$ $n$ 个大小为 $p_i$ 的奶酪，有 $m$ 只老鼠，其中第 $i$ 只老鼠吃奶酪的速度为 $s_i$ ，任意一个时刻，一只老鼠最多吃一个奶酪，且一个奶酪最多被一只老鼠吃。求给每个奶酪最少都增加多少才能吃掉所有奶酪。($n,m\le 30,p_i\le 1e5$)

$Sol:$ 二分是不用说的，将每段时间分开考虑这也是显然需要的。接下来就是考虑建图，根据朴素的网络流建图，我们无法描述每段时间中某小段时间被不同的老鼠吃的情况。我们考虑使用差分来弥补这个不足，当我们将各只老鼠的速度差分之后，现在每次流出来的情况就可以被描述为选择多个老鼠。具体的，源点向每个奶酪连权值为 $p_i$ 的边，每个奶酪再想每个时间点老鼠差分点连边。二分判断是否合法即可。

$Sum:$ 非常经典的差分网络流建图方式。

4.6 lk

T1.石头剪刀布 (rps)

$Des:$ 给出 $n$ 个长度为 $K$ 的字符串，字符串仅由 $RPS$ 组成，分别表示石头剪刀布，若两个字符串以任何任意起点作为开始进行 $K$ 轮石头剪刀布的胜负情况完全相同，则在代表这两个字符串的点之间连边。求最终图的团个数。($n\le 1e5,K\le 18$)

$Sol:$ 类似于石家庄的工人阶级比较坚强那题，看到石头剪刀布，我们首先想到三次单位根。看到循环比较，我们首先想到循环卷积。想到循环卷积，我们就会想到 $DFT$ ，而 $DFT$ 的本质就是带入点值，而要求循环比较结果相同，就要两个多项式 $DFT$ 点乘后除常数项其余全部为 $0$。至于团的求法就是看是否全部连边。根据以上思考，我们可以使用状压 $dp$ （不为 $0$ 记为 $1$）来求团。时间复杂度 $O(3^n)$ 或写子集卷积 $O(n^2 2^n)$。

$Sum:$ 很好的一道思维题，不局限于常规的思路，要求我们发散思维。考虑大家对单位根、$DFT$ 本质的思考。

T2.序排速快 (tros)

$Des:$ 给定一个 $n$ ，定义 $n$ 的一个排列 $p$ 中的分割点为：任意在该点前面的数都小于在该点后面的数。规定快速排序为：每次判定是否存在分割点，1.若存在则按照分割点将排列分割开，递归做每一个部分，直到有序；2.若不存在分割点，则进行一次冒泡排序，并产生当前排列大小的贡献。求对于 $n$ 的所有排列，其贡献之和，答案对 $998244353$ 取模。($n\le 1e7$)

$Sol:$ 题目给出了令人眼花缭乱的操作方式，在这样的描述下实在是不好按照题目给出的贡献方式计数贡献，那么，我们就考虑转化贡献形式。由于每次贡献为一次冒泡的排列大小，这等价于排列中每个值在本次冒泡中贡献了 $1$ ，而当一段区间排序好了它就不会再进行冒泡了，也即它就不会再进行冒泡排序了，同时在它结束冒泡排序之前它每次冒泡排序都参与了。所以我们的问题就转化为了求每个点它停止冒泡排序的时间。

​ 一个点停止排序当且仅当它且它前一位成为分界点。该值依旧不好直接求的，我们需要重定义计数方式实现二次转化。当一个点成为分界点，就说明小于等于它的数全部在它左边了。那么，我们定义 $p_i$ 表示小于等于 $i$ 的最大位置，由于一次冒泡会使其至少移动一位，所以最终每个点的答案形式就形如 $\max(p_{i-1}-(i-1),p_i-i)$ .

​ 我们枚举 $p_i$ ，若 $p_i$ 上的数不是 $i$ ，那么对答案的贡献就是 $p_i-i+1$ ，反之是 $p_i-i$ 。那么，我们就先加上 $p_i-i+1$ 的贡献，再减去那些只有 $1$ 的值。那么最终的答案就是：

​ \(\displaystyle ans=\sum_{i=1}^n\sum_{j=i}^n i!(n-i)!\binom{j-1}{i-1}(j-i+1)-\sum_{i=1}^n\sum_{j=i}^n(i-1)!(n-i)!\binom{j-1}{i-1}\)

​ 该式子通过下降幂裂项相消可得。具体的：

​ \(\displaystyle x^{\underline{n}}=\frac{(x+1)^{\underline {n+1}}-x^{\underline {n+1}}}{n+1}\)

​ 最终可得答案的式子：

​ \(\displaystyle ans=n!(\frac{n^2}{2}+\frac{5n}{2}+1-(n+1)\sum_{i=1}^n\frac{1}{i})-n!\sum_{i=1}^{n}\frac{1}{i}\)

$Sum:$ 考场上花了 $4h$ 做没有意义的 $dp$ ，最后几分钟才想到要转化贡献，可惜时间已经来不及了。但是事实上，本题不仅需要我们第一步的贡献转化，还有再次重定义贡献的计数。

T3.矩阵填数 (matrix)

$Des:$ $n*m$ 的矩阵中，边界位置已经填了数，其他位置未填数（部分位置不用填数），求填完数后，矩阵相邻数之差的绝对值之和的最小值。($n,m\le 150$)

$Sum:$ 本题还可以线规对偶做最大费用流。

4.7 lk

T1.自古枪兵幸运 E (luckye)

$Des:$ 权值为 $1$ 的物品 $n$ 种，权值为 $2$ 的物品 $m$ 种，每种物品能使用无限次，求权值和为 $k$ 的一堆物品有多少种情况，答案对 $p$ 取模。($n,m\le 1e5,K\le 1e12,p\le 1e6,p\in prime$)

$Sol:$ 本题求 $[x^k]\frac{1}{(1-x)^{n+m}(1+x)^m}$ 。可以根据等式：

​ \(\displaystyle \frac{1}{(1-x)^a(1+x)^b}=\sum_{i=1}^a \frac{1}{(1-x)^i}\binom{a+b-i-1}{a-i}\frac{1}{2^{a+b-i}}+\sum_{j=1}^b\frac{1}{(1+x)^i}\binom{a+b-i-1}{b-i}\frac{1}{2^{a+b-i}}\)

​ 或者，观察到本题的 $p$ 不是很大，我们可以考虑使用 $lucas$ 定理。不过由于我们存在两条限制，所以这里使用 $lucas$ 定理的时候还得考虑再分类。时间复杂度 $O((n+m)\log _pK)$ 。

$Sum:$

T2.使者 (emissary)

$Des:$ 给出一棵大小为 $n$ 的树，树上存在一些特殊边，接下来 $m$ 次操作：1.加入特殊边 $(u,v)$ ；2.删除特殊边 $(u,v)$ ；3.询问 $(u,v)$ 不通过树上的简单路径上的边到达的方案数。($n\le 1e5,m\le 1e5$)

$Sol:$ 观察询问的统计形式：1.子树对另一颗子树的贡献；2.子树对另一个子树外区间的贡献。而子树和子树外两种区间可以在 $dfn$ 序上用连续的区间来描述。所以我们考虑将原问题转到 $dfn$ 序上，那么，问题就变成了：1.插入单点对单点的贡献；2.询问区间对区间的贡献。使用二维线段树维护即可。时间复杂度 $O(n\log ^2 n)$ ，空间复杂度 $O(n\log ^2n)$。

$Sum:$ 这道题还算是一道比较经典的 $dfn$ 序问题题。

T3.和谐宇宙 (terrorist)

$Des:$ $n$ 个点的树，定义一朵花为：一个点带至少三条到叶节点的不交链，定义权值为花上点之积。求原图选一个和两个花的权值之和。($n\le 1e5$)

$Sol:$

$Sum:$ 大换根题。