Link

一道题目=解锁$inf$知识点

前置知识

下降幂:

$$ n^{\underline k} = \binom{n}{k}*k! $$

二项式定理：

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

并且我们注意到当$y=1$时，$(x+1)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} $

第二类斯特林数：$S(n,k) = S(n - 1,k-1) + k * S(n-1,k)$

重要等式

$$ \binom{n}{m} = \binom{n}{n - m} $$

$$ x^k = \sum_{i=0}^{k} \binom{x}{i} * S(k,i) * i! $$

解释：$x^k$相当于把$k$个小球放进$x$个盒子里（允许空盒），那么方案就是枚举不空的盒子个数 × 小球放进去的方案数 × 盒子标号不同（不懂就私聊

Sol

解决完以上前置知识，我就花了小半小时（菜

看题目要我们解决的式子：

$$ \sum_{k = 0}^{n} f(k)*x^k*\binom{n}{k} $$

$f(k)$是一个$m$次多项式，我们可以写成：

$$ \sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * k^{i} * \binom{n}{k} * x^{k} $$

把$k^i$用上面的恒等式替换

$$ \sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * \sum_{p=0}^{i} S(i,p) * \binom{k}{p} * p! * \binom{n}{k} * x^k $$

观察到 $\binom{k}{p}$和$\binom{n}{k}$ 两项拆成阶乘形式：

$$ \frac{k!}{p!(k-p)!} * \frac{n!}{k!(n-k)!} $$

同时消去$k!$，再同乘$\frac{(n-p)!}{(n-p)!} = 1$等式仍然成立：

$$ \frac{n! (n-p)!}{p!(n-p)!(n-k)!(n-p)!} = \binom{n}{p}*\binom{n-p}{k-p} $$

所以此时式子变成了：

$$ \sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} * \sum_{p=0}^{i} S(i,p) * \binom{n}{p} * \binom{n-p}{k-p} * p! * x^k $$

我们将所有的求和限制提前，并且对每一项的顺序稍作改变：

$$ \sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{p=0}^{i} \binom{n-p}{n-k} * x^k * a_i * S(i,p) * p! * \binom{n}{p} $$

对二项式定理上面那个等式熟悉的话，我们感觉$\binom{n-p}{n-k}$和$x^k$可以合并。我们需要将$x$的指数稍作修改

$$ \sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{p=0}^{i} \binom{n-p}{n-k} * x^{k-p} * x^p * a_i * S(i,p) * p! * \binom{n}{p} $$

此时可以合并

$$ \sum_{i=0}^{m} \sum_{p=0}^{i} (x+1)^{n-p} * x^p * a_i * S(i,p) * p! * \binom{n}{p} $$

至此，$(x+1)^{n-p}$和$x^p$两项均可通过快速幂计算，第二类斯特林数通过$O(m^2)$打表，$p!$和$\binom{n}{p}$可以一起计算

没了

Code

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

#define int long long

const int SIZE = 1e3 + 5;

int n, x, p, m;
int a[SIZE], frac[SIZE], s[SIZE][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;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans % p;
}

signed main()
{
    n = read(), x = read(), p = read(), m = read();
    for (int i = 0; i <= m; ++ i) a[i] = read();
    s[0][0] = 1;
    for (register int i = 1; i <= m; ++ i) {
        for (register int j = 1; j <= i; ++ j) 
            s[i][j] = (s[i - 1][j - 1] + 1ll * j * s[i - 1][j] % p) % p;
    }
    int ans = 0;
    for (register int i = 0; i <= m; ++ i) {
        frac[i] = qPow(x + 1, n - i);
        for (register int j = i - 1; j >= 0; -- j)
            frac[j] = frac[j + 1] * (x + 1) % p;
        for(register int j = 0, val1 = 1, val2 = 1; j <= i; ++ j, val1 = 1ll * val1 * (n - j + 1) % p, val2 = 1ll * val2 * x % p)
            ans = (ans + 1ll * a[i] * s[i][j] % p * val1 % p * val2 % p * frac[j] % p) % p;
    }
    printf("%lld\n", ans % p);
    return 0;
}