Re：從零開始的二項式反演

演繹推理是我們在數學中經常遇到的一些方法。對于數列來說，通過原數列計算出新的數列叫作演繹，而通過計算出的數列反推出原數列則被稱為反演。

形象化地，如果原數列為 \(g(x)\)，新數列是 \(f(x)\)，且滿足：\(\large f(x) = \displaystyle\sum^x_{k = 0}a_{x,k} \times g(k)\)

而反演就是希望我們可以通過 \(f(x)\) 來得到 \(g(x)\)，即 \(\large g(x) = \displaystyle\sum^x_{k = 0}b_{x,k} \times f(k)\)

以上式子經過結合表示為：

\(\large f(x) = \displaystyle\sum^x_{k = 0}a_{x,k} \times g(k) \Rightarrow g(x) = \displaystyle\sum^x_{k = 0}b_{x,k} \times f(k)\)

數列反演有許許多多種不同的類型，就例如莫比烏斯反演，二項式反演等等。其實，我們發現反演其實就是在解方程，一些方程組有算法上固定的、特殊的解，我們對于這些特殊的算法冠以具體的名字，就例如二項式反演。

\(\large \displaystyle\sum^{n}_{k = 0}\left(-1\right)^k\dbinom{n}{k} = \left[n = 0\right]\)

首先，當 \(n = 0\) 時，式子顯然成立。

當 \(n > 0\) 時，由二項式定理可得：\(\large \displaystyle\sum^n_{k = 0}\left(-1\right)^k\dbinom{n}{k} = \left(1 - \left(-1\right)\right)^n=0\)

證畢。

\(\large f(n) = \displaystyle\sum^n_{k=0}\dbinom{n}{k}g(k)\)

\(\large \Leftrightarrow g(n) = \displaystyle\sum^n_{k=0}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)\)

首先，我們拿出一個很顯然的式子：\(\large g(n) = \displaystyle\sum^{n}_{k = 0}\left[n - k = 0\right]\dbinom{n}{k}g(k)\)。

這應該不需要說明吧

\(\large \therefore g(n) = \displaystyle\sum^{n}_{k = 0}\left[n - k = 0\right]\dbinom{n}{k}g(n)\)

\(\large = \displaystyle\sum^{n}_{k = 0}\displaystyle\sum^{n - k}_{i = 0}(-1)^i\dbinom{n - k}{i}\dbinom{n}{k}g(k)\)

\(\large = \displaystyle\sum^{n}_{k = 0}\displaystyle\sum^{n - k}_{i = 0}(-1)^i\dbinom{n}{i}\dbinom{n - i}{k}g(k)\)

\(\large = \displaystyle\sum^{n}_{i = 0}(-1)^i\dbinom{n}{i}\displaystyle\sum^{n - i}_{k = 0}\dbinom{n - i}{k}g(k)\)

又 \(\because \large f(n) = \displaystyle\sum^n_{k=0}\dbinom{n}{k}g(k)\)

\(\large \therefore g(n) = \displaystyle\sum^{n}_{i = 0}(-1)^k\dbinom{n}{k}f(n - k)\)

注意此處将原來的 \(i\) 換成了 \(k\)，便于與原式比較。

\(\large \therefore g(n) = \displaystyle\sum^{n}_{k = 0}(-1)^{n - k}\dbinom{n}{k}f(k)\)

由于公式2、3證法與公式基礎公式大同小異（都是同樣的帶入方法，隻是求和的下界與上界不同），是以就不用證了吧（逃

\(\large f(n) = \displaystyle\sum^n_{k=m}\dbinom{n}{k}g(k)\)

\(\large \Leftrightarrow g(n) = \displaystyle\sum^n_{k=m}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)\)

\(\large f(n) = \displaystyle\sum^m_{k=n}\dbinom{k}{n}g(k)\)

\(\large \Leftrightarrow g(n) = \displaystyle\sum^m_{k=n}\left(-1\right)^{k - n}\dbinom{k}{n}f(k)\)

給定 \(n\) 個元素，相對應的就有 \(2^n\) 個集合。現在要在這 \(2^n\) 個集合中取出若幹集合，使得他們的交集的元素個數為 \(K\)，求取法的方案數。對 \(10^9+7\) 取模。

資料範圍：\(n \leq 10^6\)。

定義 \(f(x)\) 表示交集中有 \(x\) 個元素被固定選擇，剩餘元素随意選擇的方案數（不去重），定義 \(g(x)\) 表示交集恰好有 \(x\) 個元素的方案數，則有：

\(\large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k) = \dbinom{n}{x}\left(2^{2^{n - x}} - 1\right)\)

\(\large g(x) = \displaystyle\sum^n_{k = x}(-1)^{k - x}\dbinom{n}{k}f(k)\)

而答案為 \(g(K)\)。

時間複雜度 \(\Theta\left(n\right)\)。

