AtCoder Beginner Contest 449 题解

for-each2026年8月18日大约 20 分钟

AtCoder Beginner Contest 449 题解

项目	内容
比赛时间	2026-03-14
比赛链接	https://atcoder.jp/contests/abc449
题目数量	A–G 共 7 题

比赛概览

本场难度梯度非常清晰：A、B 是纯粹的签到题（圆面积公式、矩形模拟）；C 是经典的滑动窗口计数；D 是把"二维计数"拆成两个一维情形的分类讨论，验证基本功。从 E 开始进入需要"建模"的题目：E 把看似无穷（ $10^{100}$ 次）的操作压缩成"按频率分阶段循环追加"的结构，配合离线 BIT 回答查询；F 是求矩形并面积的扫描线 + multiset 经典套路；G 是全场最难，需要先对 repunit 之和做一步巧妙的变换（化为 $10$ 的幂之和），再借助生成函数与差分方程在 $O(N)$ 时间内完成计数。E、F、G 分别代表"过程压缩""扫描线""生成函数"三个值得反复练习的知识点，是本题的区分度所在。

A - π

题目链接：https://atcoder.jp/contests/abc449/tasks/abc449_a

题目大意

给定正整数 $D$ ，求直径为 $D$ 的圆的面积。输出与真实值的绝对误差或相对误差不超过 $10^{-6}$ 即判为正确。

思路

圆面积公式为 $S=\pi r^2$ 。直径 $D$ 是半径的两倍，即 $r=\dfrac{D}{2}$ ，代入得：

S=\pi\left(\frac{D}{2}\right)^2=\frac{\pi D^2}{4}

直接计算并输出即可。取 $\pi$ 的方式：C++ 中用 acos(-1.0)（跨平台可移植，比 M_PI 更稳妥），Python 中用 math.pi。

易错点：精度要求宽松（ $10^{-6}$ ），但输出时仍应保留足够多的小数位（例如 C++ 固定输出 20 位），避免浮点截断造成误差。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int D;
    cin >> D;
    cout << fixed << setprecision(20) << acos(-1.0) * D * D / 4.0 << '\n';
    return 0;
}

官方题解给出的 Python 实现：

from math import pi
d = int(input())
print(d * d * pi / 4)

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Deconstruct Chocolate

题目链接：https://atcoder.jp/contests/abc449/tasks/abc449_b

题目大意

有一块 $H$ 行 $W$ 列（每格为一块）的矩形巧克力。依次处理 $Q$ 个操作，每个操作输出吃掉的数量：

操作 1：给定 $R$ ，吃掉最下面 $R$ 行，输出被吃掉的块数；
操作 2：给定 $C$ ，吃掉最右边 $C$ 列，输出被吃掉的块数。

保证每次操作后巧克力仍然是矩形（即操作 1 前至少有 $R+1$ 行、操作 2 前至少有 $C+1$ 列）。

思路

题目保证操作后巧克力始终保持矩形，所以只需要用两个变量 $h, w$ 维护"当前巧克力的行数、列数"，直接模拟：

操作 1：最下面 $R$ 行共 $R\times w$ 块，输出 $R\times w$ ，然后令 $h \leftarrow h - R$ ；
操作 2：最右边 $C$ 列共 $h\times C$ 块，输出 $h\times C$ ，然后令 $w \leftarrow w - C$ 。

为什么正确：吃掉最下面 $R$ 行后，剩余部分仍是 $h-R$ 行 $w$ 列的矩形（顶部与左右边界不动）；同理吃掉最右边 $C$ 列后剩下 $h$ 行 $w-C$ 列。题目保证 $h>R$ 、 $w>C$ 恒成立，因此模拟不会出现非法的空矩形。

易错点：操作 1 的答案是 $R \times w$ （用的是当前的列数），操作 2 的答案是 $h \times C$ （用当前的行数），不要用错；更新要在输出之后进行。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int h, w, q;
    cin >> h >> w >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int r;
            cin >> r;
            cout << 1LL * r * w << '\n';
            h -= r;
        } else {
            int c;
            cin >> c;
            cout << 1LL * h * c << '\n';
            w -= c;
        }
    }
    return 0;
}

