考场上忘了怎么拆c(a,b)*c(c,a)......
后来随便想就想出来了...
先列出答案式子：
$sum_{i=0}^{n}C_n^if(i)x^i$
f拆开
$sum_{i=0}^{n}C_n^ix^isum_{j=0}^{m}a[j]i^j$
斯特林数拆后面
$sum_{i=0}^{n}C_n^ix^isum_{j=0}^{m}a[j]sum_{k=j}^{m}s(j,k)frac{i!}{(i-k)!}$
上下乘k
$sum_{i=0}^{n}C_n^ix^isum_{j=0}^{m}a[j]sum_{k=j}^{m}k!s(j,k)frac{i!}{(i-k)!k!}$
变成组合数
$sum_{i=0}^{n}C_n^ix^isum_{j=0}^{m}a[j]sum_{k=j}^{m}k!s(j,k)C_i^k$
交换和式
$sum_{j=0}^{m}a[j]sum_{k=j}^{m}k!s(j,k)sum_{i=0}^{n}C_i^kC_n^ix^i$
考场上卡在这一步。。。
有一个公式：
$C_a^b*C_c^a=C_c^bC_{c-b}^{a-b}$
用公式化简最后的组合数：
$sum_{j=0}^{m}a[j]sum_{k=j}^{m}k!s(j,k)sum_{i=0}^{n}C_n^kC_{n-k}^{i-k}x^i$
再次变换和式
$sum_{j=0}^{m}a[j]sum_{k=j}^{m}k!s(j,k)C_n^ksum_{i=0}^{n}C_{n-k}^{i-k}x^i$
调整下界
$sum_{j=0}^{m}a[j]sum_{k=j}^{m}k!s(j,k)C_n^ksum_{i=k}^{n}C_{n-k}^{i-k}x^i$
调整后面的和式
$sum_{j=0}^{m}a[j]sum_{k=j}^{m}k!s(j,k)C_n^kx^ksum_{i=k}^{n}C_{n-k}^{i-k}x^{i-k}$
二项式展开公式：
$(x+1)^k=sum_{i=0}^{k}x^kC_k^i$
后面的和式上下界同时减去k
$sum_{j=0}^{m}a[j]sum_{k=0}^{j}k!s(j,k)C_n^kx^ksum_{i=0}^{n-k}C_{n-k}^{i}x^{i}$
二项式展开
$sum_{j=0}^{m}a[j]sum_{k=0}^{j}k!s(j,k)C_n^kx^k(x+1)^{n-k}$
问题转变求$C_{n}^{0...m}$m+1个组合数的值
如果暴力求c时间复杂度很高。
但是发现相邻两个组合数$C_{n}^{i}$和$C_{n}^{i+1}$的公式只差了两个数。分解质因数后乘积用线段树维护即可。
up:蒻智了，组合数直接转化为下降幂即可。
质因数可能较大，要离散化。
#include<bits/stdc++.h> using namespace std; #define N 1010 #define int long long int pr[N*100],vi[N*100],s[N][N],n,x,mo,m,a[N],pc,ml[N*1000],c[N],p1[N],jc[N],zy[N*2][100],ct[N*2][100],cc[N*2],po[N*100],cg,cv[N*1000],ls[N*100],cq,tt[N*100],cs[N*100],mv[N*100],p2[N]; int qp(int x,int y){ int r=1; for(;y;y>>=1,x=x*x%mo) if(y&1)r=r*x%mo; return r; } void si(){ for(int i=2;i<N*100;i++){ if(!vi[i]) pr[++pc]=i; for(int j=1;j<=pc&&i*pr[j]<N*100;j++){ vi[i*pr[j]]=1; if(i%pr[j]==0)break; } } } void bd(int o,int l,int r){ if(l==r){ ml[o]=1; mv[o]=ls[l]; return; } int md=(l+r)/2; bd(o*2,l,md); bd(o*2+1,md+1,r); ml[o]=1; } void mod(int o,int l,int r,int x,int y){ if(l==r){ cv[o]=y; ml[o]=qp(mv[o],y); return; } int md=(l+r)/2; x<=md?mod(o*2,l,md,x,y):mod(o*2+1,md+1,r,x,y); ml[o]=ml[o*2]*ml[o*2+1]%mo; } signed main(){ si(); cin>>n>>x>>mo>>m; jc[0]=1; for(int i=1;i<N;i++) jc[i]=jc[i-1]*i%mo; for(int i=0;i<N;i++){ p1[i]=qp(x+1,i); p2[i]=qp(x,i); } for(int i=0;i<=m;i++) cin>>a[i]; c[0]=1; for(int i=1;i<=m*2;i++){ int x=i; if(i>m)x=n-i+m+1; for(int j=1;pr[j]*pr[j]<=x;j++) if(x%pr[j]==0){ cc[i]++; zy[i][cc[i]]=pr[j]; ls[++cq]=pr[j]; while(x%pr[j]==0){ ct[i][cc[i]]++; x/=pr[j]; } } if(x!=1){ cc[i]++; zy[i][cc[i]]=x; ct[i][cc[i]]=1; ls[++cq]=x; } } sort(ls+1,ls+cq+1); cq=unique(ls+1,ls+cq+1)-ls-1; bd(1,1,cq); for(int i=1;i<=m*2;i++) for(int j=1;j<=cc[i];j++) zy[i][j]=lower_bound(ls+1,ls+cq+1,zy[i][j])-ls; for(int i=1;i<=m;i++){ cg=0; for(int j=1;j<=cc[i];j++){ po[++cg]=zy[i][j]; cs[zy[i][j]]-=ct[i][j]; } for(int j=1;j<=cc[m+i];j++){ po[++cg]=zy[m+i][j]; cs[zy[m+i][j]]+=ct[i+m][j]; } sort(po+1,po+cg+1); for(int j=1;j<=cg;j++) mod(1,1,cq,po[j],cs[po[j]]); c[i]=ml[1]; } for(int i=0;i<N;i++) s[i][i]=1; for(int i=1;i<N;i++) for(int j=1;j<i;j++) s[i][j]=(s[i-1][j-1]+s[i-1][j]*j%mo)%mo; int v=0; for(int j=0;j<=m;j++){ int r=0; for(int k=0;k<=j;k++) r=(r+jc[k]%mo*p1[n-k]%mo*p2[k]%mo*c[k]%mo*s[j][k]%mo)%mo; v=(v+r*a[j]%mo)%mo; } cout<<v; }