3月杂题选做（part 2）

上回说到：Part 1

关于难度

\(\color{gray}\bigstar\) 可以秒杀的题。

\(\color{green}\bigstar\) 思考一会儿后可以秒的题。

\(\color{blue}\bigstar\) 需要较长时间思考的题。

\(\color{Gold}\bigstar\) 看题解、稍加指点就会做的题。

\(\color{red}\bigstar\) 看题解后需要较长时间消化，甚至现在都没有完全理解的题。

本月主要板刷 cf *2300~*2400 的题。

~~一些简单的 DS 题就直接嘴巴了。~~

由于博客过长会导致 markdown 加载缓慢，所以源码长度超过 \(1000\) 行时进行分 P 处理。

[JSOI2011]分特产 \(\color{CornflowerBlue} {提高+/省选-}\) \(\color{green}\bigstar\)

有 \(n\) 种物品，第 \(i\) 种物品有 \(a_i\) 个，现在需要分给 \(m\) 个人，要求每个人至少分到一样东西，求方案数，对 \(10^9+7\) 取模。
\(n,m,a_i\le 1000\)。

标签：组合数学，容斥。

每个人至少分到一个，这个条件比较难搞，考虑容斥，把这个条件去掉。

枚举有多少人没有分到任何东西，答案就是：

\[\sum_{i=0}^{m-1} (-1)^i C_m^i\prod_{j=1}^n C_{a_j+m-i-1}^{m-i+1} \]

code

CF1228E *2300 \(\color{green}\bigstar\)

给定一个 \(n\times n\) 的矩阵，用 \(1...k\) 的数填充，使得每行每列最小值均为 \(1\)，问有多少填法，答案对 \(10^9+7\) 取模。
\(n\le 250,k\le 10^9\)。

标签：容斥。

考虑容斥一下，枚举 \(i\) 行 \(j\) 列没有一个 \(1\)，然后就可以直接算了。

和上面的题差不多，不细讲。

时间复杂度 \(O(n^2)\)。

容斥时一定要记得加上组合数，比如该题中 \(C_n^iC_n^j\)。

code

好像有 \(O(n\log n)\) 的容斥做法，不大会。

CF1117D *2100 \(\color{gray}\bigstar\)

有一个长度为 \(n\) 的串，开始都是 \(0\)，每次选择一个都为 \(0\) 的长度为 \(m\) 的空串，把这些位置都变成 \(1\)，问最后又多少种不同的序列，对 \(10^9+7\) 取模。
\(n\le 10^{18},m\le 100\)。

标签：矩阵乘法，dp。

显然可以设 \(f_i\) 表示 \(1..i\) 的方案数，分情况讨论，得到转移式：

\[f_i=f_{i-1}+f_{i-m} \]

显然矩阵快速幂优化一下，时间复杂度 \(O(m^3\log n)\)。

CF1182E *2300 \(\color{green}\bigstar\)

已知 \(f_1,f_2,f_3,c\)，当 \(i\ge 4\) 时，\(f_i=c^{2i-6}f_{i-1}f_{i-2}f_{i-3}\)，求 \(f_n\)，答案对 \(10^9+7\) 取模。
\(n\le 10^{18}\)

标签：矩阵乘法。

这东西一眼矩阵快速幂，但是都是乘法，矩阵快速幂只能支持加法。

设答案为 \(f_1^{a_1}f_2^{a_2}f_3^{a_3}c^{a_4}\)，只需要求出这些指数就可以算出答案了。

这些指数又满足加的条件，所以矩阵快速幂维护就好了。

一起维护比较困难，分开维护每一个，然后就做完了。

code

P6835 \(\color{CornflowerBlue} {提高+/省选-}\) \(\color{blue}\bigstar\)

有一条链，\(i\) 向 \(i+1\) 连边，此外还有 \(m\) 条返祖边，\(x\) 连向 \(y(x\ge y)\)，在每个点随机选择一条出边走，求从 \(1\) 走到 \(n+1\) 的期望步数。
\(n\le 10^6\)

标签：期望，dp。

期望入门题，虽然我推了好久。

设 \(f_{x,y}\) 表示 \(x\) 走到 \(y\) 的期望步数。

\[f_{x,y}=\sum_{i=x}^{y-1}f_{i,i+1} \]

所以只需要算每一步就好了。

\[f_{x,x+1}=1+\frac{1}{d}\sum (f_{y,x}+f_{x,x+1})\\ \frac{1}{d}f_{x,x+1}=1+\frac{1}{d}\sum f_{y,x}\\ f_{x,x+1}=d+\sum f_{y,x} \]

\(d\) 表示出度，所以直接算出每一步的期望，后面的 \(f_{y,x}\) 可以直接前缀和一下查询。

code

CF1139D *2300 \(\color{blue}\bigstar\)

