90pt求调
查看原帖
90pt求调
456675
a_sad_soul楼主2022/11/24 17:36
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
struct matrix{
	long long mat[5][5];
	const matrix operator*(const matrix m)
	{
		matrix mid;
		for(int i=1;i<=2;++i)for(int j=1;j<=2;++j)mid.mat[i][j]=0;
		for(int i=1;i<=2;++i)
		{
			for(int j=1;j<=2;++j)
			{
				for(int k=1;k<=2;++k)
				{
					mid.mat[i][j]=(mid.mat[i][j]+this->mat[i][k]*m.mat[k][j])%MOD;
				}
			}
		}
		return mid;
	} 
	const matrix operator^(long long pow)
	{
		matrix ans,mid=*this;
		for(int i=1;i<=2;++i)for(int j=1;j<=2;++j)ans.mat[i][j]=0;
		ans.mat[1][1]=ans.mat[2][2]=1;
		while(pow)
		{
			if(pow&1)ans=ans*mid;
			mid=mid*mid;
			pow>>=1;
		}
		return ans;
	}
};
long long n,m,a,b,c,d;
long long read()
{
	char ch=getchar();long long x=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^'0');if(x!=1)x%=(MOD-1);else x%=MOD;ch=getchar();}
	return x;
}
int main()
{
	n=read(),m=read(),a=read(),b=read(),c=read(),d=read();
	matrix M,N;
	for(int i=1;i<=2;++i)
	{
		for(int j=1;j<=2;++j)
		M.mat[i][j]=N.mat[i][j]=0;
	}
	M.mat[1][1]=a,M.mat[2][1]=b,M.mat[2][2]=1,N.mat[1][1]=c,N.mat[2][1]=d,N.mat[2][2]=1;
	//m+=MOD-1;
	//n+=MOD-1;
	M=M^(m-1);
	matrix isM=M;
	N=M*N;
	N=N^(n-1);
	N=N*isM;
	cout<<(N.mat[1][1]+N.mat[2][1])%MOD;
	return 0;
}
2022/11/24 17:36
加载中...