题目来源：

https://ac.nowcoder.com/acm/contest/885/B

题意：

$已知a,b,x_0,x_1,P,x_n=a\times x_{n-1}+b\times x_{n-2},求x_{n}modP$已知a,b,x0​,x1​,P,xn​=a×xn−1​+b×xn−2​,求xn​modP

思路：

代码：

#include <bits/stdc++.h>

#define sz(x) (x).size()
using namespace std;
typedef long long ll;
struct matrix {
    ll m[2][2];
};
matrix I = {1,0,0,1};
ll x0,x1,a,b,mod;
string s;
inline matrix operator * (const matrix &A,const matrix &B) {
    matrix res = {0};
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                res.m[i][j] += A.m[i][k] * B.m[k][j] % mod;
                if (res.m[i][j] >= mod) res.m[i][j] -= mod;
            }
        }
    }
    return res;
}
matrix q_pow(matrix A,int x) {
    matrix res = I;
    while (x) {
        if (x & 1) res = A * res;
        A = A * A;
        x >>= 1;
    }
    return res;
}
ll solve() {
    matrix A = {a, b, 1, 0}, B = {x1, 0, x0, 0};
    int n = sz(s);
    for (int i = n - 1; ~i; --i) {
        if (s[i] - '0') {
            matrix t = q_pow(A, s[i] - '0');
            B = t * B;
        }
        A = q_pow(A, 10);
    }
    return B.m[1][0];
}
int main() {
    cin >> x0 >> x1 >> a >> b >> s >> mod;
    cout << solve() << '\n';
    return 0;
}