给一个数列，每次随机选一个 \(1\) 到 \(m\) 之间的数加在数列末尾，数列中所有数的 \(\gcd=1\) 时停止，求期望长度。
\(m\le 10^5\)

标签：莫反，dp，期望。

推式子好题。

首先设 \(f_i\) 表示当前 \(\gcd=i\)，后面的期望长度。

\[f_i=1+\frac{1}{m}\sum_{j=1}^m f_{\gcd(j,i)} \]

这个可以根据期望显然得到。

换成枚举 \(\gcd(j,i)\)。

\[f_i=1+\frac{1}{m} \sum_{d|i} f_d \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} [\gcd(j,\frac{i}{d})==1] \]

右边的式子莫反一下。

\[f_i=1+\frac{1}{m} \sum_{d|i} f_d \sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{p|\gcd(j,\frac{i}{d})} \mu(p) \]

把 \(p\) 放前面来，得到

\[f_i=1+\frac{1}{m}\sum_{d|i} f_d \sum_{p|\frac{i}{d}} \mu(p) \left \lfloor \frac{m}{dp} \right \rfloor \]

预处理 \(\mu\) 后暴力做，时间复杂度 \(O(n\log^2 n)\)，就做完了。

code

看了题解，发现还可以继续推。

设 \(T=dp\)。

\[f_i=1+\frac{1}{m}\sum_{d|i} f_d \sum_{p|\frac{i}{d}} \mu(p) \left \lfloor \frac{m}{T} \right \rfloor \]

把 \(T\) 扔前面。

\[f_i=1+\frac{1}{m}\sum_{T|i}\left \lfloor \frac{m}{T} \right \rfloor \sum_{d|T} f_d \mu(\frac{T}{d}) \]

设 \(F(T)=\sum_{d|T} f_d \mu(\frac{T}{d})\)。

\[f_i=1+\frac{1}{m}\sum_{T|i}\left \lfloor \frac{m}{T} \right \rfloor F(T) \]

\(F(T)\)，可以在 dp 的过程中处理，复杂度是调和级数 \(O(n\log n)\)，所以总时间复杂度 \(O(n\log n)\)。

code

巨佬 George1123 有很强的 \(O(m)\) 做法，根本不会。

P6810 \(\color{CornflowerBlue}{提高+/省选-}\) \(\color{gray}\bigstar\)

已知 \(n,m\)，求

\[\sum_{i=1}^n \sum_{j=1}^m d(i)d(j)d(\gcd(i,j)) \]

\(d(i)\) 表示 \(i\) 的约数个数。
\(n,m\le 2\times 10^6\)。

标签：数学。

简单题，显然枚举一下 \(\gcd(i,j)\) 的约数，然后预处理一下 \(d\)，直接暴力就好了。

时间复杂度 \(O(n\log n)\)。

code

CF1332E *2100 \(\color{blue}\bigstar\)

有一个 \(n\times m\) 的矩阵，\((i,j)\) 有数 \(a_{i,j}\)，每次操作可以让一个 \(a_{i,j}\) 加二，也可以把两个相邻的数同时加一，问有多少中不同的矩阵满足 \(a_{i,j}\in [L,R]\)，且可以通过若干次操作使得所有 \(a_{i,j}\) 相同，答案对 \(998244353\) 取模。
\(n,m,L,R\le 10^9\)

标签：数学，二项式定理。

其实这题也不是特别难。

考虑每次操作，\(\sum a_{i,j}\) 的奇偶性是不变的，并且可以发现由于可以无限次操作，所以可以操作到任意和的奇偶性相同的局面。

考虑如果 \(n\times m\) 是奇数，那么最后状态的和可以是奇数也可以是偶数，所以必然有解，答案就是 \((R-L+1)^{n=m}\)。

考虑如果 \(n\times m\) 是偶数，状态要满足奇数、偶数的个数都是偶数。

设 \([L,R]\) 区间中有 \(X\) 个奇数，\(Y\) 个偶数。

那么答案的式子就是

\[\sum_{i=0}^{\frac{nm}{2}} C_{nm}^{2i} X^{2i}Y^{nm-2i}。 \]

这个东西和二项式定理特别像，只是把奇数项全部去掉而已。

可以发现答案就是 \(\frac{(X+Y)^{nm}+(X-Y)^{nm}}{2}\)，\(X+Y=R-L+1\),\(X-Y\) 只需要判断 \(R-L+1\) 的奇偶性就好了。

code

注意不要使用欧拉定理，因为指数取模后可能出现 \(0^0\) 情况，快速幂的结果是 \(1\)，但应该是 \(0\)。

P4247 \(\color{black} {NOI/NOI+/CTSC}\) \(\color{green}\bigstar\)

