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

宣传我的博客

说明

本题解整理自完整数学推导过程，重点在于如何从定义严格推出可计算的递推式， 并说明该递推如何对应到最终实现代码。$$\newcommand{\binom}[2]{{#1 \choose #2}}$$

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

简要题意

给定整数 $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} $$

核心递推式

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

边界条件

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

最终答案

$$ \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 是边界条件

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638913

$\newcommand{\binom}[2]{{#1 \choose #2}}$

大意

求$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p$的值。其中 $n$, $x$, $p$ 为给定的整数，$f(k)$ 为给定的一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$。$\binom{n}{k}$ 为组合数，其值为 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$。

思路

好题！

我们先考虑这个式子的暴力处理方式，我们发现是外层枚举 $k$，内层枚举 $f(k)$ 的k $k$，这样是 $\mathcal{O}(nm)$ 的，但是我们发现 $1 \le n \le 10 ^ 9$，但是我们的 $m$ 是 $1 \le m \le 10 ^ 3$ 的，我们首先考虑的是把复杂度中的 $n$ 化为用 $m$ 的复杂度能解决的事情。

我们发现原始的式子中，只有 $f(k)$ 是需要我们额外处理的，所以我们先看这个东西，我们考虑化简，这个时候需要用到 $k$ 次下降幂的东西，众所周知 $x ^ k = x \times x \times \ldots $，那么我们的 $x ^ {\underline{k}} = x(x - 1)(x - k + 1)$，为什么我们需要知道这个东西呢？因为我们发现 $f(k)$ 中的 $k ^ j$ 无法很好的运算，我们考虑幂的转化，即利用**第二类斯特林数**将 $x ^ k \to x ^ {\underline{k}}$，如何做呢？我们有这样的恒等式：$k ^ i = \sum_{j = 0}^{i} {i \brace j} k ^ {\underline{j}}$。

那这个时候就有人要问了，主播主播什么是**第二类斯特林数**？我们考虑组合意义，是这样的： ${i \brace j}$ 表示将 $i$ 个互不相同的球放到 $j$ 个相同的盒子里（每个盒子都不为空）的方案数。那递推式就是：${i \brace j} = {i - 1 \brace j - 1} + j \times {i - 1 \brace j}$，那这个式子我们可以用组合的方式去理解一下，就是左边的 ${i - 1 \brace j - 1}$ 就是开一个新的盒子，而右边的 $j \times {i - 1 \brace j}$ 就是用旧的盒子。

好，回到正题，我们考虑将原始的 $f(k)$ 优化代换一下，用 $k ^ {\underline{j}}$ 替代 $k ^ j$，这样的话前面会产生一个新的系数，我们将这个系数记为 $b_j$，那么 $b_j = \sum_{i = 1}^{m} a_i \times {i \brace j}$。那么我们将这个 $b_j$ 带入原式，那么我们的式子就变成了这样~~一坨~~：$\sum_{k = 0} ^ {n} (\sum_{j = 0} ^ {m} b_j k ^ {\underline{j}}) x ^ k \binom{n}{k}$

接下来，我们先交换 $k$ 与 $j$ 的枚举顺序：$\sum_{j = 0} ^ {m} b_j (\sum_{k = 0} ^ {n} k ^ {\underline{j}} x ^ k \binom{n}{k})$

接下来我我们利用**吸收公式**的 $k$ 次下降幂的形式：$k ^ {\underline{j} \binom{n}{k}} = n ^ {\underline{j} \binom{n - j}{k - j}}$

将其带入，得到：$\sum_{j = 0} ^ {m} b_j (\sum_{k = j}^{n} n ^ {\underline{j}} \binom{n - j}{k - j} x ^ k)$

我们提取一下系数：$\sum_{j = 0} ^ {m} b_j n ^ {\underline{j}} \cdot x ^ j \sum_{k = j} ^ {n} \binom{n - j}{k - j} x ^ {k - j}$

不难注意到右边是二项式定理的形式，故可以继续化简：$\sum_{j = 0} ^ {m} b_j n ^ {\underline{j}} \cdot x ^ j (x + 1) ^ {n - j}$

到这边，我们的任务就完成了，$b_j$ 可以提前 $\mathcal{O}(m ^ 2)$ 预处理出来，$n ^ {\underline{j}}$ 可以随着递推求，$x^j$ 也可以随着递推求，至于 $(x + 1)^{n - j}$ 就可以直接快速幂求了，总时间复杂度就是 $\mathcal{O}(m ^ 2)$。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXM = 1005;
#define ll long long
int n, x, p, m;
ll a[MAXM], b[MAXM];
ll S[MAXM][MAXM];

ll qpow(ll a, ll b){
	ll res = 1;
	a %= p;
	while(b){
		if(b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

int main(){
	srand(time(NULL));
    cout << rand() % 40;
	cin.tie(0) -> ios::sync_with_stdio(0);

	cin >> n >> x >> p >> m;

	for(int i = 0;i <= m;i ++) cin >> a[i];
	S[0][0] = 1;
	for(int i = 1;i <= m;i ++){
		for(int j = 1;j <= i;j ++){
			S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % p;
		}
	}

	for(int j = 0;j <= m;j ++){
		for(int i = 0;i <= m;i ++){
			(b[j] += ((a[i] * S[i][j]) % p)) %= p;
		}
	}

	ll mi = 1, ans = 0, xi = 1;
	for(int i = 0;i <= m;i ++){
		ll del = b[i];
		(del *= mi) %= p;
		(del *= xi) %= p;
		(del *= qpow(x + 1, n - i)) %= p;
		(ans += del) %= p;
//		(ans += (b[i] * mi * qpow(x, i) * qpow(x + 1, n - i))) %= p;
		(mi *= (n - i)) %= p;
		(xi *= x) %= p;
	}
	cout << (ans + p) % p << '\n';
	return 0;
}