题目链接：

神仙思维题。

直接推式子是找不到什么性质的，我们来考虑一下这个式子的意义：

在\(nk\)个物品中，选\(x(x\mod{k}\equiv r)\)个物品的方案数

那么可以DP：设\(f[i][j]\)表示前\(i\)个物品，选\(x(x\mod{k}\equiv j)\)个物品的方案数

则有：\(f[i][j]=f[i-1][(j-1)\mod{k}]+f[i-1][j]\)

那么就可以矩阵乘法优化了。

时间复杂度 \(O(k^2\log n)\)

注意特判\(k=1\)的情况

代码：

#include 
    
     #include 
     
      #define rint register inttypedef long long ll;int n,p,k,r;struct Matrix{    int n,m,a[55][55];    inline Matrix(int ns,int ms){n=ns,m=ms;memset(a,0,sizeof a);}    inline Matrix operator*(const Matrix &o)const    {        Matrix Res(n,o.m);        for(rint i=0;i
      
       >=1,g=g*g)if(b&1)f=f*g;    printf("%d\n",f.a[0][r]);    return 0;}