有一个长度为 \(n\) 的序列，有三个操作：
I a b c 表示将 \([a,b]\) 这一段区间的元素集体增加 \(c\)。
R a b 表示将 \([a,b]\)区间内所有元素变成相反数。
Q a b c 表示询问 \([a,b]\) 这一段区间中选择 \(c\) 个数相乘的所有方案的和 \(\mod 19940417\) 的值。
\(n,q\le 50000,c\le 20\)。

标签：线段树。

这题真不难，不知道为啥是黑。

\(c\) 很小，~~适合暴力~~。

每个节点暴力开 \(s_i\) 表示选 \(i\) 个数的答案。

合并是一个卷积形式，很简单。

所以 R 操作和 Q 操作解决了，考虑区间加。

假设原来选的是 \(x_1x_2...x_k\)。

变成 \((x_1+c)(x_2+c)...(x_k+c)\)。

拆开，发现是 \(c^i\) 乘上 \(k-i\) 个 \(x\)，考虑 \(s_i\) 对 \(s_j\) 的贡献，实际上就是再选 \(j-i\) 个 \(c\)，组合数算一下就好了。

打标记就和支持加乘的线段树一样。

做完了，但出题人很凉心，模数不是指数，不能 \(O(n)\) 预处理组合数，这个地方我调 \(1h\)。

code

P7394 \(\color{CornflowerBlue} {提高+/省选-}\) \(\color{green}\bigstar\)

有一棵数，每个节点有点权 \(0/1\)，维护 \(3\) 种操作。
1 x 将 \(x\) 位置上的灯打开或关闭（原来如果打开就关闭，否则打开）。
2 x y 询问树上与 \(x\) 相同深度的点中与 \(x\) 结点距离为 \(y\) 的点中开着的灯的个数。
3 x 回到第 \(x\) 次事件发生之后的状态。

标签：主席树，dfs序。

挺简单的。

考虑 \(dis(i,j)=dep_i+dep_j-2\times dep_{LCA(i,j)}\)。

由于 \(i,j\) 深度相同，所以可以得到 \(LCA\) 是哪个点。

问题转化为查询 LCA 子树下，不与 \(x\) 在一棵子树的，深度与 \(x\) 相同点的个数。

dfs 序再线段树乱维护就好了，可持久化的话可以离线做也可以直接主席树。

code

CF1523E *2600 \(\color{blue}\bigstar\)

有 \(n\) 个台灯初始时都是暗的，每次等概率随机一个暗台灯将其点亮，若点亮后存在一个长度为 \(k\) 的连续段有大于一个台灯被点亮则立刻停止，求期望点亮多少台灯。答案对 \(10^9+7\) 取模。

标签：数学，期望。

*2600 ？？？

考虑经典转化，因为算恰好 \(i\) 个灯不合法的方案难算，所以算放 \(i\) 个灯依然合法的方案，这个组合数随便算。

答案相当于求个和就好了。

code

P2447 \(\color{CornflowerBlue} {提高+/省选-}\) \(\color{green}\bigstar\)

已知 \(m\) 个线性异或方程，问至少使用前多少个方程可以解出每个未知数的答案。

标签：高斯消元。

直接做高斯消元，答案就是使用的方程中编号最大的。

\(O(n^3)\) 过不了，用 bitset 优化一下。

code

P6478 \(\color{purple}{省选/NOI-}\) \(\color{Gold}\bigstar\)

题比较长，自己看。

标签：二项式反演，树上背包。

新科技，二项式反演。

题目中恰好非常难搞，考虑转化成大于等于。

假设 \(f_k,g_k\) 分别表示恰好 \(k\) 组匹配与至少 \(k\) 组匹配的方案。

\[g_k=\sum_{i=k}^n \binom{k}{i} f_i \]

反演一下

\[f_k=\sum_{i=k}^n \binom{k}{i}(-1)^{i-k}g_i \]

\(f_k\) 是答案， \(g_k\) 可以直接用树上背包做。

设 \(dp_{i,j}\) 表示以 \(i\) 为根的子树中匹配了 \(j\) 组的方案数。

直接合并，然后考虑一下 \(i\) 的情况就好了。

code

P2664 \(\color{black} {NOI/NOI+/CTSC}\) \(\color{green}\bigstar\)

lrb 有一棵树，树的每个节点有个颜色。给一个长度为 \(n\) 的颜色序列，定义 \(s(i,j)\) 为 \(i\) 到 \(j\) 的颜色数量。以及

\[sum_i=\sum_{j=1}^n s(i, j) \]

现在他想让你求出所有的 \(sum_i\)。

标签：dfs序。

如果直接考虑计数不是很好做，考虑反过来，考虑每个颜色对答案的贡献。

把一个颜色单独拿出来，然后考虑中间的贡献。

像下面这样：

直接考虑中间这个红色区域，贡献很好算，就是上面的加上下面子树的。

时间复杂度 \(O(n)\)。

然后就做完了，不知道为啥要淀粉质。

