BZOJ_4870_[Shoi2017]组合数问题_矩阵乘法

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]);
}