[统一省选 2020] 组合数问题 题解

宣传我的博客

说明

本题解整理自完整数学推导过程，重点在于如何从定义严格推出可计算的递推式， 并说明该递推如何对应到最终实现代码。

注意： 本题解包含较多组合恒等式与求和变形，请耐心阅读。

---

简要题意

给定整数 $n,x,p$，以及一个 $m$ 次多项式

$$ f(k)=\sum_{i=0}^{m}a_i k^i $$

要求计算：

$$ \left(\sum_{k=0}^{n} f(k)\cdot x^k \cdot \binom{n}{k}\right)\bmod p $$

---

先说结论

定义：

$$ F(a,b)=\sum_{k=0}^{a}k^b x^k\binom{a}{k} $$

核心递推式

$$ \boxed{ F(n,m)=n\left(F(n,m-1)-F(n-1,m-1)\right) } $$

边界条件

$$ F(k,0)=(x+1)^k $$

最终答案

$$ \boxed{ \text{ans}=\sum_{i=0}^{m}a_i F(n,i) } $$

---

证明

前置公式

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

---

推导一：直接展开（$O(m^2)$）

$$ F(n,m)=\sum_{k=0}^{n}k^m x^k\binom{n}{k} $$ $$ \begin{aligned} F(n,m) &=\sum_{k=0}^{n}k^{m-1}x^k\cdot k\binom{n}{k} \\ &=\sum_{k=0}^{n}k^{m-1}x^k\cdot n\binom{n-1}{k-1} \\ &=n\sum_{k=1}^{n}k^{m-1}x^k\binom{n-1}{k-1} \end{aligned} $$ $$ F(n,m) =n\sum_{j=0}^{n-1}(j+1)^{m-1}x^{j+1}\binom{n-1}{j} $$ $$ F(n,m) =nx\sum_{j=0}^{n-1}(j+1)^{m-1}x^{j}\binom{n-1}{j} $$ $$ (j+1)^{m-1}=\sum_{i=0}^{m-1}\binom{m-1}{i}j^i $$ $$ F(n,m)=nx\sum_{i=0}^{m-1}\binom{m-1}{i}F(n-1,i) $$

---

推导二：关键递推

$$ \begin{aligned} F(n,m) &=\sum_{k=0}^{n}k^m x^k\binom{n}{k} \\ &=\sum_{k=0}^{n}k^m x^k\binom{n-1}{k} +\sum_{k=0}^{n}k^m x^k\binom{n-1}{k-1} \end{aligned} $$ $$ F(n,m)=F(n-1,m)+x\sum_{i=0}^{m}\binom{m}{i}F(n-1,i) $$ $$ F(n,m)=(1+x)F(n-1,m) +x\sum_{i=0}^{m-1}\binom{m}{i}F(n-1,i) $$ $$ x\sum_{i=0}^{m-1}\binom{m-1}{i}F(n-1,i) =F(n,m-1)-F(n-1,m-1) $$

---

最终结论

$$ \boxed{ F(n,m)=n\left(F(n,m-1)-F(n-1,m-1)\right) } $$

证毕。

---

与代码的对应关系（简述）

• f[j] 表示 $F(\cdot,j)$
• 递推式直接对应循环更新
• 初值 f[0]=(x+1)^n 是边界条件