[省选联考 2020 A 卷] 组合数问题
常用手法
[{nchoose k} k^{underline m}={{n-m}choose {k-m}} n^{underline m}
]
[(sum_{k=0}^n f(k) imes x^k imes {nchoose k}) mod p
]
[sum_{i=0}^m a_i k^i=sum_{j=0}^m b_i k^{underline i}
]
通过第二类斯特林数转下降幂。
[x^n=sum_{i=0}^x {xchoose i}S(x,i) i!= sum_{i=0}^x S(n,i) x^{underline i}\
egin{aligned}
sum_{i=0}^m a_i k^i&=sum_{i=0}^m a_i sum_{j=0}^ k S(i,j)x^{underline j}\
&= sum_{j=0}^ k x^{underline j} sum_{i=j}^m a_i S(i,j)\
&= sum_{i=0}^ k x^{underline i} sum_{j=i}^m a_j S(j,i)\
end{aligned}\
b_i=sum_{j=i}^m a_j S(j,i)
]
(O(m^2)) 暴力递推，转下降幂，用上面那个方法转，然后交换求和顺序，二项式定理。
[egin{aligned}
sum_{k=0}^n f(k)x^k {nchoose k}&=sum_{k=0}^n x^k {nchoose k}sum_{i=0}^m b_i k^{underline i}\
&=sum_{k=0}^n x^k sum_{i=0}^m b_i k^{underline i}{nchoose k}\
&=sum_{k=0}^n x^k sum_{i=0}^m b_i n^{underline i}{n-ichoose k-i}\
&= sum_{i=0}^m b_i n^{underline i}sum_{k=0}^n x^k {n-ichoose k-i}\
&= sum_{i=0}^m b_i n^{underline i}sum_{k=0}^{n-i} x^{k+i} {n-ichoose k}\
&= sum_{i=0}^m b_ix^i n^{underline i}sum_{k=0}^{n-i} x^{k} {n-ichoose k}\
&= sum_{i=0}^m b_ix^i n^{underline i}{(x+1)}^{n-i}
end{aligned}
]
(O(m))
/*
繁华落尽，我心中仍有花落的声音。一朵，一朵，在无人的山间，轻轻飘落。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010, inf=0x3f3f3f3f;
int n, x, p, m, a[N], b[N], S[N][N];
inline int read(){
int x = 0, f = 1; char ch=getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int power(int x, int y){
ll ret = 1;
while(y){
if(y & 1) ret = 1ll * ret * x % p;
x = 1ll * x * x % p; y >>= 1;
}
return ret;
}
int main(){
//freopen("ex.in", "r", stdin);
//freopen("ex.out", "w", stdout);
n = read(); x = read(); p = read(); m = read();
for(int i = 0; i <= m; i++) a[i] = read();
S[0][0]=1 % p;
S[1][1]=1 % p;
for(int i = 2; i <= m; i++)
for(int j = 1; j <= i; j++)
S[i][j] = (1ll * j * S[i-1][j] % p + S[i-1][j-1]) % p;
for(int i = 0; i <= m; i++)
for(int j = i; j<= m; j++)
b[i] = (b[i] + 1ll * S[j][i] * a[j] % p) % p;
int sx = 1, sn = 1, ans = 0;
x = x % p;
for(int i = 0; i <= m; i++){
ans = (ans + 1ll * b[i] * sx % p * sn % p * power((x + 1) % p, n - i) % p) % p;
sx = 1ll * sx * x % p;
sn = 1ll * sn * (n - i) % p;
}
printf("%d
", ans);
return 0;
}