Arc of Dream

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 297    Accepted Submission(s): 93

Problem Description An Arc of Dream is a curve defined by following function: where a ₀ = A0 a _i = a _i-1*AX+AY b ₀ = B0 b _i = b _i-1*BX+BY What is the value of AoD(N) modulo 1,000,000,007?  

 

Input There are multiple test cases. Process to the End of File. Each test case contains 7 nonnegative integers as follows: N A0 AX AY B0 BX BY N is no more than 10 ¹⁸, and all the other integers are no more than 2×10 ⁹.  

 

Output For each test case, output AoD(N) modulo 1,000,000,007.  

 

Sample Input 1 1 2 3 4 5 6 2 1 2 3 4 5 6 3 1 2 3 4 5 6    

 

Sample Output 4 134 1902  

 

Author Zejun Wu (watashi)  

 

Source 2013 Multi-University Training Contest 9   #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <set> #include <sstream> #include <map> #include <bitset> using namespace std ; #define zero {0} #define INF 2000000000 #define eps 1e-6 typedef long long LL; const int N=5;//定义NxN矩阵 #define mod 1000000007//取模 struct matrix { LL a[N][N]; }origin,res; matrix multiply(matrix& x,matrix& y)//矩阵乘 { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { for(int k=0;k<N;k++) { temp.a[i][j]=(temp.a[i][j]+x.a[i][k]*y.a[k][j])%mod; } } } return temp; } matrix MatrixPow(LL n)//矩阵快速幂，求n次方 { while(n) { if(n&1) res=multiply(res,origin); n/=2; origin=multiply(origin,origin); } return res; } int main() { #ifdef DeBUG freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); #endif LL a0,ax,ay; LL b0,bx,by; LL n; while(scanf("%I64d",&n)+1) { LL i,j,k; memset(res.a,0,sizeof(res.a)); memset(origin.a,0,sizeof(origin.a)); scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a0,&ax,&ay,&b0,&bx,&by); res.a[0][1]=a0*b0%mod; res.a[0][2]=a0%mod; res.a[0][3]=b0%mod; res.a[0][4]=1; origin.a[0][0]=1; origin.a[1][0]=1; origin.a[1][1]=(ax*bx)%mod; origin.a[2][1]=ax*by%mod; origin.a[2][2]=ax%mod; origin.a[3][1]=bx*ay%mod; origin.a[3][3]=bx%mod; origin.a[4][1]=ay*by%mod; origin.a[4][2]=ay%mod; origin.a[4][3]=by%mod; origin.a[4][4]=1; MatrixPow(n); cout<<res.a[0][0]<<endl; } return 0; } /* res AoD ai*bi ai bi 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 org 1 0 0 0 0 1 ax*bx 0 0 0 0 ax*by ax 0 0 0 bx*ay 0 bx 0 0 ay*by ay by 1 */ View Code

矩阵快速幂，可做模板用

没想到这题能这么搞，现在终于知道矩阵快速幂的实用价值了

话说还有公式版的，那个太繁琐就不搞了

转载于:https://www.cnblogs.com/Skyxj/p/3271268.html