好水啊

但是我傻啊

我们设\(dp[i][j]=\sum_{t=0}^{∞}\binom{ik}{j+tk}\)

根据组合数万年不变的递推式\(\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}\)

我们有\(dp[i][j]=dp[i-1][j]+dp[i-1][(j-1+k)\%k]\)

显然这个柿子可以用矩阵优化到\(log\)

于是就没有了

有一个坑点就是当\(k=1\)的时候实际上是有\(dp[i][0]=2*dp[i-1][0]\)，于是构造矩阵的时候小心一下就可以了

代码

#include
    
     #include
     
      #include
      
       #define re register#define LL long longinline int read(){    re char c=getchar();    re int x=0;    while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9')        x=(x<<3)+(x<<1)+c-48,c=getchar();    return x;}LL n,k,P,r;LL ans[51][51],a[51][51];inline void did_a(){    LL mid[51][51];    for(re int i=0;i
       
        >=1ll;        did_a();    }}int main(){    n=read(),P=read(),k=read(),r=read();    for(re int i=0;i