引入

二項式反演又名廣義容斥定理
二項式反演可以表示成：
$f[n]={\sum }_{i=0}^n(?1{)}^i{C}_n^i{g}_i?g_n={\sum }_{i=0}^n(?1{)}^i{C}_n^{i}f[i]$
常用表達為：
$f[n]={\sum }_{i=0}^n{C}_n^{i}g[i]?g[n]={\sum }_{i=0}^n(?1{)}^{n?i}{C}_n^{i}f[i]$
證明詳見：二項式反演理解與證明

應用

恰好和至多的轉換：
設$f[i]$表示恰好的方案數，$g[i]$表示至多的方案數，則有：$g[n]={\sum }_{i=0}^n{C}_n^i?f[i]$
根據二項式反演有：
$$f[n]=\sum _{i=0}^n(?1{)}^{n?i}?C_n^i?g_i$$
$g_i$可以在很短的時間內求出，再用g求f就得到答案

恰好和至少的轉換：
設$f(i)表示恰好有i個的方案數，g(i)至少有i個的方案數$
有式子：$g(i)={\sum }_{x=i}^n{C}_x^i?f(x)$
根據二項式反演有：
$f(i)={\sum }_{x=i}^n(?1{)}^{x?i}?C_x^i?g(x)$

球染色問題：n個球，k個顏色，求滿足相鄰顏色不同，每種顏色至少出現一次的方案數
解決方案：如果忽略每種顏色至少出現一次的限制，那么方案數就是$k(k?1{)}^{n?1}$,就是一次安排顏色，除了第一次k個隨便放，之后每次都是只能選k-1個(因為要和上一個不同)
設$f_i$表示恰好使用i種顏色的方案數。$g_k$表示n個球，用了k種顏色，不強制每種顏色必須出現的方案數。那么問題就是求$f_n$
先將函數$f$與$g$建立聯系
$$g[k]=k(k?1{)}^{n?1}=\sum _{i=0}^k{C}_k^i?f[i]$$
我們反演可得：
$f[k]={\sum }_{i=0}^k{C}_k^i?g[i]$
$f[k]={\sum }_{i=0}^k{C}_k^i?(?1{)}^{k?i}?g[i]$

例題：

hdu P1465：最不容易系列之一
luogu P4859 已經沒有什么好害怕的了
[NOI Online #2 T3]游戲

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的二项式反演(非详细)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。