2019牛客多校第五场B-generator 1(矩阵快速幂)

generator 1

题目传送门

解题思路

矩阵快速幂。只是平时的矩阵快速幂是二进制的，这题要用十进制的快速幂。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

ll mod;

struct Matrix{

    ll m[2][2];

    Matrix(){

        m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0;

    }

    Matrix operator*(const Matrix& a)const{

        Matrix ans;

        for(int i = 0; i < 2; i ++){

            for(int j = 0; j < 2; j ++)

                for(int k = 0; k < 2; k ++)

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

        }

        return ans;

    }

};

Matrix fpow(const Matrix& x, string str)

{

    int k = str.size() - 1;

    Matrix t = x;

    Matrix ans;

    ans.m[0][0] = 1, ans.m[1][1] = 1;

    while(k >= 0){

        for(int i = 1; i <= str[k] - '0'; i ++)

            ans = ans * t;

        Matrix temp = t * t;

        t = temp * temp;

        t = t * t * temp;

        --k;

    }

    return ans;

}

int main()

{

    ios::sync_with_stdio(false);

    ll x0, x1, a, b;

    string n;

    cin >> x0 >> x1 >> a >> b >> n >> mod;

    Matrix t;

    t.m[0][0] = a, t.m[0][1] = b, t.m[1][0] = 1;

    Matrix ans = fpow(t, n);

    printf("%lld\n", (ans.m[1][0] * x1 + ans.m[1][1] * x0) % mod);

    return 0;

}