P6620组合数问题如何转化为？
摘要：P6620 [省选联考 2020 A 卷] 组合数问题 大意 求 [left(sum_{k=0}^{n}f(k)times x^ktimes binom{n}{k}right)bmod p ]的值。其中 (n), (
P6620 [省选联考 2020 A 卷] 组合数问题
大意
求
\[\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\)，这样是 \(\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) \ldots (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;
}