code

CF718C *2300 \(\color{gray}\bigstar\)

在本题中，我们用 \(f_i\) 来表示第 \(i\) 个斐波那契数（\(f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge 3)\)。
给定一个 \(n\) 个数的序列 \(a\)。有 \(m\) 次操作，操作有两种：
将 \(a_l\sim a_r\) 加上 \(x\)。
求 \(\displaystyle\left(\sum_{i=l}^r f_{a_i}\right)\bmod (10^9+7)\)。
\(n,m\le 10^9\)。

标签：线段树，矩阵乘法。

简单题。

CF633H 的弱化版，直接线段树维护矩阵，没了。

CF1175F *2500 \(\color{Gold}\bigstar\)

给定数组 \(a_1,a_2 \cdots a_n\)，若子序列\(a_l,a_{l+1}\cdots a_{r}\) 满足 \(1,2\cdots r-l+1\) 所有整数各出现一次，则称其为这个数组的一个子排列。求这个数组子排列个数。

标签：分治。

随便一个 *2500 都不会，我退役罢\kk。

考虑一个子排列需要满足：

最大值是 \(r-l+1\)。
没有重复的数。

考虑分治，只需要看经过分治中心 \(mid\) 的方案数。

这个比较难搞，我们可以钦定 \(mid\) 是 \(l...r\) 最大值，这样保证 \(a_{mid}\) 是最大值，也就知道了 \(r-l+1\)。

双指针扫一遍，用 st 表查询，没了。

code

CF1637F *2500 \(\color{Gold}\bigstar\)

给定一棵 \(n\) 个结点的树，第 \(i\) 个点有一高度 \(h_i\) 。你可以在任意一些结点上建信号塔，高度随意。结点 \(i\) 有信号且当 \(i\) 在 \(u,v\) 的路径上，\(u,v\) 分别有两座信号塔 \(e_u,e_v\) ，满足 \(\min(e_u, e_v) \ge h_i\) 。建高度为 \(x\) 的信号塔花 \(x\) 元，问最少得花多少钱使得所有结点都能有信号。

标签：贪心，dp。

首先一个显然的结论，信号塔必然在叶子上，不然把一个信号塔向下移动可以对更多的点产生贡献。

然后考虑一棵子树对外面的贡献只与该子树中最大的信号塔有关。

所以设 \(f_i\) 表示满足 \(i\) 子树内部后最大的信号塔值。

但这样有个问题，如果想要满足 \(i\) ，可以子树中选两个叶子，也可以外面选一个叶子，内部选一个叶子。

一个巧妙的构造思路是令 \(h_i\) 最大的为根，那么此时最大的信号塔必然在两个不同的子树中，这样可以让满足一个点的最优策略必然是内部选一个点，外部选一个点。

然后就可以直接 dfs 一遍跑 dp 了，如果 \(f_x<h_x\) 则需要把 \(f_x\) 变大，否则不变。

code

CF1585G *2500 \(\color{blue}\bigstar\)

已知一个森林，都是有根树，Alice 和 Bob 轮流操作，每次选择一棵树和一个小于这棵树秩的正整数 \(d\)，然后把这棵树深度小于等于 \(d\) 的节点删去，不能操作者输，问先手是否有必胜策略。

标签：博弈论，SG 函数。

复习一下博弈论。

考虑计算出每个子树的 SG 函数，这样最后的答案就可以直接异或算出。

咋算呢。

考虑暴力就是枚举 \(d\)，那么把深度大于 \(d\) 的子树求个异或和，然后去 mex。

但这炸了，一条链就卡掉了。

考虑优化，实际上很简单，考虑如果一个点只有一个儿子，他的答案显然可以由儿子直接转移。这一部分跑得飞快，均摊一下就没了。

时间复杂度不大会，题解说是 \(n\log n\) 的。

code

ARC101C *2913 \(\color{Gold}\bigstar\)

将给定的包含偶数 \(n\) 个点的树上的点两两配对，使得每对点之间路径的并集包含了每一条树边，求方案数。

显然可以想到容斥，如果当前有 \(i\) 条边没有被覆盖，那么就相当于把树分成 \(i+1\) 个联通块，每个联通块的答案是可以算的，乘起来就好了。

然后就不会了。

考虑树形 dp，设 \(f_{i,j}\) 表示以 \(i\) 为根的子树中，\(i\) 所在的联通块大小为 \(j\)，答案乘上容斥系数的结果。

特别的 \(f_{i,0}\) 表示和父亲之间有一条不合法边的答案。

\(j>0\) 就直接背包。

\(j=0\) 就直接考虑把当前联通块的答案加上再乘 \(-1\)。

答案就是 \(-f_{1,0}\)。

code

ABC181F *2009 \(\color{green}\bigstar\)

