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
8
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
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define LL long long 5 using namespace std; 6 7 LL n,MOD,k,r; 8 9 struct Matrix 10 { 11 LL m[59][59]; 12 Matrix(){memset(m,0,sizeof(m));} 13 Matrix operator * (const Matrix &b) const 14 { 15 Matrix c; 16 for (int i=0; i<50; ++i) 17 for (int j=0; j<50; ++j) 18 for (int k=0; k<50; ++k) 19 (c.m[i][j]+=m[i][k]*b.m[k][j])%=MOD; 20 return c; 21 } 22 }A,ans; 23 24 Matrix Qpow(Matrix a,LL b) 25 { 26 Matrix ans; 27 for (int i=0; i<50; ++i) ans.m[i][i]=1; 28 while (b) 29 { 30 if (b&1) ans=ans*a; 31 a=a*a; b>>=1; 32 } 33 return ans; 34 } 35 36 int main() 37 { 38 scanf("%lld%lld%lld%lld",&n,&MOD,&k,&r); 39 for (int i=0; i<k; ++i) 40 { 41 A.m[i][i]++; 42 A.m[(i-1+k)%k][i]++; 43 } 44 ans.m[0][0]=1; 45 ans=ans*Qpow(A,n*k); 46 printf("%lld ",ans.m[0][r]); 47 }