BZOJ4870:[SHOI2017]组合数问题(组合数学,矩阵乘法)

Description

Input

第一行有四个整数 n, p, k, r，所有整数含义见问题描述。

1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1

Output

一行一个整数代表答案。

Sample Input

2 10007 2 0

Sample Output

Solution

考虑这个式子的组合数意义，发现其实就是从$n*k$个物品里面取$\%k=r$件物品的方案数。

所以$f[i][j]$表示放完前$i$个，余数为$j$的方案数。$f[i][j] = f[i-1][j] + f[i - 1][(j - 1 + k) \% k]$，矩乘优化一下就可以了。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define LL long long

 using namespace std;

 LL n,MOD,k,r;

 struct Matrix

 {

     LL m[][];

     Matrix(){memset(m,,sizeof(m));}

     Matrix operator * (const Matrix &b) const

     {

         Matrix c;

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

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

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

                     (c.m[i][j]+=m[i][k]*b.m[k][j])%=MOD;

         return c;

     }

 }A,ans;

 Matrix Qpow(Matrix a,LL b)

 {

     Matrix ans;

     for (int i=; i<; ++i) ans.m[i][i]=;

     while (b)

     {

         if (b&) ans=ans*a;

         a=a*a; b>>=;

     }

     return ans;

 }

 int main()

 {

     scanf("%lld%lld%lld%lld",&n,&MOD,&k,&r);

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

     {

         A.m[i][i]++;

         A.m[(i-+k)%k][i]++;

     }

     ans.m[][]=;

     ans=ans*Qpow(A,n*k);

     printf("%lld\n",ans.m[][r]);

 }

巴特西