10.12 开始写，每天做的题都在这里了。
AT_arc058_b
考虑组合数。
对于从 \((1,1)\) 走到 \((n,m)\) 的方案数，显然是 \(C_{(n-1+1)+(m-1+1)-2}^{(n-1+1)-1/(m-1+1)-1}\)。那么考虑枚举一个行 \(i(1\le i \le n-a)\)，我们需要从 \((1,1)\) 走到 \((i,b)\)。这样能够使得我们的每一步都没有走到不可走的区域，然后从 \((i,b)\) 走到 \((n,m)\)。时间复杂度是 \(O(n\log n)\) 的。
AT_arc059_b
考虑答案上下界。
答案下界显然是 \(2\)，因为要求 \(l <r\)。对于一个满足条件的子串 \(t\)，令其众数为 \(x\)。有 \(2\) 种情况：
-
存在连续的 \(i,i+1\)，使得 \(t_i=t_{i+1}=x\)。此时直接构造 \(t'=t_it_{i+1}\) 是对的。
-
不存在连续的 \(i,i+1\)，使得 \(t_i=t_{i+1}=x\)。那么一定存在 \(t_{i}=t_{i+2}=x\)，否则众数不为 \(x\)。证明简单。此时构造 \(t'=t_it_{i+1}t_{i+2}\) 是对的。
所以答案上界为 \(3\)。然后暴力枚举 \(i\) 即可。时间复杂度是 \(O(|s|)\) 的。
AT_arc061_b
考虑暴力枚举。
发现 \(n,m\) 很大，但是对于一个黑点 \((i,j)\) 能够贡献到的 \(3 \times 3\) 的网格数量很少。所以对于每一个黑点 \((i,j)\)，我们去枚举它能贡献的所有 \(3 \times 3\) 的网格的中点 \((x,y)\)。改变一下它的黑点数量，随便维护一下即可。对于一个 \(n \times m\) 的网格，它里面 \(3 \times 3\) 的网格数量为 \(n \times m -2 \times (n+m) +4\)。时间复杂度 \(O(k\log V)\)。
AT_arc064_b
很难啊。
题目翻译没有说不能选两端的字符，但是就是不能选。
如果没有不能选两端的限制，考虑怎么做。对于当前字符串状态 \(s\)，若存在一个 \(i\)，使得 \(s_{i-1} \ne s_{i+1}\)。直接删掉。否则字符串 \(s\) 一定是 \(2\) 种字符交错排列的，删掉头即可。那么，对于没有限制的情况，当 \(|s|\) 是奇数时，先手必胜；反之同理。
现在考虑不能选两端的情况。那就相当于删掉了字符串的头和尾，然后没有限制地删。如果删头的时候出现了两个字符相同的情况且删尾也有同样的情况。那么此时字符串长度为奇数，且原字符串的头和尾均相同。先手必败。反之同理。
AT_arc066_b
好难啊。真的只有蓝嘛。
考虑 DP。定义状态函数 \(f_{i,j}\) 表示从高往低第 \(i\) 为，\(a+b=j\) 时不同的 \(a~ xor~ b\) 的值。然后考虑第 \(i\) 位放什么：
- \(2\) 个 \(0\)，此时有：\(f_{i-1,j} \to f_{i,j\times 2}\)。
- \(1\) 个 \(1\) 和 \(1\) 个 \(0\)，此时有：\(f_{i-1,j} \to f_{i,j\times 2+1}\)。
- \(2\) 个 \(1\)，此时有：\(f_{i-1,j} \to f_{i,j \times 2+2}\)。
然后就没有了，观察到有用的状态数不多，直接暴力即可。这题记忆化搜索就行了，纯暴力是 TLE 的。
AT_abc051_d
\(n\le 100\)，考虑暴力 Floyd。对于 Floyd 中的 \(f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k,j})\)，如果有 \(i \to j\) 的边，那么这条边在 \(f_{i,k}+f_{k,j} < f_{i,j}\) 的时候将会被松弛，也就是说这条边没用了。统计一下有多少条边满足条件，由于每条边都算了 \(2\) 次，所以实际答案是该数量的 \(\frac{1}{2}\)。时间复杂度 \(O(n^3)\)。
AT_abc054_d
直接暴力地 DP 即可。没什么好说的。
CF833B
考虑 DP。
定义状态函数 \(f_{i,j}\) 表示前 \(i\) 个数，分成 \(j\) 段的最大价值。有：\(f_{i,j}=\max(\{f_{k,j-1}+val(k+1,i)|0 \le k <i \})\)。难点在于求 \(val(i,j)\)。发现这玩意满足四边形不等式，但是直接记录 \(pre_i\) 表示颜色 \(c_i\) 在上一次的出现位置，那么在区间 \([pre_i+1,i]\) 的 \(val(x,y)\) 都会增加 \(1\) 的贡献。直接放线段树上维护，优化 DP 即可。复杂度 \(O(nk\log n)\)。
AT_arc108_e
考虑区间 DP。
定义状态函数 \(f_{l,r}\) 表示钦定选择了 \(a_l,a_r(a_l<a_r)\) 时，区间 \((l,r)\) 还能选择的期望数量。则有：\(f_{l,r}=1+\frac{1}{k}\times \sum\limits_{l < p < r\land a_l < a_p < a_r}^{}f_{l,p}+f_{p,r}\)。其中 \(k\) 表示 \(p\) 的数量。不难发现，\(\sum\) 中的二者独立。所以当我们枚举 \(l\) 后枚举 \(r\) 时，我们可以通过任意方式快速得到 \(k\)，\(\sum\limits_{l < p < r\land a_l < a_p <a_r}^{}f_{l,p}\) 和 \(\sum\limits_{l < p < r\land a_l < a_p <a_r}^{}f_{p,r}\)。然后加起来就行了。使用树状数组的时间复杂度是 \(O(n^2\log n)\) 的。
CF321E
考虑 DP。
定义状态函数 \(f_{i,j}\) 表示前 \(i\) 只狐狸分成 \(j\) 组的最小代价。那么有转移方程：\(f_{i,j}=\min(\{f_{k-1,j-1}+w(k,i)|0 < k\le i\})\)。发现 \(w(i,j)\) 满足四边形不等式，证明：
定义 \(sum(i,j)=\sum\limits_{x=i}^{j}\sum\limits_{y=i}^{j}a_{x,y}\)。那么有：\(w(a,c)+w(b,d)=\frac{sum(a,c)+sum(b,d)}{2},w(a,d)+w(b,c)=\frac{sum(a,d)+sum(b,c)}{2}\)。其中有：\(sum(a,d)=sum(a,c)+sum(a,b)+sum(c,d)+sum(b,d)-sum(b,c)\)。所以 \(w(a,d)+w(b,c)=\frac{sum(a,c)+sum(a,b)+sum(c,d)+sum(b,d)}{2}\ge w(a,c)+w(b,d)\)。
然后对于每一组分治即可。具体地，对于当前区间 \([l,r]\) 我们能够得到决策区间 \([pl,pr]\)，使得任意一个 \(l \le i \le r\)，都有 \(pl \le p_i \le p_r\)。能够先算出来 \(p_{mid}\) 的值，那么根据决策单调性就有 \(mid\) 左边的所有点的决策区间变成 \([pl,p_{mid}]\)，右侧同理。所以时间复杂度是 \(O(nk\log n)\) 的。
P9338
这题怎么这么难。
考虑 DP。
首先发现将 \(S\) 分成 \(<k\) 个子序列与分成 \(=k\) 个子序列是等价的。所以只需要求最少的子序列数量，使得它 \(\le k\)。将 \(S\) 看成 \(n \times n\) 的网格中的一条路径，将 \(A\) 看成向上走，\(B\) 看成像右走。那么一次交换 \(BA\) 的操作就会使右上变成上右。一条路径有解首先需要使得这条路径始终在对角线的上方。
根据贪心，分成的区间数量至少是这条路径的拐点数量。每次往右拐相当于一个区间。继续观察可以发现，一个区间的代价为这个拐点到原区间的拐点中间的面积数量。
然后就能 DP 了。令 \(s_i\) 为第 \(i\) 个 \(B\) 之前 \(A\) 的数量，\(S_i=\sum\limits_{j=1}^{i} s_i\)，\(cnt_i\) 为 \(s_j \le i\) 的 \(i\) 的数量，\(sum_i\) 为 \(s_j \le i\) 的 \(s_i\) 的和。 那么就有：\(w(l,r)=(cnt_{r-1}-(l-1))\times (r-1) -(sum_{r-1}-S_{l-1})\)。
把式子拆开：
\[w(l,r)=(cnt_{r-1}-(l-1))\times (r-1) -(sum_{r-1}-S_{l-1})\\ w(l,r)=cnt_{r-1}\times (r-1)-(l-1)\times (r-1)-sum_{r-1}+S_{l-1} \]定义状态函数 \(f_{i,j}\) 表示前 \(i\) 个数分成 \(j\) 段的最小代价，有：\(f_{i,j}=\min(\{f_{k-1,j-1}+w(k,i)|1 \le k \le i\})\)。然后就能够斜率优化。又因为 \(w(l,r)\) 满足四边形不等式，所以套用 wqs 二分可以做到 \(O(n\log n)\)。
CF1637G
/bx 多头老师
不容易观察到最终的数是 \(2^k\)。只要我们能够构造出来一个 \(0\)，那么就可以通过倍增的方式将所有数变成 \(2^k\) 了。那么对于每次操作，我们需要找到一组 \((x,y)\)，使得 \(x+y=2^w(w \le k)\)。
考虑如何实现。首先可以找到当前最大的一个数，然后枚举 \(k\)，使得存在一个 \(y=2^k-x\)。能够证明该做法一定是正确的。因为如果连最大的数都不行，那么小的数可能不行了。如果大的不行，那么考虑在之后将它操作，也就是继续选择次大的数，并将这个数暂存一下。最后剩余一个数时就是答案了。时间复杂度是 \(O(n\log n)\) 的。
P11184
考虑一个余数 \(r\) 满足条件的限制。因为 \(p=\frac{n-r}{q}\)，且 $ 0 \le r <p$。所以直接求解就行了。
P11185
按照三种情况分别排序。那么一个同学的最终排名就是这三种情况排名最靠前的一个。
P11186
考虑对这个表达式建树。对于点 \(x\)，我们记录它的值 \(val\) 与判断符 \(c\)。分情况讨论：
-
\(c\) 是小于号，则一个查询数字 \(k\) 小于 \(val\) 时答案一定存在于 \(x\) 的左子树，反之同理。
-
\(c\) 是大于号，则一个查询数字 \(k\) 小于等于 \(val\) 时答案一定存在于 \(x\) 的左子树，反之同理。
如果对于每个询问的 \(k\) 都去搜索一遍的话，时间复杂度将会达到 \(O(nq)\)。考虑优化。
既然在线比较困难，那就离线看看。对于当前节点 \(x\)，我们能够得到一个询问区间 \([l,r]\)，使得这个区间中任意一个 \(k_i\) 对应的答案都存在于 \(x\) 的子树中。那么，依旧分情况讨论：
-
\(c\) 是小于号，则查询区间中数字 \(k_i\) 小于 \(val\) 时答案一定存在于 \(x\) 的左子树，反之同理。
-
\(c\) 是大于号，则查询区间中数字 \(k_i\) 小于等于 \(val\) 时答案一定存在于 \(x\) 的左子树，反之同理。
记最后一个答案在 \(x\) 的左子树中的询问下标为 \(w\)，则 \([l,w]\) 的答案一定在 \(x\) 的左子树中，\((w,r]\) 的答案一定在 \(x\) 的右子树中。分治下去即可。这样的话时间复杂度是 \(O(q+n\log n)\) 的。
注意特判 \(n=0\) 的情况。
P11187
考虑 DP。
定义状态函数 \(f_{i,0/1}\) 表示子序列的最后一位的值为 \(i\)，且已经/没有连续两个 \(i\) 时的最大子序列长度。那么我们枚举 \(x\)，有：\(f_{a_x,0}=f_{a_x,1}+1,f_{a_x,1}=\max(\{f_{i,0}|i \ne a_x\})+1\)。前者直接转移，后者拿一个线段树随便优化就行了。这样的时间复杂度是 \(O(n\log n)\) 的，但是存在线性做法。
P11188
考虑 DP。
首先发现性质：当一个数的位数 \(>10\) 时，进行操作一一定优于操作二。因为数据范围有：\(1 \le v_i \le 10^5\)。
那么操作二时数的长度就不会超过 \(10\) 了。定义状态函数 \(f_{i,j}\) 表示从后往前第 \(i\) 位，保留了 \(j\) 位时删完的最小代价。那么有：\(f_{i,j}=\min(f_{i,j},f_{i+1,j}+v_{s_i}),f_{i,j+1}=\min(f_{i,j+1},f_{i+1,j}+s_i\times 10^j)\)。时间复杂度 \(O(10 \times n)\)。
P11190
考虑答案长什么样子。
对于不相同的一组 \(s_i,s_j\)，我们可以将它们拼起来。那么就会得到若干个二元组，然后剩下一些相同的 \(s_i,s_j\)。此时我们只需要考虑如何将剩下的字符放进这些二元组内，如果可行则答案一定是二元组数量。
令剩下的字符为 \(x\)，如果有一组 \((s_i,s_j)\)，使得 $s_i \ne x $ 且 \(x\) 中有些的下标大于 \(j\)，那么可以将它们全部拼到这个二元组后面。另一种情况同理。
如果还剩有字符，考虑替换两个二元组 \((s_{x1},s_{y1})\) 和 \((s_{x2},s_{y2})\)。使得其能够容下更多的字符。
如果还有，那么无解。可以证明，无解的情况只有形如：\(aaa\dots aaa\) 和 \(aaa \dots b \dots aaa\)。也就是无法分解的回文串。
之后就只剩下模拟了。注意，拼二元组的时候需要优先将当前的众数与其它的字符进行拼接，以保证能够容下更多的字符。实现难度不大，细节较多。时间复杂度 \(O(n\log n)\)。
CF2025A
如果操作 \(1\)，最优方案显然是先弄个最长公共前缀然后自己弄自己的。那么把最长公共前缀求出来就行了。时间复杂度 \(O(n)\)。
CF2025B
数感好的秒出答案。数感不好的果断打表观察规律。发现对于 \(C_{i,j}\)，若 \(j=0\lor i\)，则其值为 \(1\)，否则为 \(2^j\)。时间复杂度 \(O(n\log n)\)。
CF2025C
注意读题。发现题目中有这么一句话：Monocarp 可以取任何一张符合条件的牌，不管它在牌组中的位置如何。
那么这题就好做了。不考虑顺序，直接将 \(A\) 序列排序。然后使用双指针即可。时间复杂度 \(O(n\log n)\)。
CF2025D
注意到除了能增加智力或力量的那 \(m\) 个点外，其它的点貌似没什么用。令 \(p_i\) 表示第 \(i\) 个能获取属性点的下标。定义状态函数 \(f_{i,j}\) 表示前 \(i\) 个点中，智力为 \(j\) 时能够通过的最多的检查点数量。
那么有转移方程：\(f_{i,j}=\max(f_{i-1,j}+w1(p_i,p_{i+1},j)+w2(p_i,p_{i+1},i-j),f_{i-1,j-1}+w1(p_i,p_{i+1},j)+w2(p_i,p_{i+1},i-j))\)。其中 \(w1(l,r,k)\) 为区间 \([l,r]\) 中检查点所需的智力不超过 \(k\) 的数量，\(w2(l,r,k)\) 同理。时间复杂度 \(O(m^2)\)。
CF2025E
考虑 DP。
注意到对于一种花色 \(x(x\ge 2)\)，第一个人得到的一定不多于第二个人得到的。因为一旦比第二个人多，那么他一定会剩下一些这种花色的牌，并且用不出去。那么对于第二个人比第一个人得到的该花色的牌多的情况，此时只能由第一个人得到的多的花色为 \(1\) 的牌抵消掉。
那么思路就有了。我们只需要求出一个 \(g_i\)，表示 \(2\sim n\) 这些花色中，第二个人比第一个人多 \(i\) 张牌的方案数（其它的牌都两两抵消掉了）。然后再求一个 \(f_{i}\)，表示第一个人比第二个人多 \(i\) 张花色 \(1\) 的牌的方案数。那么答案就是 \(\sum\limits_{i=0}^{m} f_i \times g_i\)。
对于 \(g_i\)，不难发现是由 \(f'\) 经过 \(n-1\) 次背包转移得到的。因为每种花色对应的方案数相同。这里的 \(f'_i\) 和 \(f_i\) 的区别仅在于是第二个人比第一个人多 \(i\) 张牌。那么只要求出 \(f_i\)，就能得到 \(f'_i\)，从而得到 \(g_i\) 了。
定义状态函数 \(dp_{i,j,k}\) 表示前 \(i\) 张牌，发给第一个人 \(j\) 张，第一个人比第二个多 \(k\) 张的方案数。那么分类讨论：
- 第 \(i\) 张牌给第一个人，有：\(dp_{i,j,k}\to dp_{i,j,k}+dp_{i-1,j-1,k-1}\)。
- 第 \(i\) 张牌给第二个人，有：\(dp_{i,j,k}\to dp_{i,j,k}+dp_{i-1,j,k+1}\)。
那么有：\(f_i=\sum\limits_{j=0}^{m} dp_{m,j,i}\)。
然后 \(f'_i\) 和 \(g_i\) 就能相继求出来了。时间复杂度 \(O(m^3+m^2n)\)。
AT_jag2018summer_day2_i
很显然，有还原的题基本不能用势能分析做。
考虑线段树。
考虑换个方式维护。因为这题目有区间加法和区间除法。我们记录下来每次除法之后，得到的商、余数和除数。即：\(c\times b+a=c'\)。其中 \(c\) 是商，也就是当前的值，\(b\) 是除数，\(a\) 是余数，\(c'\) 是除法前的数也就是被除数。
那么，考虑一种映射：\(f(x)=\lfloor\frac{a+x}{b}\rfloor+c\)。对于每个数，我们都记录下来最近一次除法或加法后得到的商、余数和除数。那我们就可以快速得到当前这个数实际上的值了。及其分别为 \(c,a,b\)。
加法操作。直接就是在 \(c\) 上面进行加法操作。
除法操作。假设该操作为区间除以 \(w\)。这里的 \(x\) 并未改变，我们需要调整的只有该映射中的 \(a,b,c\)。所以有：\(a'=(a+bc)\bmod bw,b'=bw,c'=\lfloor\frac{a+bc}{bw}\rfloor\)。在这里，我们将 \(\frac{a}{b}+c\) 写成了 \(\frac{a+bc}{b}\)，方便计算。然后除法操作就可以直接维护了。
还原操作。我们再维护一个 \(rmax\)，表示当前节点在最开始的区间 \(max\) 值。那么一个还原操作就相当于将当前的 \(max\) 值变成 \(rmax\)，并且清空其映射的参数。记录一个懒标记表示该节点的子树是否需要全部还原即可。
询问操作。直接就是正常的区间询问最大值，不再赘述。
该算法的时间复杂度为 \(O(n\log n)\)。有一个小细节，就是在我们维护的 \(b\) 这个参数比 \(3\times 10^8\) 大时，能够证明 \(b\) 的增加是无效的。所以可以直接让 \(b\) 成为其中一个能够被接受的值。不然可能会 RE 或者 WA。
P8600
好像是我今年在中山集训的某场模拟赛 T4。当时太菜了，只因没做过套路题。
首先这道题可以转化成求有多少个区间 \([l,r]\)，使得 \(r-l=\max(a_l,a_{l+1},\dots,a_r)-\min(a_l,a_{l+1},\dots,a_r)\)。然后这种问区间数量，且存在区间最大、最小值的题。有一种套路，详见 AT_abc248_h 的题解。第一次遇到这种套路是在做 Norma 的时候。感觉很强啊。
考虑分治。我们枚举左端点 \(l\)，那么现在已知 \(\max(a_l,a_{l+1},\dots,a_{mid})=mx,\min(a_l,a_{l+1},\dots,a_{mid})=mi\)。令 \(Max_i=\max\limits_{j=mid+1}^{i}a_j,Min_i=\min\limits_{j=mid+1}^{i} a_j\)。我们能够通过指针找到最远的一个 \(j\)，使得 \(Max_j \le mx\)。也能找到一个最远的 \(k\)，使得 \(Min_k \ge mi\)。现在进行分类讨论：
- \(r \le \min(j,k)\)。此时区间最小、最大值固定。那么有：\(r=mx-mi+l \land mid+1 \le r \le \min(j,k)\)。
- \(\min(j,k) < r \le \max(j,k)\)。这时有两种情况，以 \(j <k\) 为例。此时区间最小值固定，区间最大值与 \(Max_r\) 相等。那么有：\(l-mi=r-Max_r\land \min(j,k) < r \le \max(j,k)\)。
- \(\max(j,k)<r \le R\)。此时区间最小值与 \(Min_r\) 相等，区间最大值与 \(Max_r\) 相等。那么有：\(l=r+Min_r-Max_r \land \max(j,k) < r \le R\)。
上面的所有满足条件的 \(r\) 都可以分别用桶存起来，所以访问是能够做到 \(O(1)\) 的。故时间复杂度为 \(O(n\log n)\)。
CF526F
将二维问题转化成一维的问题。让 \(a_i=j\)，那么问题就变成 \(P8600\) 了。这能 *3000？？？时间复杂度 \(O(n\log n)\)。
P10587
考虑势能线段树。
不难发现，当 \(V=5\times 10^5\) 时，小Y 喜欢的数只有 \(5\) 个。这里使用两种势能，第一种表示 \(x\) 这个数可能成为小Y 喜欢的数的势能，第二种表示 \(x\) 这个数达到 \(V\) 的势能。
对于区间加法操作。我们令 \(nxt_i\) 表示 \(i\) 与第一个比 \(i\) 大且是小Y 喜欢的数的差。对于每个节点，维护 \(mit\) 表示该节点维护的区间中 \(nxt_x\) 最小的值。进行分类讨论：
- \(mit > x\)。此时势能无影响，且对答案无影响。直接做区间加法即可。
- \(mit \le x\)。此时区间总势能至少减 \(len\)。下传继续维护区间加法。
对于区间乘法操作。每个数的初始势能不大于 \(\log V\)，一个区间的总势能至少减 \(len\)。下传继续维护区间乘法。
对于区间覆盖操作。该操作将会使一个区间的两种势能统一，且恢复原来的势能需要 \(O(n)\) 的代价。直接进行区间覆盖即可。在这里，对于一个区间所有数都相同的时候，加法操作和乘法操作均能够将该区间视做单点，所以无需下传维护。
对于区间询问。我们因为 \(mit \ge 0\)，我们记录每个点维护的区间中 \(nxt_x=mit\) 的数量，记为 \(cnt\)。当该点的 \(mit=0\) 时，答案即为 \(cnt\)。否则为 \(0\)。
根据势能分析，该算法的时间复杂度为 \(O(n\log V)\)。
AT_arc059_c
考虑 DP。
发现数据范围不大，定义状态函数 \(f_{i,j}\) 表示前 \(i\) 个小朋友，一共得到 \(j\) 颗糖的愉悦度。那么有：\(f_{i,j}=\sum\limits_{k=0}^{j}(f_{i-1,j-k}\times \sum\limits_{w=a_i}^{b_i}w^k)\)。
观察式子，发现 \(\sum\limits_{w=a_i}^{b_i}w^k\) 可以通过前缀和预处理出来。令 \(s_{i,j}=\sum\limits_{k=0}^{i}k^j\)。那么转移方程可以写成：\(f_{i,j}=\sum\limits_{k=0}^{j}(f_{i-1,j-k}\times (s_{b_i,k}-s_{a_i-1,k}))\)。时间复杂度 \(O(n^3)\)。
P3605
考虑将树转化成 DFS 序。那么就是查询区间 \([dfn_x,dfn_x+siz_x-1]\) 中比 \(p_x\) 大的数的数量了。拿一个主席树，维护的值域线段树。然后直接查询就行了。时间复杂度是 \(O(n \log n)\) 的。
AT_arc060_c
考虑倍增。定义 \(f_{i,j}\) 表示从 \(i\) 开始尽量往右走，走 \(2^j\) 天后能够到达的最远的点。那么对于询问 \(a,b\)，就是求一个最小的 \(x\)，使得 \(a\) 往右走 \(x\) 天后离 \(b\) 最近。这个倍增跳的时间复杂度是 \(O(n\log n)\) 的。
AT_arc067_c
考虑 DP。
根据题意就能直接定义状态函数并且正确的一题。定义状态函数 \(f_{i,j}\) 表示到 \(i\) 个人一组的组，一共分了 \(j\) 个人的方案数。那么能够得到转移方程：\(f_{i,j}=f_{i-1,j}+\sum\limits_{k=c}^{d}f_{i-1,j-k\times i}\times C_{n-j+k\times i}^{k\times i}\times \frac{\prod\limits_{w=1}^{k}C_{k\times i- (w-1)\times i}^{i}}{k!}\)。其中 \(f_{i-1,j}\) 表示 \(F_i=0\) 的情况。\(C_{n-j+k\times i}^{k\times i}\) 表示选出 \(k\times i\) 个人的方案数。而 \(\frac{\prod\limits_{w=1}^{k}C_{k\times i- (w-1)\times i}^{i}}{k!}\) 表示将这些人分成 \(k\) 组的方案数，这里可以简化成 \(\frac{\prod\limits_{w=1}^{k}C_{w\times i}^{i}}{k!}\)。
考虑快速计算 \(\prod\limits_{w=1}^{k}C_{w\times i}^{i}\)。发现这是一个前缀积的形式，令 \(s_{i,j}=\prod\limits_{k=1}^{i}C_{k\times j}^{j}\)，则有：\(s_{i,j}=s_{i-1,j}\times C_{i\times j}^{j}\)。那么转移方程就可以写成：\(f_{i,j}=f_{i-1,j}+\sum\limits_{k=c}^{d}f_{i-1,j-k\times i}\times C_{k\times i}^{n-j+k\times i}\times \frac{s_{k,i}}{k!}\)。
因为 \(\sum\limits_{k=c}^{d}f_{i-1,j-k\times i}\times V\) 是一个调和级数的形式，所以该算法的时间复杂度为 \(O(n^2\log n)\)。预处理 \(C_{i,j}\) 即可。
P4269
DP 的转移不难，难点在于去重。令上一次 \(a_i\) 出现的位置为 \(j\)。我们能够得到 \(1\sim i-1\) 与 \(i\) 形成的上升子序列的数量。而这里面恰好完全包含了 \(1\sim j-1\) 与 \(j\) 形成上升子序列的数量。而 \(a_j=a_i\)。所以只有 \(j+1 \sim i-1\) 与 \(i\) 形成的上升子序列是新增的。所以记录一下上一次 \(a_i\) 对应的数量即可。时间复杂度 \(O(n\log V)\)。
P6477
对于一个 \(r\)，我们有 \(g_r=\sum\limits_{l=1}^{r}(f_{l,r})^2\)。令 \(lst_x\) 表示上一次 \(x\) 出现的位置。那么 \(lst_{a_r}+1\sim r\) 这段区间所有位置的 \(f_{l,r}\) 都会增加 \(1\)，其余位置不变。所以 \(g_r\) 比 \(g_{r-1}\) 多 \(r-lst_{a_r}+2\times \sum\limits_{l=lst_{a_r}+1}^{r}f_{l,r}\)。直接维护即可。时间复杂度 \(O(n\log n)\)。
P6569
矩阵快速幂。构造 \(n\times n\) 的矩阵，若 \((i,j)\) 为 \(1\)，则表示有一条 \(i\) 到 \(j\) 的边。那么，就可以直接矩阵快速幂优化了。朴素的时间复杂度为 \(O(qn^3\log V)\)。若将 \(E^{2^i}\) 预处理出来，则可以做到 \(O(qn^2\log V)\)。
标签：le,log,limits,sum,CSP2024,times,做题,情况,复杂度 From： https://www.cnblogs.com/harmisyz/p/18471548