二项式反演

前置技能：二项式定理

定理：$(a+b)^n=\sum_{k=0}^{n}C_{n}^{k} a^k b^{n-k}$(a+b)n=∑k=0n​Cnk​akbn−k。

证明：（数学归纳法）

• $(a+b)^1=a+b=\sum_{k=0}^{1}C_{1}^{k}a^kb^{1-k}$(a+b)1=a+b=∑k=01​C1k​akb1−k。

• 假设，$(a+b)^m$(a+b)m满足二次项定理，那么

  $(a+b)^{m+1}=(a+b)\sum_{k=0}^{m}C_{m}^{k}a^kb^{m-k}$(a+b)m+1=(a+b)k=0∑m​Cmk​akbm−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}$=k=0∑m​Cmk​ak+1bm−k+k=0∑m​Cmk​akbm−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}$=k=1∑m+1​Cmk−1​akbm−k+1+k=0∑m​Cmk​akbm−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}$=k=0∑m+1​Cmk−1​akbm−k+1+k=0∑m+1​Cmk​akbm−k+1

  $=\sum_{k=0}^{m+1}C_{m+1}^ka^kb^{m+1-k}$=k=0∑m+1​Cm+1k​akbm+1−k

  证毕。

二项式反演

• 一般，二项式反演解决的是哪些问题呢？

  • 直接求不好求，但是至少好求；
  • 直接求不好求，但是至多好求；

• $f[i]$f[i]表示至多有$i$i个点的情况数，$g[i]$g[i]表示恰好有$i$i个点的方案数。

• $f[n]=\sum_{i=0}^ng[i]*C_n^i$f[n]=∑i=0n​g[i]∗Cni​，那么 $g[n]=\sum_{i=0}^n(-1)^{n-i}C_n^if[i]$g[n]=∑i=0n​(−1)n−iCni​f[i]。

• 证明就是按照定义，将$f[i]$f[i]代入推一推。（证明略）

• 例题，今天比赛第一题的30分。

• 题目求把一个s<=S,分到m个盒子里，前n个盒子里的小球数量均不能超过t，并且所有盒子非空的方案数。

• 先二项式反演一下，设$f[i]$f[i]表示n个盒子里至少有i个盒子超过t的方案数，$g[i]$g[i]表示n个盒子里恰好有i个盒子超过t的方案数。$g[0]=\sum_{i=0}^n(-1)^iC_n^iC_{s-it-1}^{n-1}$g[0]=∑i=0n​(−1)iCni​Cs−it−1n−1​。

• 考虑后面的$m-n$m−n个盒子分配方式和去掉it之后前n个盒子是一样的。

• 所以总的答案为

  $\sum_{i=0}^n\sum_{k=0}^{s}C_{k-it-1}^{m-1}C_n^i(-1)^i$i=0∑n​k=0∑s​Ck−it−1m−1​Cni​(−1)i

  $=\sum_{i=0}^nC_{s-it}^{m}C_n^i(-1)^i$=i=0∑n​Cs−itm​Cni​(−1)i。

• 下面的这个组合数合并到一起非常的妙，能这么合并是因为你考虑C的组合意义。发现$\sum_{k=0}^sC_{k-it-1}^{m-1}$∑k=0s​Ck−it−1m−1​其实就是将$s-it$s−it分成m份的方案数。

• 如此，时间复杂度变为$O(m+s)$O(m+s)。30分get。

• 妈耶，集训队神题，后面的高分解法看都不敢看QAQ。