题解 | #digits 2#

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1E6 + 10;

int x0, x1, a, b, mod;
char str[N];

void mul(int a[2][2], int b[2][2], int c[2][2])
{
         int t[2][2];
    memset(t, 0, sizeof t);
    
    for(int i = 0; i < 2; i ++)
        for(int j = 0; j < 2; j ++)
            for(int k = 0; k < 2; k ++)
                t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j]) % mod;
    
    memcpy(c, t, sizeof t);
}

void qmi(int a[][2], int k, int c[][2])
{
    int t[2][2] = 
    {
        {1, 0},
        {0, 1},
    };
    
    while(k)
    {
        if(k & 1) mul(a, t, t); // 需要将系数矩阵
        mul(a, a, a);
        k >>= 1;
    }
    
    memcpy(c, t, sizeof t);
}

int main()
{
    scanf("%d%d%d%d%s%d", &x0, &x1, &a, &b, str, &mod);
    
    int f[2][2] = {
        {x0, x1},
        {0, 0},
    };
    
    int A[2][2] = {
        {0, b},
        {1, a},
    };
    
    int n = strlen(str);
    for(int i = n - 1; i >= 0; i --) // 10进制快速幂，每一位对f的贡献应为其权重乘以系数，而二进制的系数为1，省去这一步
    { // 快速幂第二步，移位操作，枚举下一个数位
        int t = str[i] - '0';
        
        if(t) // 当前位不为0，对答案有贡献，贡献为系数乘以权重t 一般快速幂第一步
        {
            int back[2][2];
            
            memcpy(back, A, sizeof A); // 保留权重信息
            qmi(back, t, back); // 将权重当作单位1，需要快速幂求出系数矩阵当前位对f矩阵的贡献
            mul(f, back, f); // 将f矩阵乘以系数矩阵当前位的贡献
        }
        
        qmi(A, 10, A); // 一般快速幂第三步，稀疏矩阵的权重变为下一位的权重，在二进制中，即nul(A, A, A)自己与自己矩阵乘法
    }
    
    printf("%d", f[0][0]);
    
    return 0;
}