已知 \(n\) 个点在平面内第 \(i\) 个点坐标为 \((x_i,y_i),-100\le x_i,y_i\le 100\)。
现在有一个半径为 \(r\) 的圆，开始时在 \((-10^9,0)\) 的位置，像去 \((10^9,0)\)，不能碰到 \(y=100\) 和 \(y=-100\) 两条直线以及每个点。
求 \(r\) 最大值。
\(n\le 100\)。

标签：贪心，最小生成树。

随着 \(r\) 逐渐变大，会有一些两点之间的空隙这个圆无法通过，而如果某时刻左右不连通则圆无法通过。

所以点之间两两连边，在与上下直线连边，没加一条边后看看上下是否连通，类似于最小生成树。

code

CF1310D *2300 \(\color{green}\bigstar\)

\(N\) 个点的图，给你图的邻接矩阵，求从点 \(1\) 出发经过 \(K\) 条边回到点 \(1\)，且路径上没有奇环的最短距离。
\(n\le 80,k\le 10\)。

标签：图论，随机。

数据很小考虑暴力咋做。

直接暴力 \(n^k\)，显然炸。

看到奇环想到二分图，相当于黑白染色后黑白交替走。

由于 \(k\) 很小，假设 \(1\) 是黑点，那么黑点数量只有 \(\frac{k}{2}\)，所以可以暴力枚举黑点，然后就可以直接做了。

时间复杂度 \(O(n^{\frac{k}{2}})\)。

code

还有一个很强的做法，考虑每次随机每个点是白点还是黑点，然后进行一个 \(O(n^2k)\) 的 dp，这样成功地概率很高，而且跑得飞快。

多做几遍就好了。

P8229 \(\color{CornflowerBlue}{提高+/省选-}\) \(\color{blue}\bigstar\)

有一个篮子，开始有一个草莓，每次抛一枚硬币，\(P\) 的概率为正面，篮子中草莓数乘 \(K\)，\(1-P\) 的概率为背面，吃完篮子中所有草莓，然后篮子中自动生成一颗草莓，求抛 \(n\) 次硬币后吃草莓数量的期望值，答案对 \(998244353\) 取模。
\(n\le 10^{18}\)。

标签：数学。

不是很难的数学题，设 \(f_i\) 表示抛 \(i\) 次硬币后篮子中草莓数量的期望，那么答案就是：

\[(1-p)\sum_{i=0}^{n-1}f_i \]

然后可以得到 \(f\) 的递推式：

\[f_i=f_{i-1}\times kp+(1-p) \]

推一下通项，如果你不会推，可以看这里。

得到

\[f_i=(1+\frac{1-p}{kp-1})(kp)^i-\frac{1-p}{kp-1} \]

然后再推一下答案，得到：

\[ans=(1-p)(-\frac{n(1-p)}{kp-1}+(1+\frac{1-p}{kp-1})(\frac{1-(kp)^n}{1-kp})) \]

注意 \(kp\) 可能等于 \(1\) ，此时分母为 \(0\) ，需要特判计算。

code

CF741D *2900 \(\color{Gold}\bigstar\)

一棵根为 \(1\) 的树，每条边上有一个字符（ \(a...v\) 共 \(22\) 种）。一条简单路径被称为 Dokhtar-kosh 当且仅当路径上的字符经过重新排序后可以变成一个回文串。求每个子树中最长的 Dokhtar-kosh 路径的长度。
\(n\le 5\times 10^5\)

标签：dsu on tree。

学习了一下新算法 dsu on tree，发现不是个很难的算法，就不新开一个文章了，借这道题讲一下。

字母只有 \(22\) 个，显然状压，就是求最长的路径使得异或值只有一位是 \(1\)，考虑做到一棵子树时，只需要考虑经过根节点的路径，因为其他路径可以自底向上合并。

一个显然的结论是设 \(dis_{i,j}\) 表示 \(i\) 到 \(j\) 路径上的异或值，那么 \(dis_{i,j}=dis_{1,i} \ xor \ dis_{1,j}\)。

所以只需要考虑 \(dis_{1,i}\)，即可，然后找 \(dep_{i}+dep_j-2\times dep_{LCA(i,j)}\)。

后面的已知，相当于求前面的 \(dep_{i}+dep_j\) 的最大值。

考虑开桶，\(b_i\) 表示异或值为 \(i\) 的 \(dep_x\) 最大值，然后对于一个 \(dep_y\) 可以暴力找和它匹配的 \(x\) 统计答案。

暴力做 \(O(n^2)\)，一条链就可以卡掉。

然后需要 dsu on tree，其实就是重链剖分一下，然后重儿子的桶直接继承过来（做完不清空），轻儿子的暴力做，时间复杂度 \(O(n\log n)\)。

code

P6773 \(\color{black}{NOI/NOI+/CTSC}\) \(\color{red}\bigstar\)

