BZOJ 3240([Noi2013]矩阵游戏-费马小定理【矩阵推论】-%*s-快速读入)

时间：2021-01-11 17:26:43

3240: [Noi2013]矩阵游戏

Time Limit: 10 Sec   Memory Limit: 256 MB

Submit: 123  
Solved: 73

[
Submit][
Status]

Description

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质：若用F[i][j]来表示矩阵中第i行第j列的元素，则F[i][j]满足下面的递推式:

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)
递推式中a,b,c,d都是给定的常数。

现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大，你只需要输出F[n][m]除以1,000,000,007的余数。

Input

一行有六个整数n,m,a,b,c,d。意义如题所述

Output

包含一个整数，表示F[n][m]除以1,000,000,007的余数

Sample Input

3 4 1 3 2 6

Sample Output

85

HINT

样例中的矩阵为：

1 4 7 10

26 29 32 35

76 79 82 85

BZOJ 3240([Noi2013]矩阵游戏-费马小定理【矩阵推论】-%*s-快速读入)

Source

 

NOI赛场上拿了70分（没用费马小定理）

PS:实际原因是没算复杂度囧。。。。

好吧。。。这题让我们回顾一下费马小定理：

a^b mod (phi(p))=1 (mod p)

所以可以mod ，特判a=c=1的特殊情况

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<functional>

#include<iostream>

#include<cmath>

#include<cctype>

#include<ctime>

using namespace std;

#define For(i,n) for(int i=1;i<=n;i++)

#define Fork(i,k,n) for(int i=k;i<=n;i++)

#define Rep(i,n) for(int i=0;i<n;i++)

#define ForD(i,n) for(int i=n;i;i--)

#define RepD(i,n) for(int i=n;i>=0;i--)

#define Forp(x) for(int p=pre[x];p;p=next[p])

#define Lson (x<<1)

#define Rson ((x<<1)+1)

#define MEM(a) memset(a,0,sizeof(a));

#define MEMI(a) memset(a,127,sizeof(a));

#define MEMi(a) memset(a,128,sizeof(a));

#define INF (2139062143)

#define F (1000000007)

#define MAXN (1000000+10)

long long mul(long long a,long long b){return (a*b)%F;}

long long add(long long a,long long b){return (a+b)%F;}

long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}

typedef long long ll;

ll a,b,c,d,n,m,phiF;

ll getint(char s[]) //_dec_1

{

	char c;

	ll x=0;

	for(int i=0,c=s[i];s[i];c=s[++i])

	{

		x=(x*10+c-48)%phiF;

	}

	x=(x-1+phiF)%phiF;

	return x;

}

struct M

{

	int n,m;

	ll a[3][3];

	M(){n=m=2;MEM(a);}

	M(ll a1,ll a2,ll b1,ll b2){n=m=2;MEM(a) a[1][1]=a1,a[1][2]=a2,a[2][1]=b1,a[2][2]=b2;	}

	friend M operator*(M a,M b)

	{

		M c;

		For(k,2)

			For(i,2)

				For(j,2)

					c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%F;

	/*

	For(i,2)

	{

		For(j,2) cout<<c.a[i][j]<<' ';cout<<endl;

	}*/

		return c;

	}

	void make_I()

	{

		n=m=2;MEM(a)

		For(i,n) a[i][i]=1;

	}

}A,B,C,D,I;

void print(M a)

{

	For(i,2)

	{

		For(j,2) cout<<a.a[i][j]<<' ';cout<<endl;

	}

}

M pow2(M a,ll b)

{

	M c=I;

	static bool a2[MAXN];

	int n=0;while (b) a2[++n]=b&1,b>>=1;

	For(i,n)

	{

		if (a2[i]) c=c*a;

		a=a*a;

	}

	return c;

}

char s1[MAXN],s2[MAXN];

int main()

{

	scanf("%s%s",s1,s2);

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

	if (a==1&&c==1) phiF=F;else phiF=F-1;

	n=getint(s1);m=getint(s2);

	A=M(a,b,0,1);B=M(c,d,0,1);I=M(1,0,0,1);

	C=pow2(A,m);//print(C);

	D=B*C;//print(D);

	D=pow2(D,n);

	D=C*D;//print(D);

	cout<<(D.a[1][2]+D.a[1][1])%F<<endl;

	return 0;

}

顺便再附一份读文件的特殊写法：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<functional>

#include<iostream>

#include<cmath>

#include<cctype>

#include<ctime>

using namespace std;

#define For(i,n) for(int i=1;i<=n;i++)

#define Fork(i,k,n) for(int i=k;i<=n;i++)

#define Rep(i,n) for(int i=0;i<n;i++)

#define ForD(i,n) for(int i=n;i;i--)

#define RepD(i,n) for(int i=n;i>=0;i--)

#define Forp(x) for(int p=pre[x];p;p=next[p])

#define Lson (x<<1)

#define Rson ((x<<1)+1)

#define MEM(a) memset(a,0,sizeof(a));

#define MEMI(a) memset(a,127,sizeof(a));

#define MEMi(a) memset(a,128,sizeof(a));

#define INF (2139062143)

#define F (1000000007)

#define MAXN (1000000+10)

long long mul(long long a,long long b){return (a*b)%F;}

long long add(long long a,long long b){return (a+b)%F;}

long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}

typedef long long ll;

ll a,b,c,d,n,m,phiF;

ll getint() //_dec_1

{

	char c;

	while (c=getchar(),(!isdigit(c)));

		//cout<<(int)c;

	ll x=c-48;

	while (c=getchar(),(isdigit(c)))

	{

		x=(x*10+c-48)%phiF;

	}

	x=(x-1+phiF)%phiF;

	return x;

}

struct M

{

	int n,m;

	ll a[3][3];

	M(){n=m=2;MEM(a);}

	M(ll a1,ll a2,ll b1,ll b2){n=m=2;MEM(a) a[1][1]=a1,a[1][2]=a2,a[2][1]=b1,a[2][2]=b2;	}

	friend M operator*(M a,M b)

	{

		M c;

		For(k,2)

			For(i,2)

				For(j,2)

					c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%F;

	/*

	For(i,2)

	{

		For(j,2) cout<<c.a[i][j]<<' ';cout<<endl;

	}*/

		return c;

	}

	void make_I()

	{

		n=m=2;MEM(a)

		For(i,n) a[i][i]=1;

	}

}A,B,C,D,I;

void print(M a)

{

	For(i,2)

	{

		For(j,2) cout<<a.a[i][j]<<' ';cout<<endl;

	}

}

M pow2(M a,ll b)

{

	M c=I;

	static bool a2[MAXN];

	int n=0;while (b) a2[++n]=b&1,b>>=1;

	For(i,n)

	{

		if (a2[i]) c=c*a;

		a=a*a;

	}

	return c;

}

int main()

{

	freopen("matrix.in","r",stdin);

	freopen("matrix.out","w",stdout);

	scanf("%*s%*s");

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

	if (a==1&&c==1) phiF=F;else phiF=F-1;

	freopen("matrix.in","r",stdin);

	n=getint();m=getint();

	A=M(a,b,0,1);B=M(c,d,0,1);I=M(1,0,0,1);

	C=pow2(A,m);//print(C);

	D=B*C;//print(D);

	D=pow2(D,n);

	D=C*D;//print(D);

	cout<<(D.a[1][2]+D.a[1][1])%F<<endl;

	return 0;

}

相关文章