Luogu

LOJ

分析

$$
\begin{aligned}
&\sum_{k=0}^nf(k)x^k{n\choose k}\\
=&\sum_{k=0}^n\sum_{i=0}^ma_ik^ix^k{n\choose k}\\
=&\sum_{i=0}^ma_i\sum_{k=0}^nx^k{n\choose k}\sum_{j=0}^k{k\choose j}\begin{Bmatrix}i\\j\end{Bmatrix}j!\\
=&\sum_{i=0}^ma_i\sum_{j=0}^i{n\choose j}\begin{Bmatrix}i\\j\end{Bmatrix}j!\sum_{k=0}^{n-j}x^{j+k}{n-k\choose j}\\
=&\sum_{i=0}^ma_i\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}n^{\underline{j}}x^j(x+1)^{n-j}
\end{aligned}
$$

预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;
int mod;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,x,m,a[N],pw1[N],pw2[N],S[N][N];

int main() {
    n=read(),x=read(),mod=read(),m=read();
    for (int i=0;i<=m;++i) a[i]=read();
    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]+1ll*j*S[i-1][j])%mod;
    for (int i=0;i<=m;++i) pw1[i]=qpow(x,i);
    for (int i=0;i<=m;++i) pw2[i]=qpow(x+1,n-i);
    int ans=0;
    for (int i=0;i<=m;++i) {
        int now=0;
        for (int j=0,p=1;j<=i;p=1ll*p*(n-j)%mod,++j)
            now=(now+1ll*S[i][j]*pw1[j]%mod*pw2[j]%mod*p)%mod;
        ans=(ans+1ll*a[i]*now)%mod;
    }
    printf("%d\n",ans);
    return 0;
}