260820 - 260831

uoj1084 【UR #34】死亡回归

充要条件是显然的（一个节点至少有一棵子树的所有反祖边都不指向自己）。如果 dp 状态直接记录走出子树的叶子数量，需要在转移时做二项式卷积，而这本质是点值平移，因此维护点值即可。

CF1188E Problem from Red Panda

为了不算重，我们钦定存在一个位置没有操作，而这样结果序列是唯一对应操作序列的，因为两个不同但结果相同的操作序列至少相差一个全 \(1\) 序列。

考虑总共进行 \(x\) 次操作，于是第 \(i\) 个位置至少要进行 \(\lceil\frac{x-a_i}{n}\rceil\) 次操作，那么一个 \(x\) 合法，当且仅当对于任意 \(y\le x\) 都有 \(\sum \lceil\frac{y-a_i}{n}\rceil\le y\)。剩下的就是一个插板和小容斥。

P14637 [NOIP2025] 树的价值

设 \(f_{u,i,j}\) 表示 \(u\) 子树，\(\operatorname{mex}=i\)，此外有 \(j\) 个自由的节点，转移只需要把 \(j\) 卷起来，\(i\) 取 \(\max\)，随后将一些自由的点用来增加 \(i\) 的得分即可，复杂度 \(O(n^3)\)。

将转移时 \(\operatorname{mex}\) 最大的一棵子树的边描粗，形成原树的一棵链剖分，显然一个节点会选择根链中最长连续的一条重链贡献，因此可以记录到根最长的连续重链。然而不能同时记录当前和最长，由于深度不太大，可以直接枚举子树内的所有点，并钦定到当前点的路径为非严格更长的重链，用数据结构可以做到 \(O(nm\log n)\)，可以通过。

P8923 『MdOI R5』Many Minimizations

用 slope trick 刻画原问题，相当于向堆中插入两个 \(a_i\) 然后删掉最大值，答案为每次 \(mx-a_i\) 之和，也就是 \(\sum a_i~-\) 堆中剩余的数之和。考虑怎么求后者，考虑拆贡献，枚举每个 \(v\) 然后计算最终集合中 \(>v\) 的数量之和。若 \(a_i>v\) 相当于向右上走一步，若 \(a_i<v\) 相当于向右下走一步并 \(cur\gets\max(cur,0)\)。

然后把每个 \(<0\) 的位置的左边整体往上抬，转化成一个钦定碰到 \(y=0\) 但不碰到 \(y=-1\) 的格路计数：

\[ \sum_i\sum_j\sum_{x=0}^{m}ix^j(m-x)^{n-j}\left[\binom{n}{i+j}-\binom{n}{i+j+1}\right] \]

\(\sum_x x^j(m-x)^{n-j}\) 直接拉插算，之后枚举 \(i\)，复杂度 \(O(n^2)\)。

P17144 [NOI 2026] 木棉

P17145 [NOI 2026] 彩虹树

uoj1085【UR #34】摄神取念

uoj1004【UR #32】王之沉淀

不转化成 01 序列是没有前途的，经过手玩发现：删掉前缀 \(0\) 和后缀 \(1\)，一次 U 等价于删除第一个 \(1\)，一次 D 等价于删除最后一个 \(0\)，于是一定存在一个分界线，其左侧 \(1\) 都被 U 删掉，其右侧 0 都被 D 删掉，并且答案显然是所有分界线中答案最小的一个。

于是我们只关心两种操作分别进行了多少次，于是答案就是一个 \(\max_{mid}\min_i\max(\lceil\frac{lcnt}{cu}\rceil,\lceil\frac{rcnt}{cd}\rceil)\) 状物。我们对 \(\mid\) 扫描线，最优的 \(i\) 显然是单调的，于是复杂度 \(O(nk)\)。

P6620 [省选联考 2020 A 卷] 组合数问题

直接对着普通多项式做：

\[ \begin{align*} F(n,t)&=\sum_k k^tx^k\binom{n}{k}=\sum_k k^tx^k\biggl(\binom{n-1}{k-1}+\binom{n-1}{k}\biggr)\\ &=\frac{1}{n}\sum_kk^{t+1}x^k\binom{n}{k}+\sum_kk^tx^k\binom{n-1}{k}=\frac{1}{n}F(n,t+1)+F(n-1,t)\\ \end{align*} \]

于是

\[ F(n,t)=n\bigl(F(n,t-1)-F(n-1,t-1)\bigr) \]

可以 \(O(m^2)\) 求出 \(F(n,0\sim m)\)。

或者也可以转化成下降幂多项式：

\[ \sum_kk^{\underline t}x^k\binom{n}{k}=n^{\underline t}\sum_kx^k\binom{n-t}{k-t}=n^{\underline t}x^t(1+x)^{n-t} \]

P8114 [Cnoi2021] 六边形战士

把匹配边两侧的三角形合并成菱形，问题转化为用菱形覆盖六边形，这似乎是经典问题，把三种方向的菱形分别染色，图形形如一个 \(a\times b\times c\) 的立方体堆叠且两维高度分别单调。

于是对第 \(i\) 行的高度加上 \(i\)，问题转化为一个尺寸 \(a\times b\) 值域为 \(a+c\) 的半标准杨表计数。根据勾长公式，答案为

\[ \prod_{i=1}^a\prod_{j=1}^b\frac{a+c+j-i}{a+b-i-j+1} \]

化简可得原式为：

\[ \frac{f(a+b+c-1)f(a-1)f(b-1)f(c-1)}{f(b+c-1)f(a+c-1)f(a+b-1)}\\[5pt] f(n):=\prod_{i=1}^ni! \]

P7950 [✗✓OI R1] 后方之水

\[ \begin{align*} [x^s]\Bigl(\sum_{i=1} i^2x^i\Bigr)^n&=n\sum_{i=1}^{s-n+1}i^2\binom{s-i-1}{n-2}\\ &=n\sum_{i=n-2}^{s-2}(s-1-i)^2\binom{i}{n-2}\\[12pt] \sum_{i=n-2}^{s-2}(i+1)\binom{i}{n-2}&=(n-1)\sum_{i=n-2}^{s-2}\binom{i+1}{n-1}=(n-1)\binom{s}{n}\\ \sum_{i=n-2}^{s-2}(i+2)(i+1)\binom{i}{n-2}&=n(n-1)\sum_{i=n-2}^{s-2}\binom{i+2}{n}=n(n-1)\binom{s+1}{n+1}\\[12pt] ans&=ns^2\binom{s-1}{n-1}-n(n-1)(2s+1)\binom{s}{n}+n^2(n-1)\binom{s+1}{n+1}\\ &=\binom{s+1}{n+1}-\binom{s}{n+1} \end{align*} \]

P8348 「Wdoi-6」未知之花魅知之旅

发现操作可逆：+ 可以用 -- 抵消，- 可以用 +- 或者 -+ 中的一个抵消。于是考虑一对数 \((x,y)\) 能得到的字典序最小的一对数，可以用这个来判等价关系，可以通过分讨得到进行加法是没用的，于是考虑优化减法，发现减法本质是在做辗转相除，并且在 \(a-2b\ge k\) 时连续进行三次减法可以 \(a\gets a-2b\)，用这个过程优化取模即可。