2019牛客暑期多校训练营(第五场)B(十进制矩阵快速幂

题目来源:

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

题意:

思路:

在这里插入图片描述

代码:

#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;
}
点赞
  1. 六花Kami说道:

    评论测试1

  2. 六花Kami说道:

    评论测试2

  3. 111说道:

    评论测试2

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像