hdu4291 A Short problem 矩阵快速幂 求循环节----成都网络赛
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);
}
}
补充：软件开发 , Java ,
