洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)

题意

题目链接

sol

感觉做这题只要对矩阵乘法理解的稍微一点就能做出来
对于每一行构造一个矩阵
a = a 1
      0 b
列与列之间的矩阵为
b = c 1
      0 d
最终答案为
$a^{n - 1}b a^{n - 1}b \dots $
把$a^{n-1}b$看成一项进行快速幂即可

---

 

maya把数据范围看漏了1e6个0。。。。。。。

好像把快速幂换成十进制快速幂就行了

/*
感觉做这题只要对矩阵乘法理解的稍微一点就能做出来
对于每一行构造一个矩阵
a = a 1
    0 b
列与列之间的矩阵为
b = c 1
    0 d
最终答案为
$a^{n - 1}b a^{n - 1}b$
把$a^{n-1}b$看成一项进行快速幂即可

maya把数据范围看漏了1e6个0。。。。。。。

好像把快速幂换成十进制快速幂就行了
*/
#include<bits/stdc++.h>
#define ll long long 
#define int long long 
const int maxn = 1e6 + 10, mod = 1e9 + 7, l = 2;
using namespace std;
char t1[maxn], t2[maxn];
int n[maxn], m[maxn], a, b, c, d, n, m;
int mod(int x, int y) {
    if(1ll * x * y > mod) return 1ll * x * y % mod;
    else return 1ll * x * y;
}
int add(int x, int y) {
    if(x + y > mod) return x + y - mod;
    else return x + y;
}
struct matrix {
    int m[4][4];
    matrix() {
        memset(m, 0, sizeof(m));
    }
    matrix operator * (const matrix &rhs) const {
        matrix ans;
        /*for(int k = 1; k <= l; k++)
            for(int i = 1; i <= l; i++)
                for(int j = 1; j <= l; j++)
                    (ans.m[i][j] +=  1ll * m[i][k] * rhs.m[k][j] % mod) %= mod;*/
        ans.m[1][1] = add(mod(m[1][1], rhs.m[1][1]), mod(m[1][2], rhs.m[2][1]));
        ans.m[1][2] = add(mod(m[1][1], rhs.m[1][2]), mod(m[1][2], rhs.m[2][2]));
        ans.m[2][1] = add(mod(m[2][1], rhs.m[1][1]), mod(m[2][2], rhs.m[2][1]));
        ans.m[2][2] = add(mod(m[2][1], rhs.m[1][2]), mod(m[2][2], rhs.m[2][2]));
        return ans;
    }
};
matrix fp(matrix a, int *p, int len) {
    matrix base;
    for(int i = 1; i <= 3; i++) base.m[i][i] = 1;
    for(int i = len; i >= 1; i--) {
        for(int j = 1; j <= p[i]; j++) base = base * a;
        matrix tmp = a;
        a = a * a; a = a * a; a = a * a; a = a * tmp * tmp;
    }
    return base;
}
int trans(char *s, int l, int *to) {
    for(int i = 1; i <= l; i++) to[i] = s[i] - '0';
    to[l]--;
    for(int i = l; i >= 1; i--) 
        if(to[i] < 0) to[i - 1] += to[i], to[i] = 10 + to[i];
        else break;
    return l;
}
main() {
//    freopen("a.in", "r", stdin);
    scanf("%s%s%d%d%d%d", t1 + 1, t2 + 1, &a, &b, &c, &d);
    n = strlen(t1 + 1); m = strlen(t2 + 1);
    n = trans(t1, n, n); m = trans(t2, m, m);

    matrix x, y;
    x.m[1][1] = a; x.m[1][2] = b;
    x.m[2][1] = 0; x.m[2][2] = 1;
    y.m[1][1] = c; y.m[1][2] = d;
    y.m[2][1] = 0; y.m[2][2] = 1;

    matrix debug = fp(x, m, m) ;
    debug = debug * y;
    matrix ans = fp(debug, n, n);
    ans = ans * fp(x, m, m);
    cout << (ans.m[1][1] + ans.m[1][2]) % mod;
}