admin 管理员组文章数量: 887006
矩阵游戏
矩阵游戏
描述
婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的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的余数。
输入
一行有六个整数n,m,a,b,c,d。意义如题所述。
1<=N,M<=10^1000 000,a<=a,b,c,d<=10^9
输出
包含一个整数，表示F[n][m]除以1,000,000,007的余数
题解
m,n的数据范围在10^1000000，必须要使用方法加速
我使用的是矩阵；
用ma储存f[1,1];
ma=,A=，B=
F[i,j]=a*F[i][j-1]+b (j!=1)推的是F[i,1]->F[i,m]
要推n-1次
从F[1,1]->F[1,2]:
ma*A=
从F[1,1]->F[1,3]:
ma*A*A=
则F[1,1]->F[1,m] ma=ma*A^m-1;
F[i,1]=c*F[i-1][m]+d (i!=1)推的是F[i,m]->F[i+1,1];
从F[i,m]->F[i+1,1]，ma=ma*A^m-1*B
要推n-1次
ma=(ma*A^m-1*B)^n-1;
最后从F[n,1]->F[n,m]:
ma=(ma*A^m-1*B)^n-1*A^m-1;
因为n,m太大，可以使用欧拉降幂来减少次数，
1e+7为质数，则a不为1，成立
#include<bits/stdc++.h>
using namespace std;
int mod=1000000007;
typedef long long ll;
string N,M;
ll a,b,c,d;
ll ma[2][2]={1,1,0,0},A[2][2],B[2][2],C[2][2];
//C用于储存 A^m-1;
ll f(string x,int m)
{ll l=x.size();ll sum=0;for(int i=0;i<l;i++){sum=(sum*10+(x[i]-'0'))%m;}return sum;
}
void f1(ll x[2][2],ll y[2][2])
{ll D[2][2]={0,0,0,0};for(int i=0;i<=1;i++){for(int j=0;j<=1;j++){for(int k=0;k<=1;k++){D[i][j]=(D[i][j]+x[i][k]*y[k][j])%mod;}}}for(int i=0;i<=1;i++){for(int j=0;j<=1;j++){x[i][j]= D[i][j];}}
}
int main()
{ll n,m,D[2][2]={1,0,0,1};//D用于运算 cin>>N>>M>>a>>b>>c>>d;//cout<<N<<" "<<M<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;if(a==1) n=f(N,mod);else n=f(N,mod-1);if(c==1) m=f(M,mod);else m=f(M,mod-1);n--;m--;A[0][0]=a,A[0][1]=0,A[1][0]=b,A[1][1]=1; B[0][0]=c,B[0][1]=0,B[1][0]=d,B[1][1]=1;D[0][0]=D[1][1]=1;D[0][1]=D[1][0]=0;while(m){if(m&1) f1(D,A);f1(A,A);m/=2;}for(int i=0;i<=1;i++){for(int j=0;j<=1;j++){C[i][j]= D[i][j];}}//C=A^m-1;f1(D,B);//D=A^m-1*B;while(n){if(n&1) f1(ma,D);f1(D,D);n/=2;}f1(ma,C);printf("%lld",ma[0][0]);return 0;} 本文标签： 矩阵游戏
版权声明：本文标题：矩阵游戏 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732351904h1533319.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论