矩阵快速幂

算法封装模板
点击查看代码

1. struct matrix {
2.         vector<vector<int>>a,b;
3.         int n;
4.         matrix (int n1):n(n1),a(n1,vector<int>(n1,0)),b(n1,vector<int>(n1,0)){}
5.           matrix operator-(const mat& T) const {
6.     matrix res(n);
7.     for(int i = 0; i < n; ++i)
8.             for (int j = 0; j < n; ++j) {
9.                 res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
10.             }
11.             return res;
12.           }
13.         matrix operator+(const mat& T) const {
14.                 matrix res(n);
15.                 for (int i = 0; i < n; ++i)
16.                         for (int j = 0; j < n; ++j){
17.                             res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
18.                         }
19.                 return res;
20.         }
21.           matrix operator*(const mat& T) const {
22.                    matrix res(n);
23.                    int r;
24.                    for (int i = 0; i < n; ++i)
25.                      for (int k = 0; k < n; ++k) {
26.                                r = a[i][k];
27.                                for (int j = 0; j < n; ++j)
28.                                   res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= mod;
29.                       }
30.             return res;
31.    }
32.         matrix operator^(int x) const {
33.             matrix res(n), bas(n);
34.             for (int i = 0; i < n; ++i) res.a[i][i] = 1;
35.             for (int i = 0; i < n; ++i)
36.                     for (int j = 0; j < n; ++j) bas.a[i][j] = b[i][j]%mod;
37.             while (x) {
38.                       if (x & 1) res = res * bas;
39.                       bas = bas * bas;
40.                       x >>= 1;
41.             }
42.             return res;
43.         }
44. };

复制代码

例题
[例题](https://atcoder.jp/contests/abc293/tasks/abc293_e?lang=en）

思路
从题意可知，这个题明显不能用逆元，因为用费马小定理的限制是模数mod必须是质数。
而使用扩展欧几里得求逆元的条件是这个公式中\(ax \equiv 1 \pmod m\)必须满足\(gcd(a,m)==1\)条件，很明显这个题目是不满足的，
所以我们可以考虑使用矩阵加速来解决这个问题，\(x>=1;                a=a*a%m;                }        return res;}int gcd(int a,int b){        return b?gcd(b,a%b):a;}int lcm(int a,int b){        return a*b/gcd(a,b);}struct mat {        vectora;        int n;        mat (int n1):n(n1),a(n,vector(n,0)){}          mat operator-(const mat& T) const {    mat res(n);    for(int i = 0; i < n; ++i)              for (int j = 0; j < n; ++j) {                res.a[j] = (a[j] - T.a[j]) % MOD;              }            return res;          }                mat operator+(const mat& T) const {                    mat res(n);                    for (int i = 0; i < n; ++i)                            for (int j = 0; j < n; ++j){                                res.a[j] = (a[j] + T.a[j]) % MOD;                            }                    return res;                }                  mat operator*(const mat& T) const {            mat res(n);            int r;            for (int i = 0; i < n; ++i)              for (int k = 0; k < n; ++k) {                r = a[k];                for (int j = 0; j < n; ++j)                          res.a[j] += T.a[k][j] * r, res.a[j] %= MOD;                      }                    return res;                  }          mat operator^(int x) const {            mat res(n), bas(n);            for (int i = 0; i < n; ++i) res.a = 1;            for (int i = 0; i < n; ++i)              for (int j = 0; j < n; ++j) bas.a[j] = a[j] % MOD;            while (x) {              if (x & 1) res = res * bas;              bas = bas * bas;              x >>= 1;            }            return res;          }};//int e[N],ne[N],h[N],idx,w[N],in[N],out[N];//void add(int a,int b,int c){//        e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;//}signed main(){        ios::sync_with_stdio(0);        cin.tie(0);        cout.tie(0);        int _=1;        //cin>>_;        while(_--){                int a,x,m;cin>>a>>x>>m;                MOD=m;                mat ma(2);                ma.a[0][0]=a%m,ma.a[0][1]=1;                ma.a[1][1]=1;                ma=(ma^x);                cout