看网上一群人说“傻逼题”，我感觉我傻逼了。

首先我们把式子转换一下变成求有nk件物品，我取的物品数%k==r的方案数有多少。

显然f[i][j]=f[i-1][j]+f[i-1][j-1]。

但就没人教一下f[i][j]=f[i-1][j]+f[i-1][j-1]如何矩乘吗……

那我就引洛谷的题解了：

可以加速的原理，其实就是杨辉三角是一个一维递推，并且可以将递推描述为：复制矩阵到一个新矩阵，然后矩阵右移一格，加到新矩阵中。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;ll n,p,K,r;struct node{    ll g[51][51];    node(){        memset(g,0,sizeof(g));    }    friend node operator *(const node &x,const node &y){        node z;        for(int i=0;i
          
           >n>>p>>K>>r; t.g[0][0]=1; for(int i=0;i
           
            >=1; } printf("%lld\n",(t*res).g[0][r]); return 0;}
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++