NOI2013矩阵游戏
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
1<=N,M<=10^1000 000,a<=a,b,c,d<=10^9
题解
若a,p互质，则\(x^a\equiv x^{a~mod \phi p+\phi p}(\mod~p)\)
然后就直接上矩阵乘法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define ll long long #define eps 1e-12 using namespace std; ll l,n,m,a,b,c,d,phi; char s1[1000005],s2[1000005]; struct M{ ll v[2][2]; M(){ memset(v,0,sizeof(v)); } friend M operator*(M a,M b){ M c; for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod; return c; } friend M operator^(M a,ll b){ M c;c.v[0][0]=c.v[1][1]=1; for(ll i=b;i;i>>=1,a=a*a) if(i&1)c=c*a; return c; } }A,B,f; int main() { scanf("%s",s1);scanf("%s",s2); scanf("%lld%lld%lld%lld",&a,&b,&c,&d); phi=mod-1;if(a==1&&c==1)phi=mod; l=strlen(s1); for(int i=0;i<l;i++)n=(n*10+s1[i]-'0')%phi; n=(n+phi-1)%phi; l=strlen(s2); for(int i=0;i<l;i++)m=(m*10+s2[i]-'0')%phi; m=(m+phi-1)%phi; A.v[0][0]=1;A.v[0][1]=b;A.v[1][1]=a; B.v[0][0]=1;B.v[0][1]=d;B.v[1][1]=c; f.v[0][0]=f.v[0][1]=1; A=A^m;B=A*B;B=B^n; printf("%lld\n",(f*B*A).v[0][1]); return 0; } |
计数器 9863968
OI 课件=>
OI 课件=>
学长，你的程序在UOJ的额外数据貌似会WA。。。
学长 求教 if(a==1&&c==1)phi=mod 这个特判是为什么？
这个情况下费马小定理不成立
你的程序在UOJ貌似会WA。。 extra test
2333我被qmqmqm对着叉就是因为这个–n+e