四校联考第一场的坑现在来补

这个题的母题就是联合省选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;
}