组合数问题
首先明确下降幂即
\[k^{\underline m}=\sum_{i=k-m+1}^ki \]不难发现有
\[\binom{n}{k}k^{\underline m}=\binom{n-m}{k-m}n^{\underline m} \]我们尝试把普通幂多项式转为下降幂多项式
\[\sum_{i=0}^ma_i k^i=\sum_{i=0}^m b_i k^{\underline i} \]由第二类斯特林数的性质我们有
\(k^n=\sum_{i=0}^n\) $n \brace i $ \(k^{\underline i}\)
那么
\(\sum_{i=0}^ma_i k^i\)=\(\sum_{i=0}^ma_i\sum_{j=0}^i\) \(i \brace j\) \(k^{\underline j}\)
=\(\sum_{j=0}^mk^{\underline j}\) \(\sum_{i=j}^m\) \(i \brace j\) \(a_i\)
那么我们就可以 \(\Omicron(m^2)\) 求出 b
对于整个式子在用上面提到的结论代换即可(xiebuwanle
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1005;
#define ll long long
ll n,x,Mod,m,a[MAXN],b[MAXN],dp[MAXN][MAXN],tmp,va[MAXN],op,res,vv[MAXN];
void init(){
dp[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=i;j++){
dp[i][j]=(dp[i-1][j-1]+1LL*j*dp[i-1][j])%Mod;
}
}
}
ll ksm(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%Mod;a=a*a%Mod;b>>=1;
}return res;
}
int main(){
scanf("%lld%lld%lld%lld",&n,&x,&Mod,&m);op=1;init();vv[0]=1;
for(int i=0;i<=m;i++){
scanf("%lld",&a[i]);
if(i>0) vv[i]=vv[i-1]*x%Mod;
}
for(int i=0;i<=m;i++){
for(int j=i;j<=m;j++){
b[i]=(b[i]+dp[j][i]*a[j]%Mod)%Mod;
}
}
for(int i=0;i<=m;i++){
res=(res+(op*b[i]%Mod*vv[i]%Mod*ksm(x+1,n-i)%Mod))%Mod;op=op*(n-i)%Mod;
}
printf("%lld",res);
}/*
g++ 111.cpp -o 111
./111
*/