hdu4291 A Short problem 矩陣快速冪 求循環節—-成都網絡賽 – JAVA編程語言程序開發技術文章

A Short problem
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 300    Accepted Submission(s): 110

Problem Description
  According to a research, VIM users tend to have shorter fingers, compared with Emacs users.
  Hence they prefer problems short, too. Here is a short one:
  Given n (1 <= n <= 1018), You should solve for
g(g(g(n))) mod 109 + 7

  where
g(n) = 3g(n – 1) + g(n – 2)

g(1) = 1

g(0) = 0

 
Input
  There are several test cases. For each test case there is an integer n in a single line.
  Please process until EOF (End Of File).

 
Output
  For each test case, please print a single line with a integer, the corresponding answer to this case.

 
Sample Input
0
1
2

 
Sample Output
0
1
42837

 
Source
2012 ACM/ICPC Asia Regional Chengdu Online

 
Recommend
liuyiding
 
主要是求循環節。其實不難.
 
 
[cpp]
//求循環節 
#include<iostream> 
#include<stdio.h> 
using namespace std; 
typedef long long LL; 
const LLMOD = 1000000007LL; 
int main()  

    LL f0 = 0, f1 = 1, temp = -1; 
    for (LL i = 1;; i++)  
    { 
        temp = (3 * f1 + f0) % MOD; 
        f0 = f1; 
        f1 = temp; 
        if (f0 == 0 && f1 == 1)  
        { 
            printf("%I64d\n", i); 
            break; 
        } 
    } 
    return 0; 

 
//const LL MOD = 1000000007LL; 
//222222224 
 
//const LL MOD = 222222224LL; 
//183120 
 
 
 
//A題代碼 
#include<cstdio> 
#include<iostream> 
#include<cstdlib> 
#include<stdio.h> 
#include<math.h> 
#define ll __int64 
using namespace std; 
const int MAX = 2; 
ll mm; 
typedef struct 

ll  m[MAX][MAX]; 
} Matrix; 
Matrix P = 

3,1, 
1,0 
}; 
Matrix I = 

1,0, 
0,1 
}; 
Matrix matrixmul(Matrix a,Matrix b) 

int i,j,k; 
Matrix c; 
for (i = 0 ; i < MAX; i++) 
for (j = 0; j < MAX;j++) 

c.m[i][j] = 0; 
for (k = 0; k < MAX; k++) 
c.m[i][j] += (a.m[i][k] * b.m[k][j]%mm+mm)%mm; 
c.m[i][j] = (c.m[i][j]%mm+mm)%mm; 

return c; 

 
Matrix quickpow(ll n) 

Matrix m = P, b = I; 
while (n >= 1) 

if (n & 1) 
b = matrixmul(b,m); 
n = n >> 1; 
m = matrixmul(m,m); 

return b; 

 
int main() 

    ll n; 
    while(scanf("%I64d",&n)!=EOF) 
    { 
 
       if(n==0) 
       { 
           cout<<0<<endl; 
           continue; 
       } 
       else if(n==1) 
       { 
           cout<<1<<endl; 
           continue; 
       } 
       mm=183120; 
       Matrix g=quickpow2(n-1); 
       ll yy=g.m[0][0]; 
 
       mm=222222224LL; 
       if(yy!=0&&yy!=1) 
       { 
        g=quickpow2(yy-1); 
        yy=g.m[0][0]; 
       } 
 
 
       mm=1000000007LL; 
       if(yy!=0&&yy!=1) 
       { 
           g=quickpow2(yy-1); 
           yy=g.m[0][0]%mm; 
       } 
       printf("%I64d\n",yy); 
    } 

發佈留言