[省选联考 2020 A 卷] 组合数问题
\(\frak{Description}\)
\(\rm Link.\)
\(\frak{Solution}\)
当时拿到这道题的第一想法就是将多项式 \(f(k)\) 拆成单项式，然后就死了。（但是题解区有巨佬用单项式和纯组合数学搞出来了，我是 \(\rm joker\).
将 \(f(k)=\sum_{i=0}^m a_ik^i\) 转化成 \(f(k)=\sum_{i=0}^m b_ik^\underline i\). 但是你要问我怎么想到普通幂转下降幂多项式，我真的不能解释，可能需要多做题吧。由于 \(k^i\) 和 \(\binom{n}{k}\) 之间没有什么公式，枚举复杂度直接 \(\mathcal O(nm)\)，但我们又有 \(\binom{n}{k}\cdot k^{\underline i}=\binom{n-i}{k-i}\cdot n^{\underline i}\)，所以原式
此时 \(b_in^\underline i\) 已经是可接受的复杂度了，所以调换求和符号，尝试对组合数和 \(x^k\) 进行化简
\[\sum_{i=0}^mb_in^\underline i\cdot \sum_{k=0}^n x^k\cdot \binom{n-i}{k-i} \]这有点像二项式定理（蛤？你确定），所以枚举 \(k-i\)
\[\sum_{i=0}^mb_in^\underline i\cdot \sum_{k=0}^{n-i} x^{k+i}\cdot \binom{n-i}{k}=\sum_{i=0}^mb_in^\underline ix^i\cdot \sum_{k=0}^{n-i} x^{k}\cdot \binom{n-i}{k} \]所以
\[\text{Ans}=\sum_{i=0}^mb_in^\underline ix^i\cdot (x+1)^{n-i} \]现在只要求出 \(b_i\) 就将问题解决了。普通幂转下降幂多项式用第二类斯特林数，所以有
\[\begin{align} \sum_{i=0}^m a_ik^i&=\sum_{i=0}^m a_i\cdot \sum_{j=0}^i \text{S}(i,j)\cdot k^\underline j\\ &=\sum_{j=0}^m k^\underline j\cdot \sum_{i=j}^m \text{S}(i,j)\cdot a_i \end{align} \]所以 \(\mathcal O(m^2)\) 预处理第二类斯特林数，再 \(\mathcal O(m^2)\) 递推即可得知 \(b_i\).
\(\frak{Code}\)
# include
# include
# define print(x,y) write(x), putchar(y)
template
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp]=x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}
const int maxn = 1005;
int S[maxn][maxn];
int n,x,p,m,a[maxn],b[maxn];
inline int qkpow(int x,int y) {
int r=1;
for(; y; y>>=1, x=1ll*x*x%p)
if(y&1) r=1ll*r*x%p;
return r;
}
int main() {
n=read(9), x=read(9), p=read(9), m=read(9);
for(int i=0;i<=m;++i) a[i]=read(9);
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]%p)%p;
for(int j=0;j<=m;++j) for(int i=j;i<=m;++i)
b[j] = (b[j]+1ll*S[i][j]*a[i]%p)%p;
int ans=0, tmp=1, tmpx=1;
for(int i=0;i<=m;++i)
ans = (ans+1ll*b[i]*tmp%p*tmpx%p*qkpow(x+1,n-i)%p)%p,
tmp = 1ll*tmp*(n-i)%p, tmpx = 1ll*tmpx*x%p;
print(ans,'\n');
return 0;
}