HDU 4291题意：
思路：
开始的想法是一层层的求出来，后来发现是错的。只有最外层能模除. 这里有一个知识点：循环节。只要是模除一个数，，模除多次后一定会出现想循环小数一样的循环节。 如果只有一层，那么大概计算结果模除10^9+7这个数222222224次后（可暴力找到）开始循环，即
于是更换mod值用三次快速矩阵幂模板即可。
代码：/** @author FreeWifi_novicer* language : C++/C*/;lint;ll;LL;const int maxn = 4;lint mod;lint n,m,k;struct Matrix{int n , m ;lint a[maxn][maxn];Matrix( int n , int m ){this->n = n ;this->m = m ;cls(a);}Matrix operator * ( const Matrix &tmp ){Matrix res( n , tmp.m );for( int i = 0 ; i < n ; i++ )for( int j = 0 ; j < tmp.m ; j++ )for( int k = 0 ; k < m ; k++ )res.a[i][j] = ( res.a[i][j] + ( a[i][k] * tmp.a[k][j] ) % mod ) % mod;return res;}};void Matrix_print( Matrix x ){for( int i = 0 ; i < x.n ; i++ ){for( int j = 0 ; j < x.m ; j++){cout << x.a[i][j] << ‘ ‘;}cout << endl;}cout << endl;}Matrix fast_pow( Matrix x , lint n ){Matrix res( x.n , x.m );for( int i = 0 ; i < x.n ; i++ ) res.a[i][i] = 1;while( n ){if( n & 1 )res = res * x;x = x * x;n >>= 1;}return res;}void solve(){if( n <= 1 ){printf(“%I64d\n”,n);return;}Matrix base( 2 , 1 );Matrix fun( 2 , 2 );fun.a[0][0] = 3 ;fun.a[0][1] = 1 ;fun.a[1][0] = 1 ;fun.a[1][1] = 0 ;base.a[0][0] = 1 ;base.a[1][0] = 0 ;Matrix fun1( 2 , 2 ) , fun2( 2 , 2 ) , fun3( 2 , 2 );Matrix base1( 2 , 1 ) , base2( 2 , 1 ) , base3( 2 , 1 );mod = 183120;fun1 = fast_pow( fun , n – 1 );base1 = fun1 * base ;if( base1.a[0][0] == 0 ){cout << 0 << endl;return ;}mod = 222222224;fun2 = fast_pow( fun , base1.a[0][0] – 1 );base2 = fun2 * base ;if( base2.a[0][0] == 0 ){cout << 0 << endl;return ;}mod = 1e9 + 7;fun3 = fast_pow( fun , base2.a[0][0] – 1 );base3 = fun3 * base ;printf( “%I64d\n” , base3.a[0][0] % mod );}int main(){// freopen(“input.txt”,”r”,stdin);while( scanf( “%I64d” , &n ) != EOF ){solve();}return 0;}
一路走来，我们无法猜测将是迎接什么样的风景，
