【bzoj3240】 Noi2013—矩阵游戏

时间：2021-03-20 17:30:30

http://www.lydsy.com/JudgeOnline/problem.php?id=3240 (题目链接)

题意$${F[1][1]=1}$$$${F[i][j]=a*F[i][j-1]+b (j!=1)}$$$${F[i][1]=c*F[i-1][m]+d (i!=1)}$$

　　求解${F[n][m]}$，${a，b，c，d}$为常数。

Solution

　　原来费马小定理对于矩阵乘法同样适用。。设a为一矩阵，p为质数则：

【bzoj3240】 Noi2013—矩阵游戏

　　正好这里的模数1000000007为质数，那么把n,m模上(p-1)后进行矩阵快速幂即可。用来优化的矩阵很好构造，记得特判a和c等于1的情况。

细节

　　注意如果重载了*，不要弄错了乘法的顺序，因为矩阵乘法是不满足交换律的。

代码

// bzoj3240

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#define MOD 1000000007

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

char s1[1000010],s2[1000010];

LL n,m,a,b,c,d;

struct data {

	LL x[3][3];

	friend data operator * (const data &a,const data &b) {

		data tmp;tmp.x[0][1]=tmp.x[0][2]=tmp.x[0][0]=tmp.x[1][0]=tmp.x[2][0]=0;

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

			for (int j=1;j<=2;j++) {

				tmp.x[i][j]=0;

				for (int k=1;k<=2;k++) tmp.x[i][j]=(tmp.x[i][j]+a.x[i][k]*b.x[k][j])%MOD;

			}

		return tmp;

	}

}A,B,T,ans,res;

void power(data a,int b) {

	ans.x[1][1]=1;ans.x[1][2]=0;ans.x[2][1]=0;ans.x[2][2]=1;

	while (b) {

		if (b&1) ans=a*ans;

		b>>=1;

		a=a*a;

	}

}

int main() {

	scanf("%s%s%lld%lld%lld%lld",s1,s2,&a,&b,&c,&d);

	A.x[1][1]=a;A.x[1][2]=0;A.x[2][1]=b;A.x[2][2]=1;

	B.x[1][1]=c;B.x[1][2]=0;B.x[2][1]=d;B.x[2][2]=1;

	T.x[1][1]=1;T.x[1][2]=1;T.x[2][1]=T.x[2][2]=0;

	LL P=MOD-1;

	if (a==1 && c==1) P=MOD;

	int l=strlen(s1);

	for (int i=0;i<l;i++) n=(n*10+s1[i]-'0')%P;

	l=strlen(s2);

	for (int i=0;i<l;i++) m=(m*10+s2[i]-'0')%P;

	power(A,m-1);

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

		for (int j=1;j<=2;j++) A.x[i][j]=res.x[i][j]=ans.x[i][j];

	A=A*B;

	power(A,n-1);

	res=ans*res;

	res=T*res;

	printf("%lld",res.x[1][1]);

	return 0;

}

　　

相关文章