链接: click here~~
题意:
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 whereg(n) = 3g(n – 1) + g(n – 2)g(1) = 1g(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
012
Sample Output
0142837
【解题思路】具体参考前一篇博客,,基本上一样的思路:点击这里
代码:
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <math.h>using namespace std;#define LL long longconst long long mod1=1e9+7;const long long mod2=222222224;const long long mod3=183120;struct Matrix{long long mapp[2][2];};Matrix p= {0,1,1,0};Matrix p1= {0,1,1,3};Matrix unin= {1,0,0,1};Matrix powmul(Matrix a,Matrix b,long long mod){Matrix c;for(int i=0; i<2; i++)for(int j=0; j<2; j++){c.mapp[i][j]=0;for(int k=0; k<2; k++)c.mapp[i][j]+=(a.mapp[i][k]*b.mapp[k][j])%mod;c.mapp[i][j]%=mod;}return c;}Matrix powexp(long long n,long long mod){Matrix m=p1,b=unin;while(n>=1){if(n&1) b=powmul(b,m,mod);n>>=1;m=powmul(m,m,mod);}return powmul(p,b,mod);}long long T;int main(){while(~scanf("%lld",&T)){Matrix ans;ans=powexp(T,mod3);ans=powexp(ans.mapp[0][0],mod2);ans=powexp(ans.mapp[0][0],mod1);cout<<ans.mapp[0][0]<<endl;// printf("%lld\n",ans.mapp[0][0]);}return 0;}
有一些喷着香水闻不到的空气,有一些在写字楼里永远遇不见的人。