2026.2 状态精炼

洛谷P5564 [Celeste-B] Say Goodbye
神（秘）题。
考虑 \(n\) 个点有根无标号子树有序的树的计数，可以发现这东西就是 \(C_{n-1}\)，\(C\) 表示卡特兰数，因为这棵树的括号序是一对大括号里面套上由 \(n-1\) 对括号形成的合法括号序列。记 \(F(x)=\sum\limits_{i\ge2}C_{i-1}x^i\)。
如果有染色，乘上 \(\binom{n}{a_1,\dots,a_k}\) 就行。
根据 Burnside 引理可以得到：

\[ans=\sum_{l=2}^{n}\frac{1}{l}\sum_{d=1}^{l}f(d) \]

其中 \(l\) 表示基环树的环长，\(f(d)\) 表示环转 \(d\) 次的不动点个数。
经过一些转化可以得到：

\[ans=\sum_{l=2}^{n}\frac{1}{l}\sum_{d\mid l}\varphi(\frac{l}{d})f(d) \]

一个可能不对的证明：
假设当前要求 \(f(k)\)，环长为 \(l\)。
对于一张点编号在 \(0\sim l-1\) 的图，\(i\) 向 \((i+k)\bmod l\) 连边，则有 \(\gcd(k,l)\) 个环，环长为 \(\frac{l}{\gcd(k,l)}\)。
可以发现，每个环中每个点的子树结构和染色都要一样，因此 \(f(k)\) 的取值只和 \(\gcd(k,l)\) 有关，所以有 \(f(k)=f(\gcd(k,l))\)
然后枚举一下 \(\gcd\) 就能转化到那个形式。
对于 \(l\) 的一个因子 \(d\)，可以发现 \(f(l/d)=\binom{n/d}{a_1/d,\dots,a_k/d}\times[x^{n/d}]F^{l/d}\)。
带回去，有：

\[\begin{aligned}& ans\\=& \sum_{l=2}^{n}\frac{1}{l}\sum_{d\mid l}\varphi(d)f(\frac{l}{d})\\=& \sum_{l=2}^{n}\frac{1}{l}\sum_{d\mid l}\varphi(d)\binom{n/d}{a_1/d,\dots,a_k/d}\times[x^{n/d}]F^{l/d}\\=& -\binom{n}{a_1,\dots,a_k}C_{n-1}+\sum_{d=1}^{n}\varphi(d)\binom{n/d}{a_1/d,\dots,a_k/d}\times[x^{n/d}]\sum_{k=1}^{n/d}\frac{F^k}{kd} \end{aligned}\]

