总结

[BZOJ 4870]: [Shoi2017]组合数问题

传送门

DP
实际上就是要从 $nk$ 件物品里面选出若干件,使得其数量模k等于r的方案数。
可以发现 $f[n∗2,i+j]+=f[n,i]∗f[n,j]$
对dp数组做快速幂即可。
$f[i][j]$表示前i个物品选模p余j个,然后矩乘即可。
复杂度 $O(k^2log^n_2)$

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn=100010;
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-'0'+ch;ch=getchar();}
    return x*f;
}
int n,P,k,r;
struct num{
    int x[52];
    void init(){
        memset(x,0,sizeof x);
    }
}f;
num calc(const num &a,const num &b){
    num res;
    res.init();
    for(int i=0;i<=k;i++)
        for(int j=0;j<=k;j++)
            (res.x[(i+j)%k]+=(LL)a.x[i]*b.x[j]%P)%=P;
    return res;
}
num ksm(num a,LL t){
    num res;
    res.init();res.x[0]=1;
    while(t){
        if(t&1)res=calc(res,a);
        a=calc(a,a);
        t>>=1;
    }
    return res;
}
int main(){
    int i,j;
    n=read();P=read();k=read();r=read();
    f.x[0]=1;
    f.x[1%k]+=1;
    f=ksm(f,(LL)n*k);
//    for(i=0;i<=k;i++)printf("%d\n",f.x[i]);
    printf("%d\n",f.x[r]);
    return 0;
}

One comment

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注