不久前在 Discord 群看到有人在解 Codeforces 932E

然後看到這題就覺得感覺不難列出算式之後卻還是不會算

不過經由呆呆獸及他人的指導

終於理解了這類方便的方法來計算這種排列組合的題目

那就讓我們來看看這是什麼樣的方法吧

先看看 Codeforces 932E

這題的題目是這樣子的

有 $N$ 個人，你可以選任意一組集合

當你選了 $x$ 個人 ($x \ge 1$) 的集合這個集合的花費為 $x^k$

問所有選法的花費和為？（模 $10^9 + 7$）

範圍：$1 \leq N \leq 10^9$, $1 \leq k \leq 5000$

遇到這樣的題目我們應該能很輕易的列出下面這個算式

$\displaystyle \sum_{i=1}^n {\binom{n}{k} i^k}$

但接下來呢

如果我們直接跑一個 for 迴圈將總和加起來

$N \leq 10^9$ 再加上需要模運算

根本不可能解決這個問題啊？？？

換個簡單點的題目吧

大家在高中的排列組合都學會下面這個東西也就是 二項式定理

$\displaystyle (1+x)^n = \sum_{i=0}^n \binom{n}{i} x^i$

但是要怎麼讓用上面這個式子做出

$\displaystyle \sum_{i=1}^n {\binom{n}{k} i^k}$

這樣子的東西呢？

我們可以假設看看如果有個函數 $f(x) = $$\displaystyle \sum_{i=1}^n {\binom{n}{k} i^k} x^i$

那 $f(1)$ 不就會是 $\displaystyle \sum_{i=1}^n {\binom{n}{k} i^k}$ 了嗎？

會發現 $f(x)$ 與二項式定理的式子只差了 $i^k$

那如何將上面的式子推得 $f(x)$ 呢

我們會發現 $i$ 其實是二項式定理中 $x$ 的次方

我們可以想想一個問題如何將 $x$ 的次方移下來與 $x$ 相乘呢？

微分？

上面我們說到了如果我們能夠找到一個方法使得 $x$ 的次方移下來相乘

那這個方法不就是高中會學到的多項式的微分嗎？

我們可以試著先列出二項式定理的這個式子

$\displaystyle (1+x)^n = \sum_{i=0}^n \binom{n}{i} x^i$

然後 兩邊一起微分 吧

$\displaystyle n(1+x)^{n-1} = \frac{d}{dx} \sum_{i=0}^n \binom{n}{i} x^i$

什麼？你說你不會微分 Sigma？（~~回去重學微分吧~~

$\displaystyle n(1+x)^{n-1} = \sum_{i=0}^n \frac{d}{dx}(\binom{n}{i} x^i) = \sum_{i=0}^n i \times \binom{n}{i} x^{i-1}$

這樣一來右邊的式子就出現 $i$ 了！

但我們想要的是 $i^k$

假如我們繼續微分會發現移下來的會是 $i-1, i-2, i-3, …$

但如果我們兩邊同乘上 $x$ 之後再微分呢？

因此整個過程就變成了一個對二項式定理微分＝> 乘以 $x$ ＝> 微分＝> … 的一個循環過程

實際操作一遍吧！

求 $\displaystyle \sum_{i=0}^n {\binom{n}{i} i^2}$ 的一般式為何？

遇到這樣的問題我們就可以來試試看使用剛剛的技巧

也就是不停的微分再乘上 $x$

從這個式子 $\displaystyle (1+x)^n = \sum_{i=0}^n \binom{n}{i} x^i$

微分＝> $\displaystyle n(1+x)^n = \sum_{i=0}^n \binom{n}{i} x^{i-1} \times i$

乘以 $x$ ＝> $\displaystyle nx(1+x)^{n-1} = \sum_{i=0}^n \binom{n}{i} x^i \times i$

微分＝> $\displaystyle (n(1+x)^{n-1})(x)’ + (n(1+x)^{n-1})’(x) = \sum_{i=0}^n \binom{n}{i} x^{i-1} \times i^2$

＝> $\displaystyle n(1+x)^{n-1} + n(n-1)(1+x)^{n-2}x = \sum_{i=0}^n \binom{n}{i} x^{i-1} \times i^2$

乘以 $x$ ＝> $\displaystyle n(1+x)^{n-1} x+ n(n-1)(1+x)^{n-2}x^2 = \sum_{i=0}^n \binom{n}{i} x^{i} \times i^2$

代入 $1$ ＝> $\displaystyle n \times 2^{n-1} + n（n-1)\times 2^{n-2} = \sum_{i=0}^n \binom{n}{i}\times i^2$

化簡＝> $2^{n-2}n(n+1) = \displaystyle \sum_{i=0}^n {\binom{n}{i} i^2}$

得 $2^{n-2}n(n+1)$ 為 $\displaystyle \sum_{i=0}^n {\binom{n}{i} i^2}$ 的一般式