给定一棵 \(n\) 个点的树和 \(m\) 条限制，你可以给树上的每一条边赋一个 \(0\) 或 \(1\) 的权值。对于所有限制 \((u,v)\) （保证 \(v\) 为 \(u\) 的祖先）你需要保证 \(u\) 到 \(v\) 上至少有一条边的权值为 \(1\)，求赋值方案数。
\(n,m\le 5\times 10^5\)

标签：dp，线段树合并。

神仙题，无论是 dp 还是线段树合并优化 dp 都是很难想的。

考虑暴力 dp 咋做。

很妙的一个状态：\(f_{i,j}\) 表示在 \(i\) 子树中所有下端点限制中，没有满足的上端点的深度最大值是 \(j\)，\(i\) 子树中的填边方案，因为如果有多个不满足条件的上端点，显然取最下面哪一个，因为最下面的满足了上面的也一定满足，如果 \(j=0\)，则表示条件都满足。

考虑咋转移。

如果 \(u\) 的儿子是 \(v\)，那么如果 \((u,v)\) 填 \(1\)，那么与状态没有啥关系，直接加和就好了。

\[f_{u,i}=\sum_{j=0}^{dep_u}f_{u,i}f_{v,j} \]

否则考虑填 \(0\)，那么此时状态第二维就要取两者较大值。

\[f_{u,i}=\sum_{j=0}^i f_{u,i}f_{v,j}+\sum_{j=0}^{i-1} f_{u,j}f_{v,i} \]

最后可以得到转移方程：

\[f_{u,i}=f_{u,i}(\sum_{j=0}^{dep_u}f_{v,j}+\sum_{j=0}^i f_{v,j})+f_{v,i}(\sum_{j=0}^{i-1} f_{u,j}) \]

令 \(mx_i\) 表示限制中以 \(i\) 为下端点的，上端点深度最大值，那么初值就是 \(f_{i,mx_i}=1\)。

暴力代码可以看卡老师的，时间复杂度 \(O(n^2)\)。

考虑咋优化。

可以考虑线段树合并，每个节点开一棵线段树，分别表示状态，然后考虑状态咋合并。

两个括号中，第一个括号第一项可以直接算，考虑后面的，在合并的时候顺便处理两个和即可。

具体实现就是合并时先合并左边再合并右边，然后昨晚后加一下两个和就好了。

code

P3694 \(\color{CornflowerBlue}{提高+/省选-}\) \(\color{gray}\bigstar\)

已知 \(n\) 个人，每个人有一个编号 \(a_i\)，每次可以选择一个人离开，离开若干人后把这些人放回去（放在空位中），不离开的人位置不变，使得编号相同的人相邻，问最少多少个人离开队伍。
\(n\le 10^5,m\le 20\)。

标签：状压 dp。

简单题，设 \(f_i\)，表示当前已经在前面放了集合为 \(i\) 的队伍，所需要离开人的最小值，枚举接下来是哪个队伍，然后直接做就好了。

code

CF1499F *2400 \(\color{gray}\bigstar\)

给定一棵 \(n\) 个节点的树和一个正整数 \(k\)。求有多少种边的集合，使得在将此集合中的所有边断开后，形成的所有连通块的直径都不大于 \(k\)。

标签：树形 dp。

设 \(f_{i,j}\) 表示 \(i\) 子树内最长链为 \(j\) 时的答案。

直接暴力转移就好了。

code

P7214 \(\color{black}{NOI/NOI+/CTSC}\) \(\color{red}\bigstar\)

有 \(n\) 个人排成一排，开始时他们都感染了病毒，有 \(m\) 个魔法，第 \(i\) 个魔法可以在 \(t_i\) 时刻把 \([l_i,r_i]\) 中的人治愈，花费为 \(c_i\)，每个时刻，一个被感染的人 \(i\) 会把病毒感染给 \(i+1\) 和 \(i-1\) ，求最少花费使得所有人治愈。

标签：线段树，最短路。

神题，\(\color{black}{d}\color{red}{jwj233}\) 推荐做的。

完全没啥思路啊，考虑两个魔法 \(i,j\)，令 \(l_i<l_j\)，那么如果 \(r_i-l_j+1\ge |t_i-t_j|\)，那么显然这两个魔法操作后中间会都治愈，也就是说可以合并为一个魔法。

然后可以发现如果魔法治愈了边界 \(1,n\)，那么那个方向就不会感染过来。

所以大概就是合并成一个 \([1,n]\) 的魔法，问最小花费。

考虑建边，如果满足上面那个条件就连边，最后问从左端点是 \(1\) 的魔法走到右端点是 \(n\) 的魔法的点权最小和。

暴力建边跑是 \(O(n^2)\)，寄。

可以分类一下，把绝对值去掉。

