题解：AT_abc129_f [ABC129F] Takahashi's Basics in Education and Learning

· · 题解

思路：

不难想到分段做矩阵乘法。对于每一个段，二分在这一个段内原序列元素的个数。假定当前段的范围是 10^x 到 10^{x+1}-1，那么有 f_i=10^{x+1}f_{i-1}+A+B\times i。我们记 g_i=g_{i-1}+1，转移式变为 f_i=10^{x+1}f_{i-1}+A+B\times g_{i-1} 那么我们可以构造出矩阵。

\begin{bmatrix}10^{x+1}&B&1&0\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{bmatrix}

用这个矩阵与

\begin{bmatrix}f_{i-1}\\g_{i-1}\\A\\1\end{bmatrix}

相乘即可得到当前位置的答案矩阵

\begin{bmatrix}f_i\\g_i\\A\\1\end{bmatrix}

对其进行矩阵加速即可立刻算出到这一段末尾时的答案。

AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll l, a, b, nl = 1, nr = 1, nw;
int m, ls;
vector<ll> f(4);
struct node {
    ll p[4][4];
} d;
ll qm(ll a, int b) {
    ll ans = 1;
    while(b) {
        if(b & 1)  ans = ans * a;
        b >>= 1, a = a * a;
    }
    return ans;
}
bool check(ll md, int x, int op) {
    if(op == 0) if(a + b * md <= qm(10ll, x) - 1) return true;
    if(op == 1) if(a + b * md >= qm(10ll, x)) return true;
    return false;
}
node pw(node a, node b) {
    node c;
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            c.p[i][j] = 0;
            for(int k = 0; k < 4; k++) {
                c.p[i][j] = (c.p[i][j] + (ll)(a.p[i][k] % m * (b.p[k][j] % m)) % m) % m;
            }
        }
    }
    return c;
}
vector<ll> mul(node a, vector<ll> b) {
    vector<ll> c(4);
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            c[i] = (ll)(c[i] + (ll)(a.p[i][j] % m * (b[j] % m)) % m) % m;
        }
    }
    return c;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> l >> a >> b >> m;
    for(int i = 0; i < 18; i++) {
        if(qm(10ll, i) > a + b * (l - 1)) break;
        ll ql = 0, qr = l - 1, nl = 0, nr = 0;
        while(ql <= qr) {
            ll mid = ql + qr >> 1ll;
            if(check(mid, i + 1, 0)) ql = mid + 1, nr = mid;
            else qr = mid - 1;
        }
        if(a + b * nr > qm(10ll, i + 1) - 1) continue;
        ql = 0, qr = l - 1;
        while(ql <= qr) {
            ll mid = ql + qr >> 1ll;
            if(check(mid, i, 1)) qr = mid - 1, nl = mid;
            else ql = mid + 1;
        }
        if(nl > nr) continue;
        d.p[0][0] = qm(10ll, i + 1), d.p[0][1] = b, d.p[0][2] = 1, d.p[0][3] = 0;
        d.p[1][0] = 0, d.p[1][1] = 1, d.p[1][2] = 0, d.p[1][3] = 1;
        d.p[2][0] = 0, d.p[2][1] = 0, d.p[2][2] = 1, d.p[2][3] = 0;
        d.p[3][0] = 0, d.p[3][1] = 0, d.p[3][2] = 0, d.p[3][3] = 1;
        f[0] = ls, f[1] = nl, f[2] = a, f[3] = 1;
        for(ll i = nr - nl + 1; i >= 1; i >>= 1) {
            if(i & 1) f = mul(d, f);
            d = pw(d, d);
        }
        ls = f[0];
    }
    cout << ls;
    return 0;
}