# 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;

mm=222222224LL;
if(yy!=0&&yy!=1)
{
g=quickpow2(yy-1);
yy=g.m;
}

mm=1000000007LL;
if(yy!=0&&yy!=1)
{
g=quickpow2(yy-1);
yy=g.m%mm;
}
printf("%I64d\n",yy);
}