题目大意:给出长度为n的序列,求出m次前缀和后每一项的值(mod p)。
数据范围:n<=1e3 , m<=1e18 , ai <= 1e9 , p<1e5且p为质数。
正解Lucas定理,在这里提一下:
C(n,m)%p = C(n/p,m/p)*C(n%p,m%p)%p
伪代码:
ll C(int x,int y) { if(x>y)return 0; ll ans = jc[y]; ans = (ans * jny[x])%p; ans = (ans * jny[y-x])%p; return ans; } ll lucas(int x,int y) { if(x<p&&y<p)return C(x,y); return C(x%p,y%p)*lucas(x/p,y/p)%p; }
然而我考试时并没有想到lucas……(面壁)
于是半个机房的人用普通的前缀积和逆元a了……
注意:m要取模!!!(一个取模干掉我50分)
代码:
#include<cstdio> #define N 1005 #define ll long long int n,p; ll m; ll ny[2000006],jc[2000005],jcn[2000005]; ll a[N]; ll C(int x,int y) { ll ans = jc[y]; ans = (ans*jcn[x])%p; ans = (ans*jcn[y-x])%p; return ans; } ll k[N]; int main() { freopen("b.in","r",stdin); freopen("b.out","w",stdout); scanf("%d%I64d%d",&n,&m,&p); m%=p; ny[0]=ny[1]=jc[1]=jcn[0]=jcn[1]=1; for(int i=2;i<=2000000;i++) { ny[i]=((p-p/i)*ny[p%i]%p+p)%p; jc[i]=(jc[i-1]*i)%p; jcn[i]=(jcn[i-1]*ny[i])%p; } for(int i=1;i<=n;i++)scanf("%I64d",&a[i]); k[0]=1; for(int i=1;i<=n;i++) { k[i]=k[i-1]*(i+m-1)%p*ny[i]%p; } for(int i=1;i<=n;i++) { ll as = 0; for(int j=1;j<=i;j++) { as = (as + k[i-j]*a[j]%p)%p; } printf("%I64d ",as); } printf(" "); fclose(stdin); fclose(stdout); return 0; }