[HDOJ5667]Sequence（矩阵快速幂，费马小定理）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5667

费马小定理：

假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）。

即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

注意这里使用快速幂的时候要根据费马小定理对p-1取模。还有注意a%p=0的情况。

递推式：f(n)=f(n-1)*c+f(n-2)+1 非齐次。

构造矩阵：

|c  |

|  |

|  |

初始的矩阵：

||

||

||

 #include <algorithm>

 #include <iostream>

 #include <iomanip>

 #include <cstring>

 #include <climits>

 #include <complex>

 #include <fstream>

 #include <cassert>

 #include <cstdio>

 #include <bitset>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <ctime>

 #include <set>

 #include <map>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const ll maxn = ;

 ll n, a, b, c, p;

 typedef struct Matrix {

     ll m[maxn][maxn];

     ll r;

     ll c;

     Matrix(){

         r = c = ;

         memset(m, , sizeof(m));

     }

 } Matrix;

 Matrix mul(Matrix m1, Matrix m2, ll mod) {

     Matrix ans = Matrix();

     ans.r = m1.r;

     ans.c = m2.c;

     for(ll i = ; i <= m1.r; i++) {

         for(ll j = ; j <= m2.r; j++) {

                for(ll k = ; k <= m2.c; k++) {

                 if(m2.m[j][k] == ) continue;

                 ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod;

             }

         }

     }

     return ans;

 }

 Matrix quickmul(Matrix m, ll n, ll mod) {

     Matrix ans = Matrix();

     for(ll i = ; i <= m.r; i++) {

         ans.m[i][i]  = ;

     }

     ans.r = m.r;

     ans.c = m.c;

     while(n) {

         if(n & ) {

             ans = mul(m, ans, mod);

         }

         m = mul(m, m, mod);

         n >>= ;

     }

     return ans;

 }

 ll qm(ll x, ll n, ll mod) {

     ll ans = , t = x;

     while(n) {

         if(n & ) ans = (ans * t) % mod;

         t = (t * t) % mod;

         n >>= ;

     }

     return ans;

 }

 int main() {

     // freopen("in", "r", stdin);

     int T;

     scanf("%d", &T);

     while(T--) {

         cin >> n >> a >> b >> c >> p;

         Matrix r;

         r.r = , r.c = ;

         r.m[][] = ;

         r.m[][] = ;

         r.m[][] = ;

         if(n == ) {

             printf("1\n");

             continue;

         }

         if(n == ) {

             printf("%I64d\n", qm(a, b, p));

             continue;

         }

         if(a % p == ) {

             printf("0\n");

             continue;

         }

         Matrix s;

         s.r = s.c = ;

         s.m[][] = c, s.m[][] = , s.m[][] = ;

         s.m[][] = , s.m[][] = , s.m[][] = ;

         s.m[][] = , s.m[][] = , s.m[][] = ;

         s = quickmul(s, n-, p-);

         ll ans = ;

         for(int i = ; i <= r.r; i++) {

             ans = (ans + (s.m[][i] * r.m[i][]) % (p - )) % (p - );

         }

         printf("%I64d\n", qm(a, (ans*b)%(p-), p));

     }

     return ;

 }