暴力找循环节，矩阵快速幂
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <string> #include <vector> #include <list> #include <map> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <numeric> #include <functional> using namespace std; #define LL __int64 #define N 100005 #define MOD 1000000007 struct tt{ LL ma[2][2]; }; tt ksm(tt a,tt b,LL mod) { tt temp; int i,j,k; memset(temp.ma,0,sizeof(temp.ma)); for(i = 0 ; i < 2 ; i++) for(j = 0 ; j < 2 ; j++) for(k =0 ; k < 2 ; k++) temp.ma[i][j] = (temp.ma[i][j]+(a.ma[i][k]*b.ma[k][j])%mod)%mod; return temp; } LL solve(LL n,LL mod) { if(n == 0) return 0; tt p,q; p.ma[0][0] = 0,p.ma[0][1] = 1,p.ma[1][0] = 0,p.ma[1][1] = 1; q.ma[0][0] = 3,q.ma[0][1] = 1,q.ma[1][0] = 1,q.ma[1][1] = 0; while(n) { if(n&1) p = ksm(p,q,mod); q = ksm(q,q,mod); n/=2; } return p.ma[1][0]%mod; } int main() { LL n,g1 = 183120,g2 = 222222224; while(~scanf("%I64d",&n)) { printf("%I64d ",solve(solve(solve(n,g1),g2),MOD)); } return 0; }