题目链接

Solution

矩阵优化 \(dp\).

题中给出的式子的意思就是:

求 nk 个物品中选出 mod k 为 r 的个数的物品的方案数.

考虑朴素 \(dp\) ,定义状态 \(f[i][j]\) 代表前 \(i\) 个物品选择 \(mod~k\) 为 \(j\) 的方案数.

那么转移方程也很简单 :

但是很显然这样是 \(O(n^2k)\) .

考虑优化,发现对于每一项状态,仅与 \(i-1\) 的状态有关.

如此我们可以考虑构建一个 \(k*k\) 的转移矩阵,即：

然后初始矩阵即为一个 \(k*1\) 的矩阵.

然后就可以矩阵快速幂了.

Code

#include<bits/stdc++.h>

#define in(x) x=read()

#define ll long long

using namespace std;

int read()

{

    char ch=getchar(); int w=0;

    while(ch<'0'||ch>'9')ch=getchar();

    while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}

    return w;

}

ll n,mod,k,r;

struct Matrix{

    ll a[51][51];

};

Matrix X(Matrix s,Matrix e)

{

    Matrix c;

    memset(c.a,0,sizeof(c.a));

    for(int i=0;i<k;i++)

    for(int j=0;j<k;j++)

    for(int l=0;l<k;l++)

    {

        c.a[i][j]+=(s.a[i][l]*e.a[l][j])%mod;

        c.a[i][j]%=mod;

    }

    return c;

}

Matrix quick_pow(Matrix s,ll ks)

{

    if(ks==1)return s;

    Matrix k=s; ks--;

    while(ks>0)

    {

        if(ks%2==1)k=X(k,s);

        ks/=2;

        s=X(s,s);

    }

    return k;

}

Matrix x(Matrix s,Matrix e)

{

    Matrix c;

    memset(c.a,0,sizeof(c.a));

    for(int i=0;i<1;i++)

    for(int j=0;j<k;j++)

    for(int l=0;l<k;l++)

    {

        c.a[j][i]+=(s.a[j][l]*e.a[l][i])%mod;

        c.a[j][i]%=mod;

    }

    return c;

}

int main()

{

    in(n),in(mod),in(k),in(r);

    Matrix P,f;

    memset(P.a,0,sizeof(P.a));

    memset(f.a,0,sizeof(f.a));

    for(ll i=0;i<k;i++)

    {

        if(i==0)

        P.a[i][0]++,P.a[i][k-1]++;

        else

        P.a[i][i-1]++,P.a[i][i]++;

    }

    P=quick_pow(P,n*k);

    f.a[0][0]=1;

    f=x(P,f);

    cout<<f.a[r%k][0]%mod<<endl;

}