bzoj4870&luogu3746 [六省联考2017]组合数问题

​​http://www.elijahqi.win/archives/622​​

题目的大意就是要求我们从n*k个数字中选择%k余r的方案数

定义f(i,j)=∑∞t=0Cj+tki

f(i,j)=f(i−1,j)+f(i−1,(j−1) mod k)

这道题我们转移是用状态转移因为每次都是前一个i-1转移过来的

不妨设当前状态

1 2 3 4 5 6

a b c d e f

那么我们开一个矩阵可以知道

1 2 3 4 5 6

1 1 1

2 1 1

3 1 1

4 1 1

5 1 1

6 1 1

#include<cstdio>
#include<cstring>
#define N 55
struct matrix{
    int f[N][N],l,c;
}ans,m;
int n,p,k,r;
inline matrix multiply(matrix a,matrix b){
    matrix c;memset(c.f,0,sizeof(c.f));
    c.l=a.l;c.c=b.c;
    for (int i=0;i<a.l;++i)
        for (int j=0;j<b.c;++j)
            for (int z=0;z<a.c;++z){
                c.f[i][j]=((long long) a.f[i][z]*b.f[z][j]%p+c.f[i][j])%p;
            }
    return c;
}
int main(){
    freopen("3746.in","r",stdin);
    scanf("%d%d%d%d",&n,&p,&k,&r);long long t=(long long)n*k;
    m.c=m.l=k;
    for (int i=0;i<k;++i) m.f[i][i]++,m.f[(i-1+k)%k][i]++;
    ans.c=k;ans.l=k;
    for (int i=0;i<k;++i) ans.f[i][i]=1;
    for (;t;t>>=1,m=multiply(m,m)){
        if (t&1) ans=multiply(m,ans);
    }
    printf("%d",ans.f[0][r]);
    return 0;
}