复杂度分析

时间复杂度： $O(Q)$
空间复杂度： $O(1)$

C - Comfortable Distance

题目链接：https://atcoder.jp/contests/abc449/tasks/abc449_c

题目大意

给定长度为 $N$ 的小写字母字符串 $S$ 。统计满足以下条件的整数对 $(i,j)$ 的个数：

$1\le i\le j\le N$ ；
$S_i=S_j$ ；
$L\le j-i\le R$ 。

思路

固定右端点。对于每个 $j$ ，满足条件的 $i$ 必须落在区间 $j-R\le i\le j-L$ 内，且 $S_i=S_j$ 。于是问题变成：对每个 $j$ ，统计窗口 $[j-R,\ j-L]$ 中字符 $S_j$ 的出现次数，全部累加。

滑动窗口差分法：把窗口内各字符的出现次数存在数组 cnt[26] 中。随着 $j$ 每次右移一步，窗口 $[j-R,\ j-L]$ 恰好滑出一个元素（ $j-R$ 处）并滑入一个元素（ $j-L$ 处），可以在 $O(1)$ 内差分更新。把 $R$ 先自增 $1$ 可以避免边界判断，具体如下（均用 0-indexed）：

\text{cnt 维护的下标范围}=\left[i-(R+1)+1,\ i-L\right]=[i-R,\ i-L]

对 $i=0,1,\dots,N-1$ ：

若 $i\ge L$ ，加入 $S_{i-L}$ ：cnt[s[i-L]]++；
若 $i\ge R+1$ ，移出 $S_{i-R-1}$ ：cnt[s[i-R-1]]--；
累加 cnt[s[i]]。

为什么正确：每个满足条件的无序配对由它的右端点 $j$ 唯一决定，且当 $j$ 恰好取到该右端点时， $i$ 恰好落在当前维护的窗口内，因此每个配对被且仅被统计一次。 $L\ge 1$ 保证了 $i\ne j$ ，窗口内不包含 $j$ 自身，不会把自己算进去。

易错点：窗口是闭区间 $[j-R, j-L]$ ，长度为 $R-L+1$ ；先加入再移出、或先移出再加入都不影响正确性，但要注意下标越界判断。答案最大约为 $\binom{N}{2}\approx 1.25\times 10^{11}$ ，必须用 64 位整数。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, l, r;
    cin >> n >> l >> r;
    r++;                    // 提前 +1，简化滑动窗口的边界判断
    string s;
    cin >> s;
    ll ans = 0;
    vector<int> cnt(26);
    for (int i = 0; i < n; i++) {
        if (i >= l) cnt[s[i - l] - 'a']++;   // 窗口右端新进入 S[i-l]
        if (i >= r) cnt[s[i - r] - 'a']--;   // 窗口左端滑出 S[i-r]
        ans += cnt[s[i] - 'a'];              // 统计以 i 为右端点的配对
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N)$ （每个字符至多进出窗口一次）
空间复杂度： $O(26)$

D - Make Target 2

题目链接：https://atcoder.jp/contests/abc449/tasks/abc449_d

题目大意

二维坐标平面上，格点 $(x,y)$ 当 $\max(|x|,|y|)$ 为偶数时涂黑，为奇数时涂白。给定矩形 $L\le x\le R,\ D\le y\le U$ ，求其中黑色格点的个数。

思路

关键是处理 $\max(|x|,|y|)$ 。对任意格点，它恰好属于以下两种情形之一：

情形一： $|x|>|y|$ ，此时 $\max(|x|,|y|)=|x|$ ，要求 $|x|$ 为偶数。对每个偶数 $x\in[L,R]$ ， $y$ 需要满足 $|y|<|x|$ ，即 $-|x|<y<|x|$ ，等价于

-|x|+1\le y\le |x|-1

