Luogu

LOJ

分析

考虑要求的东西的组合意义，为从 $nk$ 个物品中选出 $t$ 个物品的方案数，其中 $t\bmod k=r$。

考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，选出的物品数量模 $k$ 为 $j$ 时的方案数。显然有转移
$$
dp_{i,j}=dp_{i-1,j}+dp_{i-1,(j-1)\bmod k}
$$
显然可以矩阵优化，不难得到
$$
\begin{bmatrix}dp_{i,0}&dp_{i,1}&\cdots&dp_{i,k-1}\end{bmatrix}\times\begin{bmatrix}1&1&\cdots&0\\0&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\1&0&\cdots&1\end{bmatrix}=\begin{bmatrix}dp_{i+1,0}&dp_{i+1,1}&\cdots&dp_{i+1,k-1}\end{bmatrix}
$$
直接矩阵快速幂即可。

需要注意的是 $k=1$ 时转移矩阵是 $[2]$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,k,r,mod;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

struct Matrix {
    int s[50][50];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} Q;

Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int i=0;i<k;++i)
        for (int j=0;j<k;++j)
            for (int l=0;l<k;++l)
                c[i][j]=(c[i][j]+1ll*a[i][l]*b[l][j])%mod;
    return c;
}
Matrix qpow(Matrix a,ll b) {
    Matrix c;
    for (int i=0;i<k;++i) c[i][i]=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

int main() {
    n=read(),mod=read(),k=read(),r=read();
    for (int i=0;i<k;++i) ++Q[i][i],++Q[(i-1+k)%k][i];
    Q=qpow(Q,1ll*n*k);
    printf("%d\n",Q[0][r]);
    return 0;
}