题目链接

思路

十进制矩阵快速幂。
代码

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson (rt<<1),L,mid

#define rson (rt<<1|1),mid + 1,R

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)

#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;

const int mod = 1000000007;

const int maxn = 1000000 + 7;

const double pi = acos(-1);

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int MOD;

char s[maxn];

struct matrix {

    int a[2][2];

    matrix operator * (const matrix& x) const {

        matrix b;

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

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

                b.a[i][j] = 0;

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

                    b.a[i][j] = (b.a[i][j] + 1LL * a[i][k] * x.a[k][j] % MOD) % MOD;

                }

            }

        }

        return b;

    }

}x, A[10];

matrix qpow(matrix x, int n) {

    matrix b;

    memset(b.a, 0, sizeof(b.a));

    b.a[0][0] = b.a[1][1] = 1;

    while(n) {

        if(n & 1) b = b * x;

        x = x * x;

        n >>= 1;

    }

    return b;

}

int main() {

#ifndef ONLINE_JUDGE

    FIN;

#endif

    memset(x.a, 0, sizeof(x.a));

    scanf("%d%d%d%d", &x.a[0][1], &x.a[0][0], &A[1].a[0][0], &A[1].a[1][0]);

    A[1].a[0][1] = 1;

    scanf("%s%d", s + 1, &MOD);

    for(int i = 2; i <= 9; ++i) A[i] = A[i-1] * A[1];

    int n = strlen(s + 1);

    matrix ans = A[s[1]-'0'];

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

        ans = qpow(ans, 10);

        if(s[i] > '0') {

            ans = ans * A[s[i]-'0'];

        }

    }

    ans = x * ans;

    printf("%d\n", ans.a[0][1]);

    return 0;

}
十进制矩阵快速幂

generator 1(2019年牛客多校第五场B题+十进制矩阵快速幂)

题目链接

思路

代码
