Description

Solution

其实看到数据范围应该往矩阵乘法这边想的

考虑式子的实际意义 从n*k个里面选模k等于r个的方案数 Dp

f[i][j]=f[i-1][j]+f[i-1][(j-1+k)%k]

另外给矩阵赋值的时候建议  m.a[(i-1+K)%K][i]++; m.a[i][i]++; 而不是  m.a[(i-1+K)%K][i]=1; m.a[i][i]=1; 

因为K=1的时候会出现偏差…a[0][0]应该为2

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;LL n,r,K,p;struct Matrix{    LL a[51][51];    Matrix(){memset(a,0,sizeof(a));}    Matrix operator *(const Matrix& x)    {        Matrix ans;        for(int i=0;i
         
          >=1;    }    return res;}int main(){    scanf("%lld%lld%lld%lld",&n,&p,&K,&r);    for(int i=0;i