专栏文章

一类恒等式的应用（退役选手的杂谈）

fforeverlasting
算法·理论参与者 26已保存评论 29

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
29 条
当前快照
1 份
快照标识符
@mhz5scz1
此快照首次捕获于
2025/11/15 01:55
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文
退役后的诈尸。对，诈尸了。
推销博客（既然退役了就不推销了，虽然可能githubgithub博客有更好的观赏体验）
听说没有灵魂那就没有灵魂了。
故事的开头：
退役弱鸡选手在家里听网课，下课的时候发现一位神仙学弟吐槽了CF1097GCF1097G的一部分题解。本着无所事事的原则，随手点开看了下，发现这道题好像有点眼熟。冷静思考下发现之前noipnoip模拟赛做过一个类似的，于是给神仙学弟讲解了下我的思路，发现我的思路的确比网上大部分题解清晰一点（雾）。然后神仙学弟又说这个技术好像能解决他之前不会的CF1264D2CF1264D2，于是我又推了下那道题，发现的确可以做，而且和网上的大部分做法也有点区别。最终我就因无所事事来开了篇博客。
其实就是一条恒等式。
∑i=0t(ni)(mt−i)=(n+mt)\sum_{i=0}^t \binom{n}{i}\binom{m}{t-i}=\binom{n+m}{t}
(1)(1)
证明倒也不算复杂，构造生成函数当然是最简单的做法，从组合意义考虑隔板法也是可以的。
这条形式上来看倒也有点东西，比如说，如果n+mn+m是个定值，tt是个定值，很多式子倒是可以利用这条式子直接化简。同时这条式子可以解释类似CF1097GCF1097G的树形背包的正确性问题（可能是我太菜，我只会这样解释）。
就先拿CF1097GCF1097G来说。
把kk次幂用第二类斯特林数化简后，我们就是要求出
∑i=0ki!Ski∑s⊆U(f(s)i)\sum_{i=0}^k i!S_k^i\sum_{s\subseteq U} \binom{f(s)}{i}
至于这个式子怎么划出来，意义是什么跟这篇博客无关，所以就不详讲了。接下来我们就是要对每一个i=1,...,ki=1,...,k求出后面那个东西。好像大部分题解就是简单的带过一句背包合并吧，着重放在了说明复杂度。不过在我看来这种树上背包复杂度恐怕是路人皆知的吧，反而这样合并的正确性是重中之重。
我们直接考虑dp[x][i]dp[x][i]表示xx这个节点求ii时的贡献。转移的确就是正常的树上背包合并，但为什么是对的呢？
考虑背包合并的本质，发现就是把一堆组合数乘起来再相加。冷静整理下，发现对于每一个下标ii，我们做的是把jj和i−ji-j合并起来，即f[x][i]=∑g[j]∗f[tox][i−j]f[x][i]=\sum g[j]*f[tox][i-j]，这时再考虑(1)(1)，惊讶地发现的确会是f[x][i]f[x][i]（严谨证明可以归纳），于是就证明了这种背包合并的正确性。
这一类组合数的背包合并大概都可以用(1)(1)理解，其实还是挺有用的。
当然，组合数嘛，对于OIOI而言最大的意义还是在于化简式子吧，于是引入下CF1264D2CF1264D2这道题，看看化简式子有什么帮助。
这道题考虑下组合意义啥的，大概可以把答案写成这么一条式子
∑i=1n∑j=1nj(s0[n−i]j−s1[n−i])(s0[n]−s0[n−i]i−j−(s1[n]−s1[n−i]))\sum_{i=1}^n \sum_{j=1}^n j\binom{s0[n-i]}{j-s1[n-i]}\binom{s0[n]-s0[n-i]}{i-j-(s1[n]-s1[n-i])}
其中s0[i]s0[i]表示前缀??的个数，s1[i]s1[i]表示前缀((的个数，具体这条式子怎么出来的不是这篇博客的重点，这里就不讲了。
为了接下来方便书写，我们先写成这样子
∑i=1n∑j=1nj(A[n−i]j−p[n−i])(B[n−i]i−j−q[n−i])\sum_{i=1}^n \sum_{j=1}^n j\binom{A[n-i]}{j-p[n-i]}\binom{B[n-i]}{i-j-q[n-i]}
其中A[i]+B[i]=S,p[i]+q[i]=TA[i]+B[i]=S,p[i]+q[i]=T，S,TS,T为定值。
然后开始化简
=∑i=1n∑j=0n(j+p[n−i])(A[n−i]j)(B[n−i]i−j−T)=\sum_{i=1}^n \sum_{j=0}^n (j+p[n-i])\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}
=∑i=1n∑j=0n(j(A[n−i]j)(B[n−i]i−j−T)+p[n−i](A[n−i]j)(B[n−i]i−j−T))=\sum_{i=1}^n \sum_{j=0}^n (j\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}+p[n-i]\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T})
=∑i=1n∑j=0nj(A[n−i]j)(B[n−i]i−j−T)+∑i=1n∑j=0i−Tp[n−i](A[n−i]j)(B[n−i]i−j−T)=\sum_{i=1}^n \sum_{j=0}^n j\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}+\sum_{i=1}^n \sum_{j=0}^{i-T} p[n-i]\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}
接下来用一次(1)(1)
=∑i=1n∑j=0nj(A[n−i]j)(B[n−i]i−j−T)+∑i=1np[n−i](Si−T)=\sum_{i=1}^n \sum_{j=0}^n j\binom{A[n-i]}{j}\binom{B[n-i]}{i-j-T}+\sum_{i=1}^n p[n-i]\binom{S}{i-T}
=∑i=1n∑j=0nA[n−i](A[n−i]−1j−1)(B[n−i]i−j−T)+∑i=1np[n−i](Si−T)=\sum_{i=1}^n \sum_{j=0}^n A[n-i]\binom{A[n-i]-1}{j-1}\binom{B[n-i]}{i-j-T}+\sum_{i=1}^n p[n-i]\binom{S}{i-T}
=∑i=1n∑j=0i−T−1A[n−i](A[n−i]−1j)(B[n−i]i−j−T−1)+∑i=1np[n−i](Si−T)=\sum_{i=1}^n \sum_{j=0}^{i-T-1} A[n-i]\binom{A[n-i]-1}{j}\binom{B[n-i]}{i-j-T-1}+\sum_{i=1}^n p[n-i]\binom{S}{i-T}
再用一次(1)(1)
=∑i=1n(p[n−i](Si−T)+A[n−i](S−1i−T−1))=\sum_{i=1}^n (p[n-i]\binom{S}{i-T}+A[n-i]\binom{S-1}{i-T-1})
（写得有点复杂，我背锅）
于是就得到一条O(n)O(n)的式子了，成功地解决了此题。
同时这条式子可以对一类数进行变形，称之为DelannoyDelannoy数，写成D(n,m)D(n,m)，组合意义表示的是网格图中从(0,0)(0,0)走到(n,m)(n,m)的方案数（只走上、右、右上）。
我们直接考虑组合意义的话，可以得出D(n,m)=∑i=0n(n+m−i)!(n−i)!(m−i)!i!D(n,m)=\sum_{i=0}^n \frac{(n+m-i)!}{(n-i)!(m-i)!i!}（即枚举走ii步右上来算，这时右走了n−in-i步，上走了m−im-i步）。
我们写成组合数的形式，那么
D(n,m)=∑i=0n(n+m−in)(ni)D(n,m)=\sum_{i=0}^n \binom{n+m-i}{n}\binom{n}{i}
我们尝试用(1)(1)
D(n,m)=∑i=0n(n+m−in)(ni)D(n,m)=\sum_{i=0}^n \binom{n+m-i}{n}\binom{n}{i}
=∑i=0n(ni)∑j=0n(n−in−j)(mj)=\sum_{i=0}^n \binom{n}{i}\sum_{j=0}^n \binom{n-i}{n-j}\binom{m}{j}
=∑i=0n∑j=0n(ni)(n−in−j)(mj)=\sum_{i=0}^n \sum_{j=0}^n \binom{n}{i}\binom{n-i}{n-j}\binom{m}{j}
=∑i=0n∑j=0n(nj)(ji)(mj)=\sum_{i=0}^n \sum_{j=0}^n \binom{n}{j}\binom{j}{i}\binom{m}{j}
=∑j=0n(nj)(mj)∑i=0n(ji)=\sum_{j=0}^n \binom{n}{j}\binom{m}{j}\sum_{i=0}^n \binom{j}{i}
=∑j=0n(nj)(mj)2j=\sum_{j=0}^n \binom{n}{j}\binom{m}{j}2^j
=∑i=0n(ni)(mi)2i=\sum_{i=0}^n \binom{n}{i}\binom{m}{i}2^i
（中间用到二项式定理）
我们发现，似乎成功将D(n,m)D(n,m)换到一个不太一样的形式，但我们也不知道这样的转换有什么用。或许这对出题而言，既没有降低复杂度，也没有特殊形式，显得多余。
但这份多余，可能恰恰才是数学的魅力所在吧。
笔者水平低，随便写点东西，有错误也欢迎大家指出。

评论

共 29 条评论，欢迎与作者交流。

正在加载评论...