四校联考第一场的坑现在来补
这个题的母题就是联合省选A卷那一道组合数问题,可以先做那一道题再来做这一道
Sol
首先来看我们要处理的式子
$$ \sum_{i=1}^{n} \binom{n}{i}*2^{n-i}*f(i) $$
把多项式$f(i)$拆成求和的形式
$$ \sum_{i=1}^{n}\sum_{j=0}^{k}a_j i^j*2^{n-i}*\binom{n}{i} $$
把$a_j$的计算提前,并且我们对$i^j$用第二类斯特林数进行转换
$$ \sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j} \binom{i}{p}*p!*\begin{Bmatrix} j\\p\end{Bmatrix}*2^{n-i}*\binom{n}{i} $$
观察$\binom{i}{p}$和$\binom{n}{i}$两项,按照套路这两项可以换成:
$$ \sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j}p!*\begin{Bmatrix} j\\p\end{Bmatrix}*2^{n-i} * \binom{n}{p}*\binom{n-p}{i-p} $$
利用$\binom{n}{m}=\binom{n}{n-m}$对$\binom{n-p}{i-p}$进行处理
$$ \sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j}p!*\begin{Bmatrix} j\\p\end{Bmatrix}*2^{n-i} * \binom{n-p}{n-i}* \binom{n}{p} $$
如果你熟悉二项式定理推论的话:$(x+1)^n = \sum_{i=1}^{n} \binom{n}{i} * x^i$
$$ \sum_{i=1}^{n} a_j\sum_{j=0}^{k}\sum_{p=0}^{j}p!*\begin{Bmatrix} j\\p\end{Bmatrix}*3^{n-p} * \binom{n}{p} $$
好了,现在你只要$O(k^2)$地预处理斯特林数和下降幂了
最后再讲一下下降幂的计算方法
$$ n^{\underline{i}} = i!*\binom{n}{p} = \frac{n!}{i!(n-i)!} * i! = \frac{n!}{(n-i)!} = \prod_{i=n-p+1}^{n} i $$
Code
代码还是我最喜欢的环节
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 5e3 + 5;
const int mod = 998244853;
int n, k;
int S[SIZE][SIZE], pw[SIZE], a[SIZE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline int qPow(int a, int b)
{
int ans = 1;
for ( ; b; b >>= 1, a = a * a % mod) {
if (b & 1) ans = ans * a % mod;
}
return ans;
}
inline void init()
{
S[0][0] = 1;
for (register int i = 1; i <= k; ++ i) {
for (register int j = 1; j <= i; ++ j)
S[i][j] = (S[i - 1][j] * j % mod + S[i - 1][j - 1]) % mod;
}
pw[1] = qPow(3, n - k);
for (register int i = 2; i <= k + 1; ++ i) pw[i] = pw[i - 1] * 3 % mod;
}
signed main()
{
n = read(), k = read();
for (register int i = 0; i <= k; ++ i) a[i] = read();
init();
int ans = 0;
for (register int i = 0; i <= k; ++ i) {
int sum = 0, cnt = 1;
for (register int j = 0; j <= i; ++ j) {
sum = (sum + S[i][j] * pw[k - j + 1] % mod * cnt % mod) % mod;
cnt = cnt * (n - j) % mod;
}
ans = (ans + sum * a[i] % mod) % mod;
}
printf("%lld\n", ans);
return 0;
}