【bzoj 4870】组合数问题（DP+矩阵乘法）

2019-04-14 16:14发布

站内文章 / 模拟电子
16800 0 1770
传送门biu~
题目可以转化为从nk个物品中选出模k等于r个物品模p的方案数。
令f[i][j]代表从i个物品中选出模k等于j个物品的方案数，则f[i][j]=f[i-1][j-1]+f[i-1][j]。因为每层f[i]的值都是由f[i-1]层推过来的，所以可以用矩阵乘法优化。 #include using namespace std; int n,p,k,r; struct Matrix{ int a[55][55]; Matrix operator* (const Matrix&r)const{ Matrix tmp; for(int i=0;ifor(int j=0;j0; for(int h=0;h1ll*a[i][h]*r.a[h][j])%p; } return tmp; } }base; Matrix ksm(Matrix p,long long n){ --n;Matrix re=base; while(n){ if(n&1) re=re*p; p=p*p; n>>=1; } return re; } int main(){ scanf("%d%d%d%d",&n,&p,&k,&r); for(int i=0;i1+k)%k][i],++base.a[i][i]; Matrix ans=ksm(base,1ll*n*k); printf("%d ",ans.a[0][r]); return 0; }

热门文章