二项式反演

<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/69c8a8ac69ecdd13d7195a665c33fe0e" alt="" /></p> <pre><code>$$g_n=\sum_{i=0}^{n}(-1)^i\times C_{n}^{i}\times f_i \Longleftrightarrow f_n = \sum_{i=0}^{n}(-1)^i\times C_{n}^{i}\times g_i$$ 设$f_i$表示恰好的方案数，$g_i$表示至多的方案数 $$g_n=\sum_{i=0}^{n}C_{n}^{i}\times f_i \Longleftrightarrow f_n = \sum_{i=0}^{n}(-1)^{n-i}\times C_{n}^{i}\times g_i$$ 设$f_i$表示恰好的方案数，$g_i$表示至少的方案数 $$g_k=\sum_{i=k}^{n}C_{i}^{k}\times f_i \Longleftrightarrow f_k = \sum_{i=k}^{n}(-1)^{i-k}\times C_{i}^{k}\times g_i$$</code></pre>