前置技能：二项式定理
定理：\((a+b)^n=\sum_{k=0}^{n}C_{n}^{k} a^k b^{n-k}\)。
证明：（数学归纳法）
\((a+b)^1=a+b=\sum_{k=0}^{1}C_{1}^{k}a^kb^{1-k}\)。
假设，\((a+b)^m\)满足二次项定理，那么
\[(a+b)^{m+1}=(a+b)\sum_{k=0}^{m}C_{m}^{k}a^kb^{m-k}\]
\[=\sum_{k=0}^{m}C_{m}^{k}a^{k+1}b^{m-k}+\sum_{k=0}^{m}C_{m}^{k}a^kb^{m-k+1}\]
\[=\sum_{k=1}^{m+1}C_{m}^{k-1}a^{k}b^{m-k+1}+\sum_{k=0}^{m}C_{m}^{k}a^kb^{m-k+1}\]
\[=\sum_{k=0}^{m+1}C_{m}^{k-1}a^{k}b^{m-k+1}+\sum_{k=0}^{m+1}C_{m}^{k}a^kb^{m-k+1}\]
\[=\sum_{k=0}^{m+1}C_{m+1}^ka^kb^{m+1-k}\]
证毕。
二项式反演
- 一般，二项式反演解决的是哪些问题呢？
- 直接求不好求，但是至少好求；
- 直接求不好求，但是至多好求；
- \(f[i]\)表示至多有\(i\)个点的情况数，\(g[i]\)表示恰好有\(i\)个点的方案数。
- \(f[n]=\sum_{i=0}^ng[i]*C_n^i\)，那么 \(g[n]=\sum_{i=0}^n(-1)^{n-i}C_n^if[i]\)。
- 证明就是按照定义，将\(f[i]\)代入推一推。（证明略）
- 例题，今天比赛第一题的30分。
题目求把一个s<=S,分到m个盒子里，前n个盒子里的小球数量均不能超过t，并且所有盒子非空的方案数。
先二项式反演一下，设\(f[i]\)表示n个盒子里至少有i个盒子超过t的方案数，\(g[i]\)表示n个盒子里恰好有i个盒子超过t的方案数。\(g[0]=\sum_{i=0}^n(-1)^iC_n^iC_{s-it-1}^{n-1}\)。
考虑后面的\(m-n\)个盒子分配方式和去掉it之后前n个盒子是一样的。
所以总的答案为
\[\sum_{i=0}^n\sum_{k=0}^{s}C_{k-it-1}^{m-1}C_n^i(-1)^i\]
\[=\sum_{i=0}^nC_{s-it}^{m}C_n^i(-1)^i\]。
- 下面的这个组合数合并到一起非常的妙，能这么合并是因为你考虑C的组合意义。发现\(\sum_{k=0}^sC_{k-it-1}{m-1}\)其实就是将\(s-it+1\)分成m+1份的方案数。
- 如此，时间复杂度变为\(O(m+s)\)。30分get。
妈耶，集训队神题，后面的高分解法看都不敢看QAQ。