还有 50 天左右就 NOI 了，感觉状态比较糟。
1.P7275 计树
做着玩的。题目就是说，只看 \(i,i+1\) 这样的边，每一段长度都要 \(\geq 2\) 。
先考虑一种容斥：枚举实际上 \((i,i+1)\) 的集合 \(S\) ,再在剩下的 \((i,i+1)\) 中进行容斥，强制选集合 \(T\) 。
考虑包含 \(S\cup T\) 的树个数，如果现在形成了 \(k\) 段，每段是 \(a_1,...,a_k\) ，则剩下的边方案就是 \(n^{k-2}\prod a_i\) 。
现在转为枚举 \(a\) 。令 \(f_i\) 表示，把 \(i\) 分成 \(k\) 段，每段 \(\geq 2\) 的 \((-1)^{k-1}\) 之和，则对应方案为 \(n^{k-2} \prod a_if_{a_i}\) 。
\(f\) 和上述问题都可以多项式求逆解决。
2.ARC134F Flipping Coins
好题。考虑只保留 \(i<p_i\) 的边，则 \(k\) 就是长度为奇数的链的个数，把环按最小值从大到小排成一排，最小值转到最前面，这样构成了另一个排列，它和原排列形成双射。
则现在重定义 \(k\) 为长度为奇数的极长上升子段个数。由于只关心长度的奇偶，我们把每个奇段的末尾位置钦定出来。
也就是说，我们先把序列染成 \(A,B,C\) 三色，\(C\) 代表奇段的末尾，则 \(AB\) 相邻成对地出现。我们要求每个 \(A\) 值小于后面的数 ，\(C\) 大于后面的数。
在没有限制的两个位置间分界，可以把序列分成 \(C..CAB\) 的形式，它的段内方案就是 \(len-1\) 。末尾还有一段 \(C...C\) ,方案为 \(1\) 。
由此即可多项式求逆解决。
3.P8518 [IOI2021] 分糖果
把修改离线下来，对位置做扫描线，
维护一条折线，\(y_i\) 表示考虑操作 \(1\) 到 \(i\) 且不考虑卡界时，这个盒子的值是多少。
如果只被卡上界，则答案就是 \(c_i-(\max y_i-y_q)\) ，因为 \(\max y_i\) 处一定被卡，且之后一定不会再被卡。
现在有上下界，我们就想知道它到底是被哪个界卡的。考虑找到最大的 \(t\) 使得 \(t\) 到 \(q\) 这一段 \(y\) 的极差 \(\geq c_i\)。
那如果 \(y_t\) 是后缀最小值，之后就被且仅被卡上界；否则仅被卡下界。
线段树维护这个过程即可。
4.P6611 [Code+#7]六元环
手玩可以得到，建出大根笛卡尔树后答案等同于取一个大小为 \(4\) 的连通块，但不能取根。
现在要做的就是动态维护笛卡尔树。考虑建立类似于 LCT 的结构：对于每个实链，要么一直向左，要么一直向右。
现在单点加，相当于 \(x\) 要往上单旋。利用 splay 找到所在链上最大的比 \(a_x\) 小的位置，则改变的边的量是 \(O(1)\) 的。此时要么停止上旋，要么 \(x\) 会进入另一条链，继续往上。
实现起来有一些细节，比如说要把这个二叉树和维护的 splay 区分开，还要注意这个题的 LCT 与普通 LCT 的不同。复杂度 \(O(n\log n)\) 。
5.LOJ3074 「2019 集训队互测 Day 3」操作序列计数
显然 \(\le n\) 的答案 和 \(=nk\) 的答案相等。
问题相当于是要让 \(\sum a_ik^i=n-k^L\) ,求 \(a\) 的方案。先把 \(n-k^L\) 转成 \(\sum b_ik^i\) ，其中对于 \(0\le i<L\) ，\(b_i<k\) 。
则 \(a\) 可以通过在 \(b\) 上调整得到。考虑 \(dp_{i,j}\) 为：\(a_{i+1}\) 向 \(a_i\) 贡献了 \(j\) ，填 \(a_0\) 到 \(a_{i-1}\) 的方案数。
有 \(dp_{i,j}=\sum _{k=0}^{jk+b_i}dp_{i-1,k}\) 。观察可以发现 \(dp_i\) 是关于 \(j\) 的 \(i\) 次多项式。
用点值维护这个多项式，不难做到 \(O(L^3)\) ，其中 \(L\) 是 \(n\) 转成 \(k\) 进制后的位数。
标签：LCT,多项式,sum,geq,考虑,杂题,dp From： https://www.cnblogs.com/cwhfy/p/17452772.html