A Short problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 779 Accepted Submission(s): 296
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 <= 10 18), You should solve for g(g(g(n))) mod 10 9 + 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 Recommend
liuyiding
//矩阵快速运算 //| 3 1 | //| 1 0 | 由这个矩阵进行幂运算 ，今天上数据结构课时，老师讲些无聊的线性表，就回想了下这题和斐波那契的矩阵运算，在纸上才发现 递推都可以用矩阵快速运算的 、O(∩_∩)O~ //可是上次网赛没发现呀 // 当然由于数比较大，需要找出循环节、、然后就 0Ms 过了 #include#include #include #include #define lson l,m,k<<1#define rson m+1,r,k<<1|1#define N 500002using namespace std;__int64 Matrix(__int64 n,__int64 M){ __int64 a[2][2]={3,1,1,0}; __int64 b[2][2]={1,0,0,1}; __int64 c[2][2]; for(;n>0;n=n>>1) { if(n&1) { c[0][0]=(b[0][0]*a[0][0]%M+b[0][1]*a[1][0]%M)%M; c[1][0]=(b[1][0]*a[0][0]%M+b[1][1]*a[1][0]%M)%M; c[0][1]=(b[0][0]*a[0][1]%M+b[0][1]*a[1][1]%M)%M; c[1][1]=(b[1][0]*a[0][1]%M+b[1][1]*a[1][1]%M)%M; memcpy(b,c,sizeof(c)); } c[0][0]=(a[0][0]*a[0][0]%M+a[0][1]*a[1][0]%M)%M; c[1][0]=(a[1][0]*a[0][0]%M+a[1][1]*a[1][0]%M)%M; c[0][1]=(a[0][0]*a[0][1]%M+a[0][1]*a[1][1]%M)%M; c[1][1]=(a[1][0]*a[0][1]%M+a[1][1]*a[1][1]%M)%M; memcpy(a,c,sizeof(c)); } return b[1][0];}int main(){ __int64 n; __int64 tmp; while(scanf("%I64d",&n)!=EOF) { if(!n) printf("0\n"); else { tmp=Matrix(n,183120); tmp=Matrix(tmp,222222224); printf("%I64d\n",Matrix(tmp,1000000007)); } } return 0;}