矩陣快速冪

把指數按十進制拆開的快速冪。。。

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define full(a, b) memset(a, b, sizeof a) #define __fastIn ios::sync_with_stdio(false), cin.tie(0) #define pb push_back using namespace std; typedef long long LL; inline int lowbit(int x){ return x & (-x); } inline int read(){int ret = 0, w = 0; char ch = 0;while(!isdigit(ch)){w |= ch == '-', ch = getchar();}while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ 48);ch = getchar();}return w ? -ret : ret; } inline int lcm(int a, int b){ return a / __gcd(a, b) * b; } template <typename A, typename B, typename C> inline A fpow(A x, B p, C lyd){A ans = 1;for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;return ans; } LL x0, x1, a, b, p; string n; struct Matrix{LL m[2][2];Matrix(){full(m, 0);}Matrix operator * (Matrix &a){Matrix ret;for(int i = 0; i < 2; i ++){for(int j = 0; j < 2; j ++){for(int k = 0; k < 2; k ++){ret.m[i][j] = ret.m[i][j] + (m[i][k] * a.m[k][j] % p);if(ret.m[i][j] >= p) ret.m[i][j] -= p;}}}return ret;} }; Matrix ori, t, e; inline void init(){e.m[0][0] = e.m[1][1] = 1;ori.m[0][0] = x1, ori.m[1][0] = x0;t.m[0][0] = a, t.m[0][1] = b, t.m[1][0] = 1; }inline Matrix fpow(Matrix &a, const string &n){Matrix ret = e;for(int i = n.size() - 1; i >= 0; i --){int y = n[i] - '0';while(y --) ret = ret * a;Matrix tr = a * a;a = tr * tr;a = a * a * tr;//for(int j = 1; j <= 9; j ++) a = a * tr;}return ret; }int main(){__fastIn;cin >> x0 >> x1 >> a >> b;cin >> n >> p;init();t = fpow(t, n);ori = t * ori;cout << (ori.m[1][0] % p) << endl;return 0; }

轉載于:https://www.cnblogs.com/onionQAQ/p/11294161.html

總結

以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第五场）- generator 1的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。