辛有才网络营销-2015沈阳网络赛 1002（HDU 5451 矩阵快速幂 + 矩阵循环群）

hrzl7092

HDU 5451 题意：  
  输入 x ( 0 > t ; int kase = 1 ; while( t-- )#define out( kase ) printf( "Case #%d: " , kase++ )#define mp make_pair#define pb push_backtypedef long long lint;typedef long long ll;typedef long long LL;int mod ;const int maxn = 4;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 >= 1; } return res;}lint quick_pow( lint x , lint n , lint p ){ lint res = 1 ; x %= p ; while( n ){ if( n & 1 ) res = res * x % p ; n >>= 1 ; x = x * x % p ; } return res ;}void solve(){ lint n , x; cin >> x >> mod ; lint MOD = ( mod - 1 ) * ( mod + 1 ) ; n = quick_pow( 2 , x , MOD ) + 1 ; if( n == 0 ){ cout << 1 << endl ; return ; } if(n == 1){ cout << 9 << endl; return; } Matrix base(2,1); Matrix fun(2,2); base.a[0][0] = 5; base.a[1][0] = 2; fun.a[0][0] = 5; fun.a[0][1] = 12; fun.a[1][0] = 2; fun.a[1][1] = 5; fun = fast_pow(fun,n-1); base = fun * base; cout << (2*base.a[0][0] - 1) % mod << endl;}int main(){ //freopen( "input.txt" , "r" , stdin ) ; test( t ){ out( kase ) ; solve(); } return 0;}