abc板刷记录

最近训练太不勤快了！决定用 atcoder beginner contest 给25级小登训练的同时，自己也跟上进度。

给自己立下束缚：从 3 月 16 号开始，到下一个大事件发生为止。必须同步补完训练的每场abc。并且对于赛后补的题，把题解写到这个博客！

abc448_e

题解

$\lfloor {n\over m} \rfloor \pmod p \rightleftarrows \lfloor{n \pmod{mp}\over m}\rfloor$, 这样就能先算 $n$。求 $n$ 的难点在于求连续的 $111\dots11$，由于 $9^{-1}\pmod{mp}$ 未必存在，所以要避开求逆。
可以倍增求，记 $R_l = 111\dots11 (len = l)$，那么 $R_{2^k} = R_{2^{k - 1}}\times (10^{2^{k - 1}} + 1)$。预处理出 $R_{2^k}$ 后，$R_l = \sum R_{2^{k_i}}\times 10^{} (l = 2^{k_1} + 2^{k_2} + \dots)$。比如 $R_{11} = 11111111 11 1$ 可以拆成 $R_8\times 10^3 + R_2\times 10 ^ 1 + R_1\times 10^0$。
本质不算太难，就是指数来回绕。

另外很重要的一点：指数不能直接取模，参见欧拉定理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
auto Mikasa() {
    ll k, n = 0, m;
    cin >> k >> m;
    const ll Mod = 10007 * m;
    vector<ll> Rpow2(55); // 111..111; len = 2^k
    vector<ll> suffix(k + 1);
    vector<pair<ll, ll>> cl(k + 1);

    Rpow2[0] = 1;
    for (ll i = 1; i < Rpow2.size(); ++i) {
        const ll pra = (1 + fastpow(10, 1ll << (i - 1), Mod)) % Mod;
        (Rpow2[i] = pra * Rpow2[i - 1]) %= Mod;
    }

    for (ll i = 1; i <= k; ++i) 
        cin >> cl[i].first >> cl[i].second;
    for (ll i = k - 1; i >= 1; --i) 
        suffix[i] = suffix[i + 1] + cl[i + 1].second;

    auto getR = [&](ll pownum)->ll {
        ll ans = 0;
        for (ll h = 50; h >= 0; --h) {
            if ((pownum >> h) & 1) {
                (ans *= fastpow(10, 1ll << h, Mod)) %= Mod;
                (ans += Rpow2[h]) %= Mod;
            }
        }
        return ans;
    };

    for (ll i = 1; i <= k; ++i) {
        (n += cl[i].first * getR(cl[i].second) % Mod * fastpow(10, suffix[i], Mod) % Mod) %= Mod;
    }
    cout << n / m << endl;
}