點選檢視代碼

有 \(n\) 個糖果和 \(n\) 個藥片，将它們兩兩配對。每個糖果和藥片都有能量值。求糖果的能量大于藥片的配對恰好比藥片的能量大于糖果的配對多 \(k\) 對的方案數。對 \(10^9+7\) 取模。

資料範圍：\(n \leq 2 \times 10^3\)。\(0 \leq k \leq n\)。藥片和糖果的能量值在 <code>int</code> 範圍内，且 \(2n\) 個能量值保證互不相同。

定義 \(f(x)\) 表示保證有 \(x\) 對糖果的能量大于藥片的配對後，剩餘 \(n - x\) 對糖果和藥片随機比對的方案數（不去重），\(g(x)\) 表示恰好有 \(x\) 對糖果的能量大于藥片的配對的方案數，則有：

\(\large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k)\)

\(\large g(x) = \displaystyle\sum^n_{k=x}\left(-1\right)^{k - x}\dbinom{k}{x}f(k)\)

接下來目标即為求出 \(f(x)\) 的表達式。（其中不含 \(g(x)\)）

顯然我們需要 \(DP\)。

首先，我們對糖果和藥片按能量值從小到大排序。定義 \(dp_{i,j}\) 表示将第 \(i\) 個糖果配對後，一共有 \(j\) 對糖果的能量大于藥片的配對。根據定義，我們可以很快得出 \(\large dp_{i,j} = dp_{i - 1,j} + \left(tot_i - j + 1\right)dp_{i - 1, j - 1}\)，其中 \(tot_i\) 表示能量值比糖果 \(i\) 小的藥片數。

是以，\(\large f(x) = dp_{n,x} \cdot \left(n - x\right)!\)，答案為 \(g\left(\dfrac{n+k}{2}\right)\)。

時間複雜度 \(\Theta\left(n^2\right)\)。

小w一共買了 \(n\) 塊喜糖，發給了 \(n\) 個人，每個喜糖有一個種類。這時，小w突發奇想，如果這 \(n\) 個人互相交換手中的糖，那會有多少種方案使得每個人手中的糖的種類都與原來不同。兩個方案不同當且僅當，存在一個人，他手中的糖的種類在兩個方案中不一樣。

資料範圍：\(type_i \leq n \leq 2 \times 10^3\)。

咕咕咕……

稱一個 \(1\) ∼ \(n\) 的排列的完美數為有多少個 \(i\) 滿足 \(\left|P_i - i\right| = 1\)。

求有多少個長度為 \(n\) 的完美數恰好為 \(m\) 的排列。答案對 \(10^9 + 7\) 取模。

資料範圍：\(1 \leq n \leq 1000\)，\(0 \leq m \leq n\)。

定義 \(f(x)\) 表示強制确定 \(x\) 個位置為完美的，剩下 \(n - x\) 個位置随便放的方案數(不去重)，\(g(x)\) 為恰好有 \(x\) 個位置為完美的方案數。則有：

接下來，我們嘗試去得到 \(f(x)\)。

定義 \(dp_{i,j,0/1,0/1}\) 表示目前選到了第 \(i\) 位，一共有 \(j\) 個位置是完美的，是否已經選了 \(i\)，是否已經選了 \(i + 1\) 的方案數。

根據定義，我們可以進行分類讨論：

第 \(i\) 位是完美的：

第 \(i\) 位選 \(i - 1\)：

由狀态 \(\left(i - 1, j - 1, 0, 0\right)\) 轉移到狀态 \(\left(i, j, 0, 0\right)\)。

由狀态 \(\left(i - 1, j - 1, 0, 1\right)\) 轉移到狀态 \(\left(i, j, 1, 0\right)\)。

第 \(i\) 位選 \(i + 1\)：

由狀态 \(\left(i - 1, j - 1, 0/1, 0\right)\) 轉移到狀态 \(\left(i, j, 0, 1\right)\)。

由狀态 \(\left(i - 1, j - 1, 0/1, 1\right)\) 轉移到狀态 \(\left(i, j, 1, 1\right)\)。

第 \(i\) 位是不完美的：

由狀态 \(\left(i - 1, j, 0/1, 0\right)\) 轉移到狀态 \(\left(i, j, 0, 0\right)\)。

由狀态 \(\left(i - 1, j, 0/1, 1\right)\) 轉移到狀态 \(\left(i, j, 1, 0\right)\)。

而 \(f(x) = \left(dp_{n, x, 0, 0} + dp_{n, x, 1, 1}\right) \times \left(n - x\right)!\)，由此，我們便可以求出 \(g(x)\)。最終答案為 \(g(m)\)。

注意此時 \(dp_{i,j,0/1,0/1}\) 可以壓維成 \(dp_{0/1,,j,0/1,0/1}\)。

時間複雜度 \(\Theta \left(n^2\right)\)。