首页 > 代码库 > hdu----(4686)Arc of Dream(矩阵快速幂)

hdu----(4686)Arc of Dream(矩阵快速幂)

2024-07-24 00:57:49   220人阅读

Arc of Dream

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


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
 
这道题的分析，其实应该这样分析：
  我们看到这么个式子    然后我们知道ai=ai-1*AX+AY   ;     bi=bi-1*BX+BY;
   ai*bi =AXBX*ai-1*bi-1+AXBY*ai-1+BXAY*bi-1+AY*BY;
   对于这样一个式子，我们不妨构造这样一个矩阵......
如：
  |ai*bi|     |AX*BX , AXBY , BXAY , AYBY, 0  |^n-1   | ai-1*ai-1 |
  |  ai  |     |  0       , AX    , 0        , AY   , 0  |           |  ai-1       |
  |  bi  |  = |  0       , 0     ,   BX    , BY    , 0  |   *      |  bi-1       |
  |   1  |     |  0       , 0     ,  0       ,    1   , 0  |           |     1        |
  |  sn  |     | AXBX  , AXBY,  BXAY,  AYBY, 1 |            |     sn-1   |
然后就是快速矩阵...
  1 #define LOCAL  2 #include<cstdio>  3 #include<cstring>  4 #define LL __int64  5 using namespace std;  6   7 const LL mod=1000000007;  8   9 struct node 10 { 11    LL mat[5][5]; 12    void init(int v){ 13         for(int i=0;i<5;i++){ 14          for(int j=0;j<5;j++) 15          if(i==j) 16             mat[i][j]=v; 17          else 18             mat[i][j]=0; 19      } 20    } 21 }; 22  23  24 LL AO,BO,AX,AY,BX,BY,n; 25 node ans,cc; 26  27 void init(node &a) 28 { 29   a.mat[4][0]=a.mat[0][0]=(AX*BX)%mod; 30   a.mat[4][1]=a.mat[0][1]=(AX*BY)%mod; 31   a.mat[4][2]=a.mat[0][2]=(BX*AY)%mod; 32   a.mat[4][3]=a.mat[0][3]=(AY*BY)%mod; 33   a.mat[1][0]=a.mat[1][3]=a.mat[1][4]=a.mat[0][4]=0; 34   a.mat[2][0]=a.mat[2][1]=a.mat[2][4]=0; 35   a.mat[3][0]=a.mat[3][1]=a.mat[3][2]=a.mat[3][4]=0; 36   a.mat[3][3]=a.mat[4][4]=1; 37   a.mat[1][1]=AX; 38   a.mat[1][3]=AY; 39   a.mat[2][2]=BX; 40   a.mat[2][3]=BY; 41 } 42  43 void Matrix(node &a, node &b) 44 { 45   node c; 46   c.init(0); 47   for(int i=0;i<5;i++) 48   { 49       for(int j=0;j<5;j++) 50       { 51       for(int k=0;k<5;k++) 52       { 53         c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod; 54       } 55     } 56   } 57  58  for(int i=0;i<5;i++) 59  { 60   for(int j=0;j<5;j++) 61   { 62     a.mat[i][j]=c.mat[i][j]; 63   } 64  } 65 } 66  67 void pow(node &a,LL w ) 68 { 69    while(w>0) 70    { 71          if(w&1) Matrix(ans,a); 72          w>>=1L; 73          if(w==0)break; 74          Matrix(a,a); 75    } 76 } 77  78 int main() 79 { 80    LL sab; 81    #ifdef LOCAL 82    freopen("test.in","r",stdin); 83    #endif 84   while(scanf("%I64d",&n)!=EOF) 85   { 86       scanf("%I64d%I64d%I64d",&AO,&AX,&AY); 87       scanf("%I64d%I64d%I64d",&BO,&BX,&BY); 88     if(n==0){ 89  90       printf("0\n"); 91       continue; 92     } 93     AO%=mod; 94     BO%=mod; 95     AX%=mod; 96     AY%=mod; 97     BX%=mod; 98     BY%=mod; 99       ans.init(1);100       init(cc);101       pow(cc,n-1);102 103       sab=(AO*BO)%mod;104     LL res=(ans.mat[4][0]*sab)%mod+(ans.mat[4][1]*AO)%mod+(ans.mat[4][2]*BO)%mod+ans.mat[4][3]%mod+(AO*BO)%mod;105       printf("%I64d\n",res%mod);106   }107  return 0;108 }
View Code

 

hdu----(4686)Arc of Dream(矩阵快速幂)


联系
我们