\[\left\{\begin{matrix}1+r_i-t_i\ge l_j-t_j\ (t_i>t_j) \\ 1+r_i+t_i\ge l_i+t_j\ (t_i< t_j) \end{matrix}\right. \]

一个比较显然的是对于每个 \(i\) 必然走 \(l_j>l_i\) 的 \(j\) 所以上面的成立。

然后考虑咋建边，一开始想的是主席树，但感觉非常阿拉丁。

实际上可以直接线段树，开始时按 \(t\) 排序，这样的话相当于查询一个前缀后缀，然后由于是点权和最小，所以在做 dij 的时候每次必然可以更新一个点必然更新，相当于每个点只会被能到达自己的最小的点更新，只会被更新一次，所以更新完了后就直接在线段树上扔掉。

然后具体找的话记录两个右边值的最小值，比较一下，如果该区间中有答案就暴力向下找，因为每找一次 \(O(\log n)\)，且至少会找到一个。

总时间复杂度 \(O(n\log n)\)。

code

开始板刷 CF *2600~*2700 了。

CF85E *2600 \(\color{blue}\bigstar\)

已知 \(n\) 座塔的坐标，把他们分成两组，使得同组内的两座塔的曼哈顿距离的最大值最小在此前提下求出有多少种分组方案，答案对 \(10^9+7\) 取模。
\(n\le 5000\)。

标签：二分。

考虑二分答案一下，那么久相当于知道了有一些点对他们不能分到一个组里，显然可以建二分图，然后染色判断一下，第一问做完了。

考虑第二问，建出二分图，那么实际上对于一个联通块来说有两种方法，直接并查集找一下联通块个数就好了。

时间复杂度 \(O(n^2\log n)\)，常熟小一点就过了。

code

CF1344D *2700 \(\color{blue}\bigstar\)

给你一个长为 \(n\) 的数组 \(a_i\) ，构造自然数数组 \(b_i\) 满足
\(\forall i ,b_i \in[0,a_i],\sum_{i=1}^nb_i=k\)。
并最大化 \(\sum_{i=1}^nb_i(a_i-b_i^2)\)，输出任意一组合法的 \(b_i\)。
\(n\le 10^5\)。

其实不是很难。

考虑求导一下，得到 \(f'(x)=-3x^2+A\)，可以发现斜率单调递减。

考虑暴力咋做，每次选一个对答案贡献最大的，然后向后移动一格，时间复杂度 \(O(k\log n)\)。

考虑由于越取越小，所以满足单调，直接二分一下最大的是多少，然后微调一下就好了。

嘴巴很简单，但实现真的阿拉丁，还卡精度（建议找零点还是用二分。

code

CF1034C *2700 \(\color{blue}\bigstar\)

一棵 \(n\) 个点的树，每个点有权值。你想砍树。你可以砍任意次，每次你选择一些边断开，需要满足砍完后每个连通块的权值和是相等的。求有多少种砍树方案。
\(n\le 10^6\)。

考虑如果已知每个连通块大小为 \(t\) 咋做。

记录一个 \(a_i\) 表示子树权值之和，然后如果 \(a_i\mod t=0\)，那么 \(i\) 向父亲的边必须断掉，不断掉就不合法，断掉一定最优。

然后可以发现实际上就是满足

\[\sum [a_i\mod t=0]=\frac{a_1}{t} \]

那么 \(t\) 就合法，并且方案数为 \(1\)。

但是发现 \(t\) 的取值很大，不好做。

很妙的一点是考虑 \(\frac{a_1}{t}\) 表示分成几个连通块，容易发现 \(\frac{a_1}{t}\le n\)，所以可以枚举这个。

枚举 \(\frac{a_1}{t}\)，一个子树产生贡献的实际上就是 \(\gcd(t,a_i)\) 的因数，这些因数有需要满足 \(\frac{a_1}{x}\le n\)，所以可以直接预处理。

code

CF13E *2700 \(\color{Gold}\bigstar\)

有 \(n\) 个洞，每个洞有弹跳值 \(a_i\)，跳一次可以从 \(i\) 跳到 \(a_i+i\) 个洞，维护两种操作。
0 x y 修改 \(a_x=y\)。
1 x 询问从 \(x\) 出发跳几次可以 \(>n\) ，并输出最后一个经过的洞。
\(n,m\le 10^5\)。

标签：分块。

和 P3203 一样。

考虑如果使用倍增跳，那么修改很难维护，所以考虑使用分块。

之前一道题的思路是记录 \(nex_i\) 表示 \(i\) 跳 \(\sqrt{n}\) 步之后的位置，但这个东西在本题中也难维护，因为这是个树形结构。

看题解，发现用 \(nex_i\) 表示从 \(i\) 开始跳，跳到第一个距离 \(i\) 超过 \(\sqrt{n}\) 的点，\(s_i\) 表示这样需要跳几次。

这样就很好维护，因为一次修改只会影响块内的，暴力重构就好了。

时间复杂度 \(O(n\sqrt{n})\)。

code

CF383E *2700 \(\color{green}\bigstar\)

给出 \(n\) 个长度为3的由 ′a′...′z′ 组成的单词，一个单词是正确的当且仅当其包含至少一个元音字母。这里的元音字母是 \(a-x\) 的一个子集。对于所有元音字母集合，求这 \(n\) 个单词中正确单词的数量平方的异或和。
\(n\le 24\)

标签：高维前缀和，容斥。

一个比较显然的容斥，选一个减去选两个加上选三个，然后做一个高维前缀和。

时间复杂度 \(O(n2^n)\)，然后过了？？

看了 CF 提交记录，发现只有一个是 \(O(2^n)\) 的。

由于最多只会选 \(3\) 个，所以设 \(f_{i,j}\) 表示集合为 \(i\) 选了 \(j\) 个的和。

然后发现这个东西像三维前缀和，直接做就好了，时间复杂度 \(O(2^n)\)。

code

loj6194 \(\color{Gold}\bigstar\)

给 \(n\) 个二维点 \((a_i,b_i)\) ，询问有多少种排列 \(p\)（答案对 \(10^9+7\) 取模）使得执行以下伪代码后留下的点是 \(i\) ，即最后 \(saved=i\)。

saved = p[1]
for x from 2 to n
    if a[p[x]] >= a[saved] and b[p[x]] >= b[saved]
        saved = p[x]

保证 \(a,b\) 是排列。
\(n\le 10^5\)。

标签：树状数组，dp，数学。

考虑 \(saved\) 在过程中形成一个序列 \(q_1,q_2...,q_k\)。

那么一个性质是对于 \(q_i\) 来说，所有 \(x_j>x_{q_i},y_j>y_{q_j}\) 的数必须放在 \(p_{i+1}\) 的后面。

假设有 \(x\) 个数需要放在一个数后面，那么总方案数可以推一下得到需要除以 \(x\)。

假设 \(p_i\) 有 \(A_i\) 个 \(j\) 满足条件，那么答案就是

\[\frac{(n-1)!}{A_1A_2A_3...A_{k-1}} \]

需要注意第一个必须选 \(q_1\)。

可以得到一个 dp，直接按上面那个做，然后发现是个二维数点，可以直接树状数组做。

code

CF351D *2700 \(\color{green}\bigstar\)

已知一个长度为 \(n\) 的序列 \(a\)，定义一次操作为选择三个数 \(v,t,k\)，满足 \(a_v=a_{v+t}=a_{v+2t}...=a_{v+kt}\) ，然后把这些数全部删去，删去后可以把该序列重排，现在有 \(Q\) 次询问，每次询问一个区间，求该区间至少多少次操作后被完全删除。
\(n,Q\le 10^5\)。

标签：回滚莫队。

考虑重排这个东西很有用，因为可以把相同的数放在一起，之后每次操作就是区间不同数的个数。

只有第一次操作前没有重排，问题相当于求一次操作后区间不同数个数的最小值。

一次操作最多去掉一种数，所以判断是否可以删除一种数就好了。

由于一次删除的是一个等差数列，所以用莫队维护一种数当前的左右端点以及公差是多少。

删除比较难做，所以直接回滚莫队，只需要增加就好了。

时间复杂度 \(n\sqrt{n}\)。

code

突然发现有 \(O(n\log n)\) 的做法，这里嘴巴一下。

考虑区间不同数的个数很好做，只需要判断是否有出现位置是等差数列的数即可。

然后可以记录一个 \(las_i\) 表示最小的一个 \(las_i\) 满足 \([las_i,i]\) 区间中 \(a_i\) 的出现位置是等差数列。

然后这个东西可以 \(O(n)\) 预处理，然后查询就和区间不同数个数一样了。

CF1270F *2700 \(\color{Gold}\bigstar\)

给定一个长度为 \(n\) 的 \(01\) 串 \(s\)。
求有多少个区间 \([l,r]\) 满足 \(r - l + 1\) 是 \(s_{l\dots r}\) 中 \(1\) 的个数的倍数。
\(n \le 2 \times 10^5\)。

标签：根号分治。

首先可以得到一个比较简单的暴力，枚举一个左端点，然后枚举一下有多少个 \(1\)，向后跳判断一下就好了。

会寄，考虑根号分治。

令 \(\frac{r-l+1}{s_r-s_{l-1}}=t\)，如果 \(s_r-s_{l-1}\ge \sqrt{n}\)，可以发现 \(t\le \sqrt{n}\)。

然后可以化简一下，变成 \(ts_r-r=t(l-1)-(l-1)\)，所以开桶做就好了。

时间复杂度 \(O(n\sqrt{n})\)。

code

3月杂题选做（part 2）

关于难度

推荐阅读