回到原題

扯了那麼多讓我們回到原來的題目吧

$\displaystyle \sum_{i=1}^n {\binom{n}{k} i^k}$

你可能會想說就只要微分再乘上 $x$ 的操作做 $k$ 次對吧

但如何做到呢？

我們必須要寫個程式來 模擬微分的運算！

也就是使用 DP 來模擬！

我們可以記下每一項 $(1+x)^{n-i} x^i$ 的係數

用 $dp[i][j]$ 來表示到第 $i$ 次時 $(1+x)^{n-j} x^j$ 的係數

但微分要怎麼做呢?

我們可以再試一次看看把上面練習題的兩次微分後的式子再拿來微分看看

$\displaystyle n(1+x)^{n-1} x+ n(n-1)(1+x)^{n-2}x^2$

微分後

$\displaystyle n(1+x)^{n-1}+ n(n-1)(1+x)^{n-2}x + n(n-1)(1+x)^{n-2}\times 2x + n(n-1)(n-2)(1+x)^{n-2}x^2$

乘以 $x$

$\displaystyle (1n)(1+x)^{n-1}x+ (n \times (n-1) +2n(n-1))(1+x)^{n-2}x^2+ (n(n-1)\times(n-2) + 3 \times 0)(1+x)^{n-2}x^3$

觀察出來了嗎如果還沒那我們假設係數都是未知數

$\displaystyle C_1(1+x)^{n-1} x+ C_2(1+x)^{n-2}x^2 + C_3(1+x)^{n-2}x^3 + …$

微分後乘以 $x$

$(1 \times C_1)(1+x)^{n-1}x + (C_1 \times (n-1) + 2 \times C_2)(1+x)^{n-2}x^2 + (C_2 \times (n-2) + 3 \times C_3)(1+x)^{n-2}x^3 + …$

規律就出現了

DP 模擬微分以及程式碼

既然推得了規律那我們來看看轉移式要怎麼列吧

$dp[i][j]$ 表示到第 $i$ 次操作時 $(1+x)^{n-j} x^j$ 的係數

轉移式由規律可寫成

$dp[i+1][j] = dp[i+1][j] + dp[i][j] \times j$

$dp[i+1][j+1] = dp[i+1][j+1] + dp[i][j] \times (n-j)$

因此我們就可以得到該題的程式碼（記得進行模運算

for(int i = 1;i < k;i++){
    for(int j = 1;j <= i;j++){
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * j % MOD) % MOD;
        dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * (n-j) % MOD) % MOD;
    }
}
for(int i = 1;i <= k;i++){
    ans = (ans + fastpow(2,n-i) * dp[k][i] % MOD) % MOD;
}

二項式機率也能做一樣的事情嗎？ Codeforces 1278F

這裡又有另一道例題了 Codeforces 1278F

題意

桌上有 $m$ 張牌（其中一張是鬼牌），你可以抽 $n$ 次

假如抽到鬼牌的期望值是 $x$，問 $x^k$ 為何？

由於每一次抽鬼牌都是獨立的事件

$E(X+Y) = E(X) + E(Y)$

因此我們可以將每一次抽到鬼牌的次數相加

而期望值 = 機率 $\times$ 次數

任何有學過高中排列組合的人都知道二項式機率的算法為 $\displaystyle \binom{n}{i} p^i q^{n-i}$

我們可以列出這個式子 $\displaystyle \sum_{i=0}^n \binom{n}{i} p^i q^{n-i} i^k$

那麼再來推式子吧

$\displaystyle(p+q)^n = \sum_{i=0}^n \binom{n}{i} p^i q^{n-i}$

我們要如何讓這個式子推出上面的式子呢？

很簡單原本我們是先微分再乘以 $x$

現在我們只要先微分之後再乘以 $p$ 就好了

由於 $p+q=1$ 因此結果非常漂亮

推導過程與前一例題相同我們則不證明留給讀者當作練習

附上程式碼

m = fastpow(m,MOD-2);
for(int i = 1;i < k;i++){
    for(int j = 1;j <= i;j++){
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * j % MOD) % MOD;
        dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * (n-j) % MOD) % MOD;
    }
}
for(int i = 1;i <= k;i++){
    ans = (ans + fastpow(m,n-i) * dp[k][i] % MOD) % MOD;
}

心得

在競程當中使用到微積分真的是讓我滿驚訝的

但是同時這個方法也非常神奇且好用

實作的程式碼也非常短

雖然這個方法在競程上可能比較少會看到

但是以後如果遇到含有二項式的有限級數

我們就可以使用這個方法來找到一般式了！

聽說這個方法在生成函數是個滿常見的方式不過我還沒學

所以先將這個方法歸納在這裡至於這個方法的名稱我查好久都找不到

唯一找到的只有這個影片稱其為 Finite Series With Binomial Coefficient

所以我就直翻成中文了 XD