对于最右边那个 \(\sum\limits_{k=1}^{n/d}\frac{F^k}{kd}\)，把 \(d\) 拉出去，发现 \(k\) 的上界其实可以开到正无穷，然后变成了 \(-\ln(1-F)\)，其实就是泰勒展开一下。
不难注意到 \(d\) 要满足 \(d\mid\gcd(a_i),d\mid n\)。
套一个多项式板子就行了！
省选集训模拟赛 #2 T2
阴间的套路（？）题
用 \(a\) 表示最初的 \(A\)，\(a'\) 表示排序 \(k\) 轮后的 \(A\)。
很难注意到，如果 \(a\) 是一个 01 序列，那么做一层双向冒泡后相当于把第一个 1 和最后一个 0 互换一下。
最终答案可以写成 \(\sum\limits_{v=1}^{n}\sum\limits_{i=l}^{r}[a'_i\ge v]\) 的形式，差分一下变成求 \(\sum\limits_{v=1}^{n}\sum\limits_{i=1}^{r}[a'_i\ge v]\)。
对于一个 \(v\)，把 \(a\) 中大于等于它的看成 \(1\)，小于它的看成 \(0\)，那么 \(\sum\limits_{i=1}^{r}[a'_i\ge v]\) 就是 \(a\) 排序后 \(1\sim r\) 的区间和。
不难发现 \(\sum\limits_{i=1}^{r}[a'_i\ge v]=\max(\sum\limits_{i=1}^{r}[a_i\ge v]-k,\max(r-v+1,0))\)。
解释一下，最开始前 \(r\) 个数有 \(\sum\limits_{i=1}^{r}[a_i\ge v]\) 个 \(1\)，排序完后就是减掉 \(k\)，然后可能还会有 \((n-v+1)-(n-r)\) 个 \(1\) 不能放在 \(r+1\sim n\)，就堆在 \(1\sim r\) 里。
考虑怎么求这个诡异状物，按 \(r\) 从小到大扫描线，用线段树可以简单维护 \(\sum\limits_{i=1}^{r}[a_i\ge v]\) 和 \(r-v+1\)，查询的时候把前面那个全局减掉 \(k\)，线段树二分分界点就能把 \(v\in[1,r]\) 的答案查询出来，\(v\in[r+1,n]\) 的答案可以再二分一次求，再把 \(k\) 加回去。
轻轻松松啊！（实则不然
省选集训模拟赛 #2 T1
没有人类了/ll
不难发现，如果一条边 \((u,v)\) 的边权为 \(\min(u,v)\)，那么 \(j\in V_i\) 当且仅当 \(i\) 到 \(j\) 的路径中最小边权的最大值大于等于 \(j\)。
注意到（？，\(V_i\) 其实就是 \(i\) 在最大 Kruskal 生成树上的祖先集合，证明是简单的！
然后图上问题就能转成树上问题了！
第一问：
枚举一下 \(S\) 的 lca，可以发现交集大小其实就是 \(V_{lca}\) 的大小，然后是简单的。
第二问：
dp。设 \(f_i\) 表示只考虑 \(i\) 子树的贡献。
不难（？）得到：

\[f_u=k(2(\sum_{v\in son_u}(f_v+1)-1)+1) \]

\(f_v+1\) 是 \(v\) 这个子树的贡献，加一是因为可以不选，减一是减掉全都不选的情况，乘二是 \(u\) 选不选都行，再加一是加上只选 \(u\) 的贡献，乘 \(k\) 是因为并集多了 \(u\) 这个点。
第三问：
没有人类了/ll（点题）
你注意到 \(V_i\oplus V_{fa_i}=\{i\}\)，因此单点集合是可以拿来随便异或的，也就是说所有 \(\bigoplus_{i\in S}V_i\) 构成的集合等于 \(\{1,\dots,n\}\) 的非空子集，答案是 \(\sum\limits_{i=1}^{n}\binom{n}{i}\lceil\frac{i}{k}\rceil\)。
然后就做完了！
qoj8353 T1
这题最难的地方是你要觉得你的复杂度能过！
你先胡一个简单的 \(O(2^nn^4)\)：
枚举行的集合 \(S\)，从小到大记为序列 \(a_i\)，然后从枚举列，如果这列的 \(S\) 行满足单调，那么这列就能选上，否则给它丢了。
dp。用 \(f_{i,T}\) 表示考虑到第 \(i\) 列且强制选第 \(i\) 列，\(i\) 列不单独选，\(T_{a_j}\) 为 \(0/1\) 说明第 \(a_j\) 行递减/递增的方案数，最终答案就是所有 \(f_{i,T}\) 的和再加上能选上的列数（因为没考虑单独的）。
转移也不难，枚举能选上的列 \(i,j,i>j\)，比较一下这两列的 \(S\) 行，搞出一个 \(T'\)，就有 \(f_{i,T'}\gets f_{j,T'}+1\)。
优化其实也不难！可以预处理出 \(S={1,\dots,n}\) 时任意两列的 \(T'=cmp_{i,j}\)，那么比较 \(i,j\) 时就有 \(T'=cmp_{i,j}\& S\)
然后就能得到一个 \(O(2^nn^2)\) 的做法。
直接交上去，发现过了！！
我赛时 0.5h 想到 \(O(2^nn^2)\)，但是以为它过不去又瞪了若干 h/ll
loj6786 克莱茵蓝彼岸花
不难发现 \(\max\limits_{x=1}^{3}\max\limits_{i\in S_x}a_i=\max\limits_{i=1}^{n}a_i\)，\(\sum\limits_{x=1}^{3}\sum\limits_{i\in S_x}d_i=\sum\limits_{i=1}^{n}d_i\)，可以直接把这两项毙掉。
你发现 \(\Xi\) 的第二项比较难处理，可以按 \(b\) 从小到大排序，那么 \(\max\limits_{i\in S_x} b_i\) 就是 \(S_x\) 中选的最后一个数的 \(b\)。
不妨设 \(S_1\) 选的最后一个数在 \(l\)，\(S_2\) 选的最后一个数在 \(r\)，\(S_3\) 选的最后一个数在 \(n\)，且满足 \(l<r<n\)。那么 \([1,l]\) 中的数 \(S_1,S_2,S_3\) 都能选，\((l,r]\) 中的数 \(S_2,S_3\) 可以选，\((r,n]\) 中的数只有 \(S_3\) 能选。
可以考虑枚举 \(l\)，然后再最小化 \(\Xi_b\times \Xi_c\)，其中 \(\Xi_b\) 表示 \(\Xi\) 的第二项，\(\Xi_c\) 就是第三项。
对于 \(\Xi_b\)，dp！设 \(f_{i,x,y}\) 表示将 \([i,n]\) 中的数加到 \(S_2\) 和 \(S_3\)，且满足 \(\sum\limits_{j\in S_2}c_j=x\)，\(\sum\limits_{j\in S_3}c_j=y\) 的所有方案中 \(b_r+b_n\) 的最小值。可以发现 \(y=\sum\limits_{j=i}^{n}c_j-x\)，就能把这一维去掉。
不难发现初始值是 \(f_{n+1,x}=\infty\)，转移是 \(f_{i,c_i}\gets b_i+b_n\)，\(f_{i,j}\gets\min(f_{i+1,j},f_{i+1,j-c_i})\)。
还要预处理一个 \(g_{i,x,y,z}\) 表示 \([1,i]\) 中的数是否存在一个分配方案，使得 \(S_1\) 的和为 \(x\)，\(S_2\) 的和为 \(y\)，\(S_3\) 的和为 \(z\)。你发现 \(z=\sum\limits_{j=1}^{i}c_j-x-y\)，可以把这一维去了，再滚动一下就不用存第一维了。
转移是简单的，\(g_{i,x,y}=g_{i-1,x,y}\cup g_{i-1,x-c_i,y}\cup g_{i-1,x,y-c_i}\)，可以用 bitset 简单维护。
现在考虑枚举 \(l\) 的时候要干啥。
枚举时，枚举 \(S_1\) 中 \(c\) 的和 \(j\)，可以发现 \(j\in[\lfloor\frac{1}{3}\sum c_i-\max c_i\rfloor,\lceil\frac{1}{3}\sum c_i+\max c_i\rceil]\)。为啥呢？如果 \(j<\lfloor\frac{1}{3}\sum c_i-\max c_i\rfloor\)，那么 \(S_2\) 和 \(S_3\) 中一定有一个集合的 \(c\) 的和比 \(j\) 大 \(\max c_i\)，此时将那个集合的数换进 \(S_1\) 更优，上界是类似的，因此 \(j\) 的数量级是 \(O(\max c_i)\)。
然后枚举 \(S_2\) 在 \([1,l]\) 中的数的 \(c\) 的和 \(x\)，以及在 \((l,n]\) 中的数的 \(c\) 的和 \(y\)，\(x\) 需要满足 \(g_{l,j,x}\) 为真，不难发现 \(\Xi_b=b_l+G_{l+1,y}\)，\(\Xi_c=\max(j,x+y,\sum\limits_{i=1}^{n}c_i-j-(x+y))\)。
也就是说，我们要最小化 \((b_l+G_{l+1,y})\times\max(j,x+y,\sum\limits_{i=1}^{n}c_i-j-(x+y))\)。
不可以发现，当 \(y\) 固定时，\(\max(x+y,\sum\limits_{i=1}^{n}c_i-j-(x+y))\) 取到最小值当且仅当：\(x\) 为满足 \(x+y\ge\sum\limits_{i=1}^{n}c_i-j-(x+y)\) 的最小值，或为满足 \(x+y\le\sum\limits_{i=1}^{n}c_i-j-(x+y)\) 的最大值，枚举 \(y\) 然后写两个双指针就行
然后就做完了！！！！！！！！！！！！！！！！！！！！！！！！！！！！
洛谷P9393 紫丁香
ljfjslkjdflsjfskljdflksdjjeopwpii
答案肯定是从高位往地位贪心，然后要做 check 一个答案合不合法。
假设要判断 01 串 \(S'\) 合不合法：
记当前状态是 \(R\)，\(R\) 中 1 的位置表示这个位置必须是 1，为 0 的位置表示这个位置是啥都行。
按操作从后往前，初始状态 \(R=S'\)。
对于当前操作，他 0 的位置和 \(R\) 中 1 的位置显然不能有交，而他 1 的位置与 \(R\) 中 1 的位置的交集从今往后都不用管，可以把 \(R\) 上这些位置的 1 变成 0。
操作都扫完后，\(R\) 中剩下的 1 肯定是 \(S\) 中 1 的位置的子集，不然那些不在 \(S\) 的 1 里的就不能填上。
可以发现，对于 \(0\sim 2^m-1\) 的数，它在扫完操作后得到的数的 popcount 肯定越小越好，把最后的数记为 \(f_i\)，check 就是判断 \(f_{S'}\) 是不是 \(S\) 中 1 的位置的子集。
考虑怎么求 \(f_i\)，可以发现如果一个操作中 0 的位置和 \(i\) 中 1 的位置无交，那么就能通过这个操作把 \(i\) 中的 1 减少，因此还需求出一个 \(g_i\)，表示所有 0 的位置是 \(i\) 中 1 的位置的子集的操作的 1 的位置的并集，可以高维前缀和求，就有转移 \(f_i\gets f_{i\oplus(i\& g_{2^m-1-i})}\)，需要注意后面那个下标等于 \(i\) 的情况，此时 \(f_i=i\)。
然后就做完了！！！！
洛谷P10756 [COI 2023] Sličnost
记 \(p_i\) 表示 \(a_i\) 在 \(b\) 中出现的位置，每次修改就相当于交换 \(p\)，\(i\) 对应的区间是 \([max(1,p_i-k+1),p_i]\)。
先考虑 \(q=0\)：
开一棵线段树，初始全是 \(0\)。
从 \(k\) 到 \(n\) 扫描线，扫到 \(i\) 的时候，让 \([i-k+1,i]\) 中的所有区间做一个区间+1，\(i\) 的贡献就是当前这个线段树的全局最大值和最大值个数。
无修就做完了！
对于每次修改，你发现它在扫描线时只会对 \(t_i\) 和 \(t_i+k\) 产生影响，可以对每个 \(i\) 都开个 vector 存下。
扫描线的时候，先求出 \(i\) 无修时对应的线段树，然后扫一遍它 vector 里的，可以发现 \(i\) 的每个修改会对一个操作区间产生贡献，可以把这个区间差分一下，就能存下来了。
求答案就是扫一遍操作，再开一个线段树维护每个最大值对应的个数，直接线段树二分！！！！！！！
CF1967C Fenwick Tree
观察一下树状数组的结构，可以发现求一次 \(f\) 就相当于在树状数组上求子树和。
考虑一个点给距离它 \(d\) 的祖先造成了多少次贡献，可以发现是从 \(0\) 开始的序列 \(a=(1,0,0,\dots)\) 做了 \(k\) 次前缀和后的 \(a_d\)。
记 \(F^n(x)\) 表示 \(a\) 做了 \(n\) 次前缀和后的生成函数，可以发现 \(F^0(x)=1,F^i(x)=\frac{F^{i-1}(x)}{1-x}=(1-x)^{-i}\)。
提取一下系数：

\[\begin{aligned}& [x^d](1-x)^{-k}\\=& [x^d]\sum\limits_{i=0}^{+\infty}\binom{-k}{i}(-x)^i\\=& (-1)^d\binom{-k}{d}\\=& \frac{k\times(k+1)\times\dots\times(k+d-1)}{d!}\\=& \binom{k+d-1}{d} \end{aligned}\]

然后就很简单，从下往上求原序列就行。