BZOJ_4870_[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
设$f[i][j]$表示$i$个球，取出$m(m$%$k=r)$个的方案数。
转移：$f[i][j]=f[i-1][j]+f[i-1][j-1]$，特别的，$f[i][0]=f[i-1][0]+f[i-1][k-1]$。
可以构造矩阵，$i->i，i->(i+1)$%$k$ 。
然后乘$nk$次，$v[0][r]$为答案。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
ll mod;
int n,m,r;
struct Mat {
ll v[51][51];
Mat(){memset(v,0,sizeof(v));}
Mat operator*(const Mat &x)const {
Mat re;int i,j,k;
for(i=0;i<m;i++) {
for(j=0;j<m;j++) {
for(k=0;k<m;k++) {
(re.v[i][j]+=v[i][k]*x.v[k][j]%mod)%=mod;
}
}
}
return re;
}
};
Mat qp(Mat x,ll y) {
Mat I;
int i;
for(i=0;i<m;i++) I.v[i][i]=1;
while(y) {
if(y&1ll) I=I*x;
x=x*x;
y>>=1ll;
}
return I;
}
int main() {
scanf("%d%lld%d%d",&n,&mod,&m,&r);
int i;
Mat x;
for(i=0;i<m-1;i++) x.v[i][i+1]++; x.v[m-1][0]++;
for(i=0;i<m;i++) x.v[i][i]++;
Mat T=qp(x,1ll*m*n);
printf("%lld\n",T.v[0][r]);
}