题目描述

Description

Input

第一行有四个整数 n, p, k, r，所有整数含义见问题描述。
1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1

Output

一行一个整数代表答案。

Sample Input

2 10007 2 0

Sample Output

8

题目分析

竟然是矩乘加速DP我的天
题目实质是求出从nk个数选出%k为r个数的方案数
表示从i个数里 选出%k为j的数的方案个数

之后矩阵乘法加速递推即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long n,p;
int k,r;
struct your
{   
    long long x[60][60];
    your(){ memset(x,0,sizeof x) ; }
    friend your operator*(your x,your y)
    {   
        your z;
        for(int i=0;i<k;i++)
            for(int j=0;j<k;j++)
                for(int l=0;l<k;l++)
                    z.x[i][j]=(z.x[i][j]+(x.x[i][l]*y.x[l][j])%p)%p;
        return z;
    }
}A,B;
void ksm(long long y)
{
    while(y)
    {
        if(y&1ll) A=A*B;
        B=B*B,y>>=1;
    }
}
int main()
{   
    scanf("%lld%lld%d%d",&n,&p,&k,&r);/*
    f[0][0]=1;
    for(int i=1;i<=n*k;i++)
        for(int j=0;j<k;j++)
            f[i][j]+=f[i-1][j]+f[i-1][(j-1+k)%k],f[i][j]%=p;
    printf("%d",f[n*k][r]);*/
    A.x[0][0]=1;
    for(int i=0;i<k;i++) B.x[i][i]++,B.x[i][(i-1+k)%k]++;
    ksm((long long)n*k);
    printf("%lld",A.x[0][r]%p); 
    return 0;
}