首页 > 代码库 > HDOJ 4686 Arc of Dream 矩阵快速幂

HDOJ 4686 Arc of Dream 矩阵快速幂

2024-07-31 06:45:39   229人阅读

矩阵快速幂:


根据关系够建矩阵 , 快速幂解决.


Arc of Dream

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


Problem Description
An Arc of Dream is a curve defined by following function:

where
a0 = A0
ai = ai-1*AX+AY
b0 = B0
bi = bi-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 1018, and all the other integers are no more than 2×109.
 


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


Sample Input
11 2 34 5 621 2 34 5 631 2 34 5 6
 


Sample Output
41341902
 


Author
Zejun Wu (watashi)
 


Source
2013 Multi-University Training Contest 9
 


[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
    1. #include <iostream>  
    2. #include <cstdio>  
    3. #include <cstring>  
    4. #include <algorithm>  
    5. #include <cmath>  
    6.   
    7. using namespace std;  
    8.   
    9. typedef long long int LL;  
    10.   
    11. const LL mod=1000000007LL;  
    12.   
    13. struct Matrix  
    14. {  
    15.     int x,y;  
    16.     LL m[6][6];  
    17.     Matrix() {x=y=5;memset(m,0,sizeof(m));}  
    18.     void one()  
    19.     {  
    20.         for(int i=0;i<5;i++) m[i][i]=1LL;  
    21.     }  
    22.     void show()  
    23.     {  
    24.         cout<<x<<" * "<<y<<endl;  
    25.         for(int i=0;i<x;i++)  
    26.         {  
    27.             for(int j=0;j<y;j++)  
    28.                 cout<<m[i][j]<<",";  
    29.             cout<<endl;  
    30.         }  
    31.     }  
    32. };  
    33.   
    34. Matrix Mul(Matrix& a,Matrix& b)  
    35. {  
    36.     Matrix ret;  
    37.     ret.x=a.x; ret.y=b.y;  
    38.     for(int i=0;i<a.x;i++)  
    39.     {  
    40.         for(int j=0;j<b.y;j++)  
    41.         {  
    42.             LL temp=0;  
    43.             for(int k=0;k<b.y;k++)  
    44.             {  
    45.                 temp=(temp+(a.m[i][k]*b.m[k][j])%mod)%mod;  
    46.             }  
    47.             ret.m[i][j]=temp%mod;  
    48.         }  
    49.     }  
    50.     return ret;  
    51. }  
    52.   
    53. Matrix quickPow(Matrix m,LL x)  
    54. {  
    55.     Matrix e;  
    56.     e.one();  
    57.     while(x)  
    58.     {  
    59.         if(x&1LL) e=Mul(e,m);  
    60.         m=Mul(m,m);  
    61.         x/=2LL;  
    62.     }  
    63.     return e;  
    64. }  
    65.   
    66. LL n,A0,B0,AX,AY,BX,BY;  
    67.   
    68. Matrix init_matrix()  
    69. {  
    70.     Matrix ret;  
    71.     ret.m[0][0]=1;  
    72.     ret.m[1][0]=AY; ret.m[1][1]=AX;  
    73.     ret.m[2][0]=BY; ret.m[2][2]=BX;  
    74.     ret.m[3][0]=(BY*AY)%mod; ret.m[3][1]=(AX*BY)%mod;  
    75.     ret.m[3][2]=(BX*AY)%mod; ret.m[3][3]=(AX*BX)%mod;  
    76.     ret.m[4][3]=1LL; ret.m[4][4]=1LL;  
    77.     return ret;  
    78. }  
    79.   
    80. Matrix Beg()  
    81. {  
    82.     Matrix beg;  
    83.     beg.m[0][0]=1;  
    84.     beg.m[1][0]=A0;  
    85.     beg.m[2][0]=B0;  
    86.     beg.m[3][0]=A0*B0%mod;  
    87.     return beg;  
    88. }  
    89.   
    90. int main()  
    91. {  
    92.     while(cin>>n)  
    93.     {  
    94.         cin>>A0>>AX>>AY>>B0>>BX>>BY;  
    95.         A0=A0%mod; AX=AX%mod; AY=AY%mod;  
    96.         B0=B0%mod; BX=BX%mod; BY=BY%mod;  
    97.         Matrix m=init_matrix();  
    98.         m=quickPow(m,n);  
    99.         Matrix beg=Beg();  
    100.         LL ans=0;  
    101.         for(int i=0;i<5;i++)  
    102.             ans=(ans+beg.m[i][0]*m.m[4][i]%mod)%mod;  
    103.         cout<<ans<<endl;  
    104.     }  
    105.     return 0;  
    106. } 

HDOJ 4686 Arc of Dream 矩阵快速幂


联系
我们