319
HDU4291 循環節+矩陣連乘2012 ACM/ICPC Asia Regional Chengdu Online1004
A Short problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 404 Accepted Submission(s): 165
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
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).
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
Recommend
liuyiding
題解：這題需要考慮循環節 然後利用矩陣連乘 相對比於其他的廣義斐波那契問題 這題給了好幾層斐波那契數來取餘 這就很麻煩了 首先通過
暴力 找出g(n)mod10^9+7的循環節 循環節的值為222222224 就是g(g(n))達到222222224的時候222222225時g(222222225)%10^9+7的值
為0 222222226的值為1.... 再次通過暴力 求出g(g(n))循環節的值為183120 同理 再求一次就是240 也就是n的循環節 n經過240循環一次
然後通過矩陣連乘 快速冪取餘 模板就可以過掉 scanf會WA 所以用cin
題解：這題需要考慮循環節 然後利用矩陣連乘 相對比於其他的廣義斐波那契問題 這題給了好幾層斐波那契數來取餘 這就很麻煩了 首先通過
暴力 找出g(n)mod10^9+7的循環節 循環節的值為222222224 就是g(g(n))達到222222224的時候222222225時g(222222225)%10^9+7的值
為0 222222226的值為1.... 再次通過暴力 求出g(g(n))循環節的值為183120 同理 再求一次就是240 也就是n的循環節 n經過240循環一次
然後通過矩陣連乘 快速冪取餘 模板就可以過掉 scanf會WA 所以用cin
注意不要用矩陣連乘找循環節 知道多慢嗎 慢到我以為這題沒循環節 哎 如果昨天腦子好用 用暴力求了 這題我就過了
#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAX = 2;
int M;
typedef struct
{
long long m[MAX][MAX];
} Matrix;
Matrix P =
{
0,1,
1,3,
};
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])%M;
c.m[i][j] %= M;
}
return c;
}
Matrix quickpow(long long 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()
{
long long n,m,c,b;
while(cin>>n)
{
n%=240;
M=183120;
m=quickpow(n).m[0][1]%M;
M=222222224;
m=quickpow(m).m[0][1]%M;
M=1000000007;
m=quickpow(m).m[0][1]%M;
cout<<m<<endl;
}
return 0;
}
最後更新：2017-04-02 15:28:26