当前位置：首页 > news >正文

做题记录5 —— 2026.6

news 2026/6/4 22:38:10

做题记录5 —— 2026.6

P4719 【模板】动态 DP

[动态dp] [树链剖分]

先写一下方程，简单的 \(f(i, 0) = \sum\limits_j\max(f(j, 0), f(j, 1)), f(i, 1) = \sum\limits_j f(j, 0) + a_i\)。

想办法将其转为矩阵的形式

\[\begin{bmatrix} f_{u, 0} , f_{u, 1} \end{bmatrix} = \begin{bmatrix}f'_{u,0},f'_{u, 1} \end{bmatrix}\times \begin{bmatrix}\max(f_{v, 0}, f_{v, 1}), -\infty \\ -\infty,f_{v, 0} \end{bmatrix} \]

但是发现这样根本就处理不了转移。

不行的原因在于，修改了一个点后，影响了到根的路径上所有的转移矩阵。

引入一个思想，对于轻重儿子分别处理。

可以知道的是，使用树剖后只有 \(\log{n}\) 次轻儿子 \(\to\) 父亲的更新，和 \(\log{n}\) 段重链中重儿子 \(\to\) 父亲的更新。

这需要轻儿子不影响重儿子的信息。

考虑改写一下 dp 设计，\(g_u\) 表示只考虑一个点轻儿子的 dp 值，于是

\[\begin{array}{l} f_{u, 0} = g_{u, 0} + \max(f_{v, 0}, f_{v, 1})\\ f_{u, 1} = g_{u, 0} + a_u + f_{v, 0} \end{array} \]

将 \(g\) 视为自身参数，写出矩乘形式有

\[\begin{bmatrix} f_{u, 0}, f_{u, 1} \end{bmatrix} = \begin{bmatrix} f_{v, 0}, f_{v, 1} \end{bmatrix}\times \begin{bmatrix} g_{u, 0}, g_{u, 1}\\ g_{u, 0}, -\infty \end{bmatrix} \]

然后更新的时候就是连接两个重链的一个轻儿子，由于此时没有重儿子，于是 \(\begin{bmatrix} f_{u, 0}, f_{u, 1} \end{bmatrix} = \begin{bmatrix} \max(g_{u, 0}, g_{u, 1}), g_{u, 0} \end{bmatrix}\)。

发现，这样轻儿子更新一下 \(g\gets g + \Delta\) 就行了，重儿子像序列上那样处理就行了。

P13790 「CZOI-R6」Border

[exKMP] [字符串哈希]

考虑将 border 长度小于等于一半串长和大于的分开讨论。

如果小于等于，两个串是分开的。

考虑枚举 border 长度，判断是否只有一个位置不同。

这个可以先求出两端的 lcp，然后判断 lcp 后的部分是否相等，这个 exKMP 和字符串哈希就行了。

然后如果 border 长度大于一半串长，那就不能这么做，因为修改可能影响两个串。

这里 border 有两个，修改的话修改靠后的位置，不然会破坏原来的相等，剩下自己讨论一下就行了。

复杂度线性。

CF1278F Cards

[斯特林数] [期望] [组合计数] [二项式定理]

考虑枚举王牌出现了多少次。

\[\begin{aligned} E(x^k) &= \sum_{i = 0}^n i^k \binom ni (\frac 1m)^i (\frac{m - 1}m)^{n - 1}\\ &= \sum_{i = 0}^n i^k \binom ni \frac{(m - 1)^{n - i}}{m^n} = \frac 1{m^n} \sum_{i = 0}^n i^k \binom ni (m - 1)^{n - i} \end{aligned} \]

考虑用斯特林数展开 \(i^k\) 的贡献，就是 \(\sum_{j = 0}^i {k \brace j} i^{\underline{j}}\)。

\[\begin{aligned} E(x^k) &= \frac 1 {m^n} \sum_{i = 0}^n \binom ni (m - 1)^{n - 1} \sum_{j = 0}^i {k \brace j} i^{\underline{j}}\\ &=\frac 1 {m^n} \sum_{i = 0}^n \binom ni (m - 1)^{n - 1} \sum_{j = 0}^i {k \brace j} \binom ij j!\\\end{aligned} \]

考虑这样，\(\binom ni \binom ij = \binom nj \binom {n - j}{i - j}\)，然后式子可以用二项式定理合并。

\[\begin{aligned} E(x^k)&=\frac 1 {m^n} \sum_{i= 0}^n \sum_{j = 0}^i {k \brace j} j! \binom nj \binom{n - j}{i - j} (m - 1)^{n - i}\\ &= \frac 1{m^n} \sum_{j = 0}^k {k \brace j} j! \binom nj \sum_{i =0}^n \binom{n - j}{i - j} (m - 1)^{n - i}\\ \end{aligned} \]

单独拿出 \(\sum_{i =0}^n \binom{n - j}{i - j} (m - 1)^{n - i}\)，推一下这等于 \(\sum_{i = j}^n (m - 1)^{n - i} \binom {n - j}{i - j}\)，这里从 \(j\) 开始是组合数都有负数了肯定是 \(0\)。

然后考虑整体下移 \(j\)，有 \(\sum_{i = 0}^{n - j} (m - i) ^{n - j - i} \binom {n - j}{i} 1^{i} = m^{n - j}\)。

终于得到答案

\[E(x^k) = \frac 1{m^n} \sum_{j = 0}^k {k\brace j}j! \binom nj m^{n - j} = \frac 1{m^n} \sum_{j = 0}^k {k\brace j} m^{n - j} n^{\underline{j}} \]

然后递推预处理斯特林数，由于这已经 \(n^2\)，其他的直接快速幂就行了。

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