链接：https://ac.nowcoder.com/acm/contest/123788

A – 无穷无尽的力量

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    cout << string(n, 'a') << 'b' << string(n, 'a') << endl;
}

B – 无穷无尽的字符串

算法：

    数学。

思路：

    无。

关键代码：

void miyan()
{
    ll l, r;
    cin >> l >> r;

    int cnt1 = r / 3, cnt2 = r / 3, cnt3 = r / 3;

    int m = r % 3;
    if (m == 1)
        ++cnt1;
    else if (m == 2)
        ++cnt1, ++cnt2;

    --l;

    int cnta = l / 3, cntb = l / 3, cntc = l / 3;

    m = l % 3;
    if (m == 1)
        ++cnta;
    else if (m == 2)
        ++cnta, ++cntb;

    cout << cnt1 - cnta << ' ' << cnt2 - cntb << ' ' << cnt3 - cntc << endl;
}

C – 无穷无尽的力量2.0

算法：

    思维，分类讨论。

思路：

    无。

关键代码：

void miyan()
{
    ll n, m;
    cin >> n >> m;

    if (n > m)
        swap(n, m);

    if (n == 1)
        cout << 1 << endl;
    else if (n == 2)
        cout << (m + 1) / 2 << endl;
    else if (n == 3 && m == 3)
        cout << 8 << endl;
    else
        cout << n * m << endl;
}

D – 无穷无尽的小数

算法：

    模拟，高精度，\(lcm\)。

思路：

    可以发现 \(lcm(n, m)\) 必然是一个循环节。

    \(a\) 的小数部分可能小于 \(b\)，如果 \(a < b\)，需要向 \(a\) 的最后一位借 1。

关键代码：

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

void miyan()
{
    int n, m;
    string a, b;
    cin >> n >> m >> a >> b;

    int d = lcm(n, m);

    string A, B, C;
    for (int i = 0; i < d / n; ++i)
        A += a;
    for (int i = 0; i < d / m; ++i)
        B += b;

    int cnt = 0;

    if (a < b)
        cnt = -1;

    for (int i = d - 1; i >= 0; --i)
    {
        int cur = A[i] - B[i] + cnt;

        cnt = 0;

        if (cur < 0)
        {
            cur += 10;
            --cnt;
        }

        C.push_back(cur + '0');
    }

    cout << d << endl;

    ranges::reverse(C);
    cout << C << endl;
}

E – 无穷无尽的树

算法：

    树形\(dp\)。

思路：

    简单树形\(dp\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1, 0);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        ++deg[u], ++deg[v];
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }

    vector<int> dp(n + 1, 0);
    vector<int> h(n + 1, 1);
    auto dfs = [&](auto &&self, int u, int f) -> void
    {
        int maxx = 1;
        for (auto &v : g[u])
        {
            if (v == f)
                continue;

            self(self, v, u);

            h[u] = max(h[u], h[v] + 1);
            maxx = max(maxx, h[v]);
        }

        for (auto &v : g[u])
        {
            if (h[v] == maxx)
                dp[u] += dp[v];
        }

        if (deg[u] != 1 && !dp[u])
            dp[u] = 1;
    };

    dfs(dfs, 1, 0);

    for (int i = 1; i <= n; ++i)
        cout << dp[i] << ' ';
    cout << endl;
}

F – 无穷无尽的数

算法：

    快速幂，逆元。

思路：

    可以将需求区间分为三部分：\(suf + mid + pre\)

• \(suf =\) 字符串 \(s\) 的一段后缀
• \(mid =\) 连续的 \(k\) 段 \(s\)
• \(pre =\) 字符串 \(s\) 的一段前缀

    那么答案 \(= suf * 10 ^ {size(mid) + size(pre)} + mid * 10 ^ {size(pre)} + pre\)。

    对于 \(suf\) 和 \(pre\) 写一个 \(get\) 函数提取字符串子串值即可，类似字符串哈希获取子串哈希值的写法。

    对于 \(mid\) 是由 \(k\) 段 \(s\) 组成，那么 \(mid = nums(s) + nums(s) * 10 ^ {n} + nums(s) * 10 ^ {2n} + …..\)，可以发现是一个等比数列。

关键代码：

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

void miyan()
{
    ll n, l, r;
    string s;
    cin >> n >> l >> r >> s;

    --l, --r;
    s = ' ' + s;

    vector<ll> sum(n + 1, 0), pow(n + 1, 1);
    for (int i = 1; i <= n; ++i)
    {
        sum[i] = ((sum[i - 1] * 10ll % MOD) + (s[i] - '0')) % MOD;
        pow[i] = pow[i - 1] * 10ll % MOD;
    }

    auto get = [&](int l, int r) -> ll
    {
        return (sum[r + 1] - sum[l] * pow[r - l + 1] % MOD + MOD) % MOD;
    };

    ll pos1 = l / n, pos2 = r / n;
    ll suf = l % n;
    ll pre = r % n;
    ll len = pre + 1;
    ll t = pos2 - pos1 - 1;
    ll mid = t * n;

    if (pos1 == pos2)
    {
        cout << get(suf, pre) << endl;
        return;
    }

    ll ans1 = get(suf, n - 1) * qmi(10, mid + len, MOD) % MOD;
    ll ans2 = get(0, pre);
    ll ans3 = 0;

    if (t)
    {
        ll cnt = sum[n] * ((qmi(pow[n], t, MOD) - 1 + MOD) % MOD) % MOD * qmi(pow[n] - 1, MOD - 2, MOD) % MOD;
        ans3 = qmi(10, len, MOD) * cnt % MOD;
    }

    cout << (ans1 + ans2 + ans3) % MOD << endl;
}