再与区间 $[D,U]$ 求交，个数为

\max\left(0,\ \min(U,\ |x|-1)-\max(D,\ -|x|+1)+1\right)

情形二： $|x|\le|y|$ ，此时 $\max(|x|,|y|)=|y|$ ，要求 $|y|$ 为偶数。对每个偶数 $y\in[D,U]$ ， $x$ 满足 $|x|\le|y|$ ，即

-|y|\le x\le |y|

与 $[L,R]$ 求交，个数为

\max\left(0,\ \min(R,\ |y|)-\max(L,\ -|y|)+1\right)

两种情形互斥且并集覆盖所有格点，因此答案就是两部分的简单求和。坐标范围 $|L|,|R|,|D|,|U|\le 10^6$ ，直接枚举所有偶数 $x$ 与偶数 $y$ 即可。

易错点：情形一的不等式是严格小于（ $|y|<|x|$ ），所以下界是 $-|x|+1$ ；情形二是不等号（ $|x|\le|y|$ ），下界是 $-|y|$ 。二者边界差 1，写反会导致答案相差一行（列）的计数。另外用 $\max(\cdot,0)$ 处理区间为空的情形。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int L, R, D, U;
    cin >> L >> R >> D >> U;
    ll ans = 0;

    // |x| > |y|：max = |x|，需要 |x| 为偶数
    for (int x = L; x <= R; x++) {
        if (x % 2 == 0) {
            int lo = max(D, -abs(x) + 1);
            int hi = min(U, abs(x) - 1);
            ans += max(0, hi - lo + 1);
        }
    }

    // |x| <= |y|：max = |y|，需要 |y| 为偶数
    for (int y = D; y <= U; y++) {
        if (y % 2 == 0) {
            int lo = max(L, -abs(y));
            int hi = min(R, abs(y));
            ans += max(0, hi - lo + 1);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O((R-L)+(U-D))$ ，坐标范围 $\pm 10^6$ ，完全可行
空间复杂度： $O(1)$

E - A += v

题目链接：https://atcoder.jp/contests/abc449/tasks/abc449_e

题目大意

给定整数 $N,M$ 与长度 $N$ 的序列 $A=(A_1,\dots,A_N)$ （ $1\le A_i\le M$ ）。对这个序列执行 $10^{100}$ 次操作：设 $v$ 为 $1$ 到 $M$ 之间在 $A$ 中出现次数最少的整数，若并列取最小的那个，把 $v$ 追加到 $A$ 末尾。给定 $Q$ 个询问 $X_i$ ，求操作 $10^{100}$ 次后 $A_{X_i}$ 的值。

思路

操作次数 $10^{100}$ 巨大，不可能直接模拟，需要"把同频追加的过程打包"。以下记 $c[v]$ 为值 $v$ 当前出现次数。

关键观察：按频率排序后的"分阶段循环"结构。

把 $1,\dots,M$ 按 $(c[v],v)$ 升序排序，得到序列 $P_1,P_2,\dots,P_M$ ，并令 $V_i=c[P_i]$ ，则 $V_1\le V_2\le\cdots\le V_M$ 。再定义 $V_{M+1}=+\infty$ 。

整个过程可以等价描述为：对 $k=1,2,\dots,M$ ，依次执行 $(V_{k+1}-V_k)$ 轮"把 $P_1,\dots,P_k$ 按数值升序依次各追加一次"。

为什么这样是对的：在第 $k$ 阶段开始时， $P_1,\dots,P_k$ 的次数都等于 $V_k$ ，且是全局最小；其余值的次数都大于 $V_k$ 。于是每次追加都在这些最小值中选，平局按数值取最小——恰好就是"升序轮转"。每轮把 $P_1,\dots,P_k$ 各加一次，它们的次数同步 +1；重复 $V_{k+1}-V_k$ 轮后它们都到达 $V_{k+1}$ ，阶段结束，进入 $k+1$ 阶段。（当 $V_k=V_{k+1}$ 时该阶段是空转。）

回答询问。记 $r_0=N$ ，第 $k$ 阶段结束后序列长度为

r_k=N+\sum_{i=1}^{k} i\,(V_{i+1}-V_i)\qquad (1\le k<M)

这是因为第 $i$ 阶段每轮追加 $i$ 个元素。 $r_k$ 关于 $k$ 单调不减。注意到 $r_{M-1}\le N+(M-1)N\le 2.5\times 10^{11}<10^{18}$ ，所以设 $r_M=+\infty$ 即可覆盖所有 $X\le 10^{18}$ 。

对询问 $X$ ：

若 $X\le N$ ，答案为初始序列的 $A_X$ ；
否则二分出最小的 $k$ 使得 $r_k\ge X$ （即 $X$ 落在第 $k$ 阶段），令

\text{off}=(X-r_{k-1}-1)\bmod k

则 $X$ 是该阶段第 $\text{off}+1$ 个追加元素。由于第 $k$ 阶段每轮都是" $P_1,\dots,P_k$ 升序"的循环，答案就是 $P_1,\dots,P_k$ 中第 $\text{off}+1$ 小的值。

离线回答"前 $k$ 个中的第 $t$ 小"：把询问按 $k$ 分组并排序，用 BIT 维护值域（值 $1..M$ 每个位置放 0/1）。当 $k$ 从小到大增加时，把 $P_k$ 加入 BIT；此时 $P_1,\dots,P_k$ 都已在 BIT 中，用 lower_bound 求出前缀和 $\ge \text{off}+1$ 的最小位置，即为第 $\text{off}+1$ 小的值。总复杂度 $O((N+Q+M)\log M)$ 。

验证：以样例 1 为例， $A=(1,1,2)$ ， $c=(2,1,0)$ ，排序得 $P=(3,2,1)$ ， $V=(0,1,2)$ 。 $r_0=3$ ， $r_1=3+1\times1=4$ ， $r_2=4+2\times1=6$ 。前三个阶段追加的分别是 $3$ 、 $2,3$ 、然后 $(1,2,3)$ 循环，得到序列 $1,1,2,3,2,3,1,2,\dots$ ，与样例输出完全一致。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n) : n(n), bit(n + 1, 0) {}
    void add(int i, int x) {          // 1-indexed
        for (; i <= n; i += i & -i) bit[i] += x;
    }
    // 返回前缀和 >= w 的最小下标（1-indexed）
    int lower_bound(int w) {
        int x = 0, k = 1;
        while (k << 1 <= n) k <<= 1;  // 不大于 n 的最大 2 的幂
        for (; k; k >>= 1) {
            if (x + k <= n && bit[x + k] < w) {
                w -= bit[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n), c(m + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        c[a[i]]++;
    }

    // 按 (当前次数, 值) 升序排序
    vector<pair<int, int>> p;          // (V_i, P_i)
    for (int v = 1; v <= m; v++) p.push_back({c[v], v});
    sort(p.begin(), p.end());

    vector<ll> V(m + 1), r(m + 1);
    for (int i = 0; i < m; i++) V[i + 1] = p[i].first;
    r[0] = n;
    for (int k = 1; k < m; k++)
        r[k] = r[k - 1] + 1LL * k * (V[k + 1] - V[k]);
    r[m] = (ll)4e18;                   // 视为 +inf

    int q;
    cin >> q;
    vector<vector<pair<ll, int>>> byPhase(m + 1);
    vector<ll> ans(q);
    for (int i = 0; i < q; i++) {
        ll x;
        cin >> x;
        if (x <= n) { ans[i] = a[x - 1]; continue; }
        int ok = m, ng = 0;            // 最小 ok 使得 r[ok] >= x
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (r[mid] >= x) ok = mid;
            else ng = mid;
        }
        ll off = (x - r[ng] - 1) % ok; // 阶段内第 off+1 个
        byPhase[ok].push_back({off, i});
    }

    BIT bit(m);
    for (int k = 1; k <= m; k++) {
        bit.add(p[k - 1].second, 1);   // 值 P_k 进入 BIT
        for (auto [off, idx] : byPhase[k])
            ans[idx] = bit.lower_bound((int)off + 1);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
    return 0;
}

官方题解还提供了 Python 实现（基于相同的离线 BIT 思路），供参考：

import sys
input = sys.stdin.readline

# 返回前缀和 >= w 的最小下标（1-indexed）
def lower_bound(bit, w):
    n = len(bit) - 1
    x = 0
    k = 1 << (n.bit_length() - 1)
    while k:
        if x + k <= n and bit[x + k] < w:
            w -= bit[x + k]
            x += k
        k >>= 1
    return x + 1

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    c = [0] * (m + 1)
    for v in a:
        c[v] += 1
    p = sorted((c[v], v) for v in range(1, m + 1))
    V = [0] * (m + 1)
    for i in range(1, m + 1):
        V[i] = p[i - 1][0]
    r = [0] * (m + 1)
    r[0] = n
    for k in range(1, m):
        r[k] = r[k - 1] + k * (V[k + 1] - V[k])
    r[m] = 10**18 + 1

    q = int(input())
    ans = [-1] * q
    by = [[] for _ in range(m + 1)]
    for i in range(q):
        x = int(input())
        if x <= n:
            ans[i] = a[x - 1]
            continue
        ok, ng = m, 0
        while ok - ng > 1:
            mid = (ok + ng) // 2
            if r[mid] >= x:
                ok = mid
            else:
                ng = mid
        off = (x - r[ng] - 1) % ok
        by[ok].append((off, i))

    bit = [0] * (m + 1)
    for k in range(1, m + 1):
        v = p[k - 1][1]
        i = v
        while i <= m:
            bit[i] += 1
            i += i & -i
        for off, idx in by[k]:
            ans[idx] = lower_bound(bit, off + 1)
    print('\n'.join(map(str, ans)))

main()

复杂度分析

时间复杂度： $O(N\log N+Q\log M+M\log M)$ （排序 + 二分 + 离线 BIT）
空间复杂度： $O(N+Q+M)$

F - Grid Clipping

题目链接：https://atcoder.jp/contests/abc449/tasks/abc449_f

题目大意

$H\times W$ 网格中有 $N$ 个黑色格子 $(R_k,C_k)$ ，其余为白色。求所有全由白色格子组成的 $h\times w$ 矩形区域的个数，即满足 $1\le r_0\le H-h+1$ 、 $1\le c_0\le W-w+1$ 、且该 $h\times w$ 区域不含任何黑格的 $(r_0,c_0)$ 的个数。

思路

补集转化。合法子矩形总数是 $T=(H-h+1)(W-w+1)$ 。数出"至少含一个黑格"的坏矩形个数 $X$ ，则答案为 $T-X$ 。

一个黑格 $(R_k,C_k)$ 使得哪些左上角 $(r_0,c_0)$ 对应的 $h\times w$ 矩形变坏？矩形需要盖住 $(R_k,C_k)$ ，即

R_k-h+1\le r_0\le R_k,\qquad C_k-w+1\le c_0\le C_k

所以每个黑格对应一个轴平行矩形（注意坐标范围可能越界，扫过时自然截断）。 $X$ 就是这些矩形的并集面积。由于 $H,W$ 高达 $10^9$ 而 $N\le 2\times10^5$ ，需要对稀疏的矩形做扫描线。

扫描线 + multiset 维护区间并。沿 $r_0$ 方向扫描：

黑格 $k$ 的矩形在 $r_0=R_k-h+1$ 处"进入"（带来 $c_0$ 方向区间 $[C_k-w+1,\ C_k]$ ），在 $r_0=R_k+1$ 处"离开"；
把事件按 $r_0$ 坐标排序，相邻两个事件行之间的所有行，其被覆盖的 $c_0$ 集合都相同，可以整段计算。

维护"当前行被覆盖的 $c_0$ 长度"需要高效支持插入/删除区间并。做法是：用一个有序集合（C++ multiset）存放所有活动区间的左端点 $c$ ，并插入两个哨兵 $-w$ 与 $W-w+1$ 。对集合中相邻的两个元素 $l<r$ ，它们之间未被覆盖的 $c_0$ 个数为

\operatorname{gap}(l,r)=\max(0,\ r-l-w)

理由：左端点为 $l$ 的区间覆盖 $[l,l+w-1]$ ，因此在 $[l,r)$ 段内覆盖了前 $\min(w,r-l)$ 个位置，剩下 $r-l-\min(w,r-l)=\max(0,r-l-w)$ 个未被覆盖。对集合中所有相邻对求和，即得当前行的未覆盖数 good，被覆盖数为 $Y-\text{good}$ （ $Y=W-w+1$ 为合法 $c_0$ 总数）。

插入或删除左端点 $x$ 时，只影响它与前驱 $l$ 、后继 $r$ 构成的局部，令

\text{good}\leftarrow \text{good}\ \pm\ \big(\operatorname{gap}(l,x)+\operatorname{gap}(x,r)-\operatorname{gap}(l,r)\big)

即可 $O(\log N)$ 更新。

累加答案：设事件按行排序为 $x_1<x_2<\dots$ 。扫描时维护 pre 为已处理到的行，遇到事件行 $x$ 时，先累加行区间 $[\text{pre},\min(x,H-h+1))$ 的坏矩形数 $(\min(x,X)-\text{pre})\cdot(Y-\text{good})$ ，再处理该行的事件（先加后删按事件类型）。最后处理完所有事件后，把剩余的行也累加进去。

易错点：事件行可能为负（ $R_k-h+1<0$ ）或超过 $X-1$ ，处理时用 $\min(x,X)$ 截断；在负行上只更新集合不累加答案即可。复杂度 $O(N\log N)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll H, W, h, w, n;
    cin >> H >> W >> h >> w >> n;
    vector<tuple<ll, ll, bool>> g;      // (事件行, 区间左端点, 是否加入)
    g.reserve(2 * n);
    for (int i = 0; i < n; i++) {
        ll r, c;
        cin >> r >> c;
        r--; c--;                       // 转 0-indexed
        g.push_back({r - h + 1, c - w + 1, true});   // 在行 r-h+1 进入
        g.push_back({r + 1, c - w + 1, false});      // 在行 r+1 离开
    }
    sort(g.begin(), g.end());

    multiset<ll> s;
    s.insert(-w);
    s.insert(W - w + 1);                // 两个哨兵

    ll ans = (H - h + 1) * (W - w + 1); // 总矩形数
    auto gap = [&](ll l, ll r) { return max(0LL, r - l - w); };
    const ll X = H - h + 1;             // 合法 r0 个数
    const ll Y = W - w + 1;             // 合法 c0 个数
    ll good = Y;                        // 当前行未覆盖的 c0 数

    auto add = [&](ll x) {
        auto it = s.lower_bound(x);
        ll r = *it, l = *prev(it);
        good += gap(l, x) + gap(x, r) - gap(l, r);
        s.insert(x);
    };
    auto del = [&](ll x) {
        auto it = s.find(x);
        ll r = *next(it), l = *prev(it);
        good -= gap(l, x) + gap(x, r) - gap(l, r);
        s.erase(it);
    };

    ll pre = 0;
    int i = 0;
    while (i < 2 * n) {
        ll x = get<0>(g[i]);
        ll nx = min(x, X);
        if (pre < nx) {                 // 先累加 [pre, nx) 这些行的坏矩形
            ans -= (nx - pre) * (Y - good);
            pre = nx;
        }
        while (i < 2 * n && get<0>(g[i]) == x) {   // 再统一处理本行的所有事件
            auto [r, c, in] = g[i];
            if (in) add(c);
            else del(c);
            i++;
        }
    }
    if (pre < X) ans -= (X - pre) * (Y - good);
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N\log N)$ （排序 + 每个事件一次 multiset 操作）
空间复杂度： $O(N)$

G - Many Repunit Sum 2

题目链接：https://atcoder.jp/contests/abc449/tasks/abc449_g

题目大意

给定正整数 $N,M$ 。对正整数 $d$ ， $d$ 位 repunit（全 1 数）定义为 $\displaystyle\sum_{i=0}^{d-1}10^i$ 。求" $N$ 个位数在 $1$ 到 $M$ 之间的 repunit 之和"所能表示的不同整数的个数，对 $998244353$ 取模。

思路

本题的核心是两步：先把问题变换为" $N$ 个 $10$ 的幂之和"，再用生成函数 + 差分方程计数。

第一步：问题变换。 设 $d$ 位 repunit 为 $R_d=\dfrac{10^d-1}{9}$ 。若 $n=\sum_{i=1}^{N}R_{d_i}$ ，则

9n=\sum_{i=1}^{N}(10^{d_i}-1)=\sum_{i=1}^{N}10^{d_i}-N\ \Longrightarrow\ \frac{9n+N}{10}=\sum_{i=1}^{N}10^{d_i-1}

反之同理（两边同乘 $9$ 并加 $N$ 即可反推）。因此 $n$ 可表示 ⟺ $m=\dfrac{9n+N}{10}$ 可表示为 $N$ 个"位数不超过 $M$ 的 $10$ 的幂"（即 $10^0,10^1,\dots,10^{M-1}$ ）之和，且 $n\leftrightarrow m$ 是表示值之间的双射。问题转化为：计数可表示为 $N$ 个 $10$ 的幂（指数 $0\sim M-1$ ）之和的不同 $m$ 的个数。

第二步：判断 $m$ 是否可表示。 设 $f(m)$ 为用 $10$ 的幂表示 $m$ 所需的最少项数（ $m\ge 0$ ，指数 $\le M-1$ ）。 $m$ 可表示为 $N$ 项之和当且仅当：

$m\ge N$ （每项至少为 $1$ ）；
$f(m)\le N$ （由 $f(m)$ 的定义）；
$f(m)\equiv N\pmod 9$ （因为 $10^e\equiv 1\pmod 9$ ，任何 $N$ 项之和 $\equiv N\pmod 9$ ；而 $m\equiv f(m)\pmod 9$ ，故 $N\equiv m\equiv f(m)$ ）。

充分性：取 $f(m)$ 项的最优表示。把一项 $10^d$ （ $d>0$ ）拆成十个 $10^{d-1}$ ，项数恰好增加 $9$ 。如此重复 $\dfrac{N-f(m)}{9}$ 次即可得到 $N$ 项表示； $m\ge N$ 保证过程中不会出现"所有指数都为 $0$ 却还需要再拆"的情况（若全为 $0$ ，则 $m=$ 项数 $<N$ ，矛盾）。

$f(m)$ 的计算（贪心）：从高位到低位贪心。设 $Q=\left\lfloor m/10^{M-1}\right\rfloor$ ， $R=m\bmod 10^{M-1}$ ，则

f(m)=Q+\operatorname{digitSum}(R)

因为 $Q$ 个 $10^{M-1}$ 无法用少于 $Q$ 项凑出；而 $R<10^{M-1}$ 时，用 $10$ 的幂表示 $R$ 的最少项数就是 $R$ 的数位和（任何表示的数位和 $\le$ 项数，且直接用各位数字即可达到）。

第三步：计数。 把 $m$ 写成"数字分解"： $A_{M-1}=Q\ge 0$ ，而 $A_0,\dots,A_{M-2}\in[0,9]$ 是 $R$ 的十进制数字。则 $f(m)=\sum_i A_i$ 。先忽略 $m\ge N$ 条件，对所有 $m\ge 0$ 计数满足

\sum_i A_i\le N,\qquad \sum_i A_i\equiv N\pmod 9

的元组个数；最后再减去误计为可表示、但 $m<N$ 的元组。当 $m<N$ 时 $f(m)\le m<N$ ，条件 2 自动满足，且 $f(m)\equiv m\pmod 9$ ，故 $m<N$ 且被计数的 $m$ 恰是满足 $m\equiv N\pmod 9$ 的 $m\in[0,N-1]$ ，个数为 $\lfloor N/9\rfloor$ 。于是

\text{答案}=\sum_{\substack{0\le S\le N\\ S\equiv N\pmod 9}}c_S-\left\lfloor\frac{N}{9}\right\rfloor

其中 $c_S$ 是满足 $\sum A_i=S$ 的元组个数。前 $M-1$ 个数字各 $\in[0,9]$ ，最后一个无上界，因此 $c_S$ 是 $(1+x+\cdots+x^9)^{M-1}$ 系数 $b_s$ 的前缀和：

c_S=\sum_{s=0}^{S}[x^s](1+x+\cdots+x^9)^{M-1}

第四步： $O(N)$ 递推系数。 令 $e=M-1$ ， $P(x)=1+x+\cdots+x^9$ ， $F(x)=P(x)^e=\sum f_n x^n$ （这里的 $f_n$ 即上面的 $b_n$ ）。由 $P F'=e P' F$ 两边比较 $x^n$ 的系数，可整理出（推导要点： $P'=\sum_{i=1}^9 i x^{i-1}$ ，将 $i$ 重标号为 $k=n-i+1$ ）：

f_{n+1}=\frac{1}{n+1}\sum_{k=\max(0,\,n-8)}^{n}\big(e\,(n-k+1)-k\big)\,f_k,\qquad f_0=1

因为 $P$ 的次数只有 $9$ ，求和范围至多 $9$ 项，可在 $O(9N)$ 内算出 $f_0,\dots,f_N$ 。由于 $N\le 10^5$ ，模 $998244353$ 下做逆元、加减乘即可（ $998244353$ 为素数， $1..N+1$ 均与其互素，可直接用费马小定理求逆）。

为什么正确：整个推导链条是等价的——repunit 和 ⟺ $10$ 的幂之和 ⟺ 满足三条条件的 $m$ ⟺ 满足同余条件的"数字分解"元组。每一步都是双射或无损的计数（最后一步减去 $\lfloor N/9\rfloor$ 恰好剔除 $m<N$ 的部分），因此结果即原问题的不同整数个数。

补充：官方题解还指出可以用 FPS 的 log/exp 或 NTT 快速幂在 $O(N\log N)$ 内求解，也可直接利用闭式

[x^N]\frac{(1-x^{10})^{M-1}}{(1-x)^M(1-x^9)}

同样 $O(N)$ 可做，但差分方程法实现最简洁。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N, M;
    cin >> N >> M;
    int n = (int)N;
    ll e = (M - 1) % MOD;

    vector<ll> f(n + 1), inv(n + 2);
    for (int i = 1; i <= n + 1; i++) inv[i] = modpow(i, MOD - 2);

    // f = (1 + x + ... + x^9)^(M-1) 的前 n+1 个系数，差分方程递推
    f[0] = 1;
    for (int i = 0; i < n; i++) {
        ll sum = 0;
        for (int k = max(0, i - 8); k <= i; k++) {
            ll coef = (e * (i - k + 1) - k) % MOD;
            if (coef < 0) coef += MOD;
            sum = (sum + coef * f[k]) % MOD;
        }
        f[i + 1] = sum * inv[i + 1] % MOD;
    }

    // c_S = sum_{s<=S} f_s；累加所有 S ≡ N (mod 9), S <= N 的 c_S
    ll pre = 0, ans = 0;
    for (int S = 0; S <= n; S++) {
        pre = (pre + f[S]) % MOD;
        if (S % 9 == n % 9) ans = (ans + pre) % MOD;
    }
    ans = (ans - n / 9) % MOD;   // 剔除 m < N 的部分
    if (ans < 0) ans += MOD;
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(9N)$
空间复杂度： $O(N)$