AtCoder Beginner Contest 466 题解

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

比赛概览

本场整体难度中等偏高，A、B 是两道热身题；C 是一道交互题，需要利用点的顺序性做双指针滑动窗口；D 考察逆向思维（或带计数的正向模拟）；E 需要先把"区间翻转"问题规约成"段划分"，再做简单的 DP；F 用"区间多重集 + 优先队列"的巧妙视角统计取模结果；G 则是全场最难、最有区分度的一题，综合了带权并查集与二进制按位 DP。建议重点掌握 C 的交互式滑动窗口思想、E 的区间合并观察，以及 F 的"对区间整体取模"技巧。

---

A - Compromise

题目链接：https://atcoder.jp/contests/abc466/tasks/abc466_a

题目大意

有 $N$ 个选项，若选择第 $i$ 个选项，你会获得快乐值 $X_i$。若无论选择哪个选项，你的快乐值都是负数，输出 Yes，否则输出 No。

思路

题目其实是在问：是否存在一个选择能让自己开心（快乐值 $\ge 0$）。

• 如果存在某个 $i$ 使得 $X_i \ge 0$，那么选它即可，答案应为 No；
• 只有当所有 $X_i$ 都是负数（严格 $< 0$）时，无论怎么选都会不开心，答案才是 Yes。

即

$$\text{答案为 } \texttt{No} \iff \max_{1\le i\le N} X_i \ge 0 .$$

逐项读入、检查即可。注意 $X_i = 0$ 不属于负数（样例 3 中的 $0$ 就说明了这一点）。

参考代码

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

int main() {
    int n;
    cin >> n;
    bool allNegative = true;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x >= 0) allNegative = false;
    }
    cout << (allNegative ? "Yes" : "No") << '\n';
    return 0;
}

官方题解还给出了一行 Python 写法：

N = int(input())
X = list(map(int, input().split()))
print("No" if max(X) >= 0 else "Yes")

复杂度分析

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

---

B - Representative Balls

题目链接：https://atcoder.jp/contests/abc466/tasks/abc466_b

题目大意

有 $N$ 个球，第 $i$ 个球的颜色为 $C_i$、大小为 $S_i$（颜色编号为 $1\sim M$）。对每种颜色 $k=1,2,\ldots,M$，输出该颜色球的最大大小；若该颜色不存在任何球，输出 -1。

思路

经典"按颜色维护最大值"问题。开一个数组 mx[1..M] 初始化为 $-1$（恰好表示"该颜色不存在"），然后依次扫描每个球，做

$$mx[C_i] = \max(mx[C_i],\; S_i).$$

把初值设成 $-1$ 的好处是不需要再单独处理"颜色不存在"的分支——如果没有该颜色的球，mx[k] 就一直是 $-1$。

最后按 $k=1,2,\ldots,M$ 的顺序输出即可。

参考代码

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> mx(m, -1);
    for (int i = 0; i < n; i++) {
        int c, s;
        cin >> c >> s;
        c--;
        mx[c] = max(mx[c], s);
    }
    for (int i = 0; i < m; i++) {
        if (i) cout << ' ';
        cout << mx[i];
    }
    cout << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N + M)$
• 空间复杂度：$O(M)$

---

C - Count Close Pairs

题目链接：https://atcoder.jp/contests/abc466/tasks/abc466_c

题目大意

这是一道交互题。数轴上从左到右依次有 $1,2,\ldots,N$ 个点（每个点的具体坐标未知）。你可以向评测机发起至多 $2N$ 次如下询问：

• 选择 $1\le i<j\le N$，询问点 $i$ 与点 $j$ 之间的距离是否不超过 $1$，返回 Yes / No。

求满足"距离不超过 $1$"的点对 $(i,j)$（$i<j$）的总数，输出 ! X。

思路

设第 $i$ 个点的坐标为 $p_i$，由题意 $p_1 < p_2 < \cdots < p_N$，距离即 $p_j - p_i$。

关键观察 1（连续性）：对固定的 $i$，若 $p_j-p_i\le 1$，则对任意 $i\le k\le j$ 都有 $p_k-p_i\le p_j-p_i\le 1$。因此满足 $p_j-p_i\le 1$ 的 $j$ 构成一段连续区间 $[i,\ M_i]$，其中 $M_i$ 是与 $i$ 的距离不超过 $1$ 的最远点。

关键观察 2（单调性）：若 $p_{M_i}-p_i\le 1$，则

$$p_{M_i}-p_{i+1} < p_{M_i}-p_i \le 1,$$

所以 $M_{i+1}\ge M_i$，即

$$M_1 \le M_2 \le \cdots \le M_N .$$

于是答案可写成

$$\sum_{i=1}^{N} (M_i - i),$$

因为点 $i$ 与 $i+1,\ldots,M_i$ 之间（共 $M_i-i$ 个点）的距离都不超过 $1$。

滑动窗口算法：我们按 $i=1,2,\ldots,N$ 的顺序确定 $M_i$。维护两个指针 $L,R$（初值 $L=1,R=2$），并保持如下不变量：已知"$L$ 到所有 $L<j<R$ 的 $j$ 的距离都不超过 $1$"。

• 询问 ? L R：
  • 若回答 Yes（$p_R-p_L\le 1$）：由单调性 $M_L\ge R$，我们还不知道 $M_L$ 的确切值，于是 $R \leftarrow R+1$，继续扩大；
  • 若回答 No（$p_R-p_L>1$）：由连续性与不变量，$M_L = R-1$，累加答案 $R-1-L$，然后 $L \leftarrow L+1$（此时新 $L$ 到 $L+1,\ldots,R-1$ 的距离都已不超过 $1$，不变量保持）。若 $L=R$，则把 $R$ 也加一（此时 $L$ 到它自身距离为 $0\le 1$，相当于已知答案）。

当 $R>N$ 时主循环结束，此时剩余的 $L,L+1,\ldots,N$ 都有 $M_i=N$，逐个累加 $N-i$ 即可。

询问次数：每次询问都会让 $L+R$ 至少增加 $1$，而 $L+R$ 最多从 $3$ 增长到 $2N+1$，所以总询问次数至多 $2N-2$（事实上可以证明至多 $2N-3$ 次），严格小于上限 $2N$。

易错点：这是交互题，每次输出后必须换行并刷新输出缓冲（C++ 中用 endl 即可），否则可能因缓冲未刷新导致超时；输出 ! X 后要立即结束程序。

参考代码

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

int main() {
    int n;
    cin >> n;

    int l = 1, r = 2;
    long long ans = 0;
    string s;

    while (r <= n) {
        cout << "? " << l << " " << r << endl;   // endl 自带 flush
        cin >> s;
        if (s == "Yes") {
            r++;                                  // M_l >= r，还不知道确切的 M_l
        } else {
            ans += (r - l - 1);                   // 确定 M_l = r-1
            l++;
            if (l == r) r++;
        }
    }
    while (l < n) {                               // 剩余的 l: M_l = n
        ans += (r - l - 1);
        l++;
    }

    cout << "! " << ans << endl;
    return 0;
}

复杂度分析

• 询问次数：至多 $2N-2$ 次（满足 $2N$ 的限制）
• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

---

D - Placing Rooks

题目链接：https://atcoder.jp/contests/abc466/tasks/abc466_d

题目大意

有一个 $N\times N$ 的棋盘，初始为空。Takahashi 按顺序进行 $M$ 次操作，第 $i$ 次操作：

1. 移除第 $R_i$ 行上所有棋子；
2. 移除第 $C_i$ 列上所有棋子；
3. 在 $(R_i,C_i)$ 格子上放一枚棋子。

求全部 $M$ 次操作结束后棋盘上的棋子总数。

思路

官方题解给出两种解法，这里都介绍一下。

解法 1：倒着思考（推荐）

关键观察：第 $i$ 次操作放置的棋子能活到最后，当且仅当第 $i+1$ 到第 $M$ 次操作中，没有任何一次操作在第 $R_i$ 行或第 $C_i$ 列上放置棋子。

理由很直接：后续每次操作都会"清除整行 + 清除整列"。若第 $j$ 次操作（$j>i$）满足 $R_j=R_i$ 或 $C_j=C_i$，那么第 $j$ 次操作就会把 $(R_i,C_i)$ 上的棋子清掉（之后放上去的新棋子当然不是原来的那枚了）。反之，如果所有后续操作的 $R_j,C_j$ 都不等于 $R_i,C_i$，则 $(R_i,C_i)$ 永远不会被清除。

因此，倒序扫描操作（从第 $M$ 次到第 $1$ 次），维护两个布尔数组：

• rused[x]：第 $R$ 行是否已被"当前已经扫描过的操作"放置过棋子；
• cused[y]：第 $C$ 列是否已被放置过棋子。

对第 $i$ 次操作，若 rused[R_i] 与 cused[C_i] 都为假，则这枚棋子存活，答案加一；然后无条件地标记 rused[R_i] = cused[C_i] = true。

正确性：当前操作放置的棋子存活与否，只取决于更靠后的操作（即已经扫描过的那些），所以倒序扫描时在"决策时刻"就能得到与正序模拟完全一致的结果。

解法 2：正向模拟

先做一个观察：任意时刻，每一行和每一列至多有一枚棋子（因为每次放棋子前都会清空它所在的行和列）。

于是可以维护两个数组：

• rplace[x]：第 $x$ 行的棋子是由哪次操作放置的（0 表示空）；
• cplace[y]：第 $y$ 列的棋子是由哪次操作放置的。

对第 $i$ 次操作 $(R_i,C_i)$：

1. 若 rplace[R_i] > 0，说明第 $R_i$ 行上有一枚棋子，把它移除（同时清空对应行、列记录，答案减一）；
2. 若 cplace[C_i] > 0，同理移除第 $C_i$ 列上的棋子（若它与第 1 步是同一枚棋子，则此时已被清掉，不会重复减）；
3. 放置新棋子：rplace[R_i] = cplace[C_i] = i，答案加一。

每次操作至多移除两枚棋子，均摊 $O(1)$。

参考代码

解法 1（倒序）：

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

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

    vector<char> rused(n + 1, 0), cused(n + 1, 0);
    int ans = 0;
    for (int i = m - 1; i >= 0; i--) {
        if (!rused[r[i]] && !cused[c[i]]) ans++;   // 该棋子存活
        rused[r[i]] = 1;
        cused[c[i]] = 1;
    }
    cout << ans << '\n';
    return 0;
}

解法 2（正向模拟）：

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> r(m + 1), c(m + 1);
    vector<int> rplace(n + 1, 0), cplace(n + 1, 0);
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        cin >> r[i] >> c[i];
        if (rplace[r[i]] > 0) {
            int idx = rplace[r[i]];
            rplace[r[idx]] = 0;
            cplace[c[idx]] = 0;
            ans--;
        }
        if (cplace[c[i]] > 0) {
            int idx = cplace[c[i]];
            rplace[r[idx]] = 0;
            cplace[c[idx]] = 0;
            ans--;
        }
        rplace[r[i]] = i;
        cplace[c[i]] = i;
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：解法 1 为 $O(M)$；解法 2 为 $O(M)$（读入本身是 $O(M)$）
• 空间复杂度：解法 1 为 $O(N+M)$；解法 2 为 $O(N+M)$

---

E - Range Flip

题目链接：https://atcoder.jp/contests/abc466/tasks/abc466_e

题目大意

有 $N$ 张卡，第 $i$ 张正面写 $A_i$、背面写 $B_i$，初始全部正面朝上。你可以进行至多 $K$ 次操作：选择区间 $[l,r]$，把区间内每张卡翻面。求操作结束后朝上一面的数字之和的最大可能值。

思路

设区间用半开区间 $[l,r)$ 表示。

关键观察 1：可以把操作区间变成互不相交的

翻转的本质是对每个位置异或 $1$，所以最终哪些卡是背面朝上，取决于每个位置被覆盖的次数是奇数还是偶数，即这些区间的对称差。

假设存在一个最优解，其"被操作区间的总长度"在所有最优解中最小。若其中有两个区间重叠，设它们为 $[l_1,r_1)$ 与 $[l_2,r_2)$，则用下面两个区间替换它们：

$$[\min(l_1,l_2),\ \max(l_1,l_2)) \quad \text{与} \quad [\min(r_1,r_2),\ \max(r_1,r_2)),$$

每张卡最终的朝向完全不变（对称差不变），但两个新区间的总长度严格变小（例如当 $l_1\le l_2<r_1\le r_2$ 时，原总长 $(r_1-l_1)+(r_2-l_2)$ 减去新总长 $(l_2-l_1)+(r_2-r_1)$ 等于 $2(r_1-l_2)>0$）。这与最小性矛盾，所以可以假定最优解中的操作区间互不相交（替换后若出现空区间，直接丢弃该次操作即可）。

于是问题等价于：选择至多 $K$ 个互不相交的区间翻转。

关键观察 2：转成"段划分"

从左到右扫过卡片，每当进入一个翻转区间时，朝向就翻转一次。因此整副牌被划分成若干交替的段：奇数段正面朝上（取 $A_i$），偶数段背面朝上（取 $B_i$）。因为至多 $K$ 个翻转区间，段数至多 $2K+1$。

DP

设 $dp_{i,j}$ 表示考虑前 $i$ 张卡、且第 $i$ 张卡属于第 $j$ 段（$1\le j\le 2K+1$）时，朝上一面数字之和的最大值。第 $j$ 段为奇数段时取 $A_i$，偶数段时取 $B_i$，记

$$v(i,j) = \begin{cases} A_i, & j \text{ 为奇数},\\ B_i, & j \text{ 为偶数}. \end{cases}$$

转移时，第 $i$ 张卡要么延续第 $i-1$ 张卡的段（$j$ 不变），要么新起一段（第 $i-1$ 张在第 $j-1$ 段）：

$$dp_{i,j} = v(i,j) + \max(dp_{i-1,j},\ dp_{i-1,j-1}).$$

边界：$dp_{0,j}=0$（$1\le j\le 2K+1$），这允许开头若干段为空，即允许第一张卡就直接属于一个翻转区间。

为什么只需要从 $j-1$ 转移，而不是所有 $j'\le j$？ 因为中间的空段是无意义的：若两段同朝向之间夹一个空段，它们本质上仍是同一段（相邻的两个翻转区间会合并成一个），所以最优解里中间的段不会为空，只有末尾（或开头）的段可以空。

答案取 $\max_{1\le j\le 2K+1} dp_{N,j}$。

正确性：任意一个"至多 $K$ 个不相交区间翻转"的方案都唯一对应一个段划分（以及空段），DP 枚举了所有段划分；反之每个 DP 产生的段划分都对应一个合法的翻转方案（偶数段即翻转区间，数量不超过 $K$）。因此两者最大值一致。

参考代码

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];

    int C = 2 * k + 1;
    const long long NEG = -(1LL << 62);
    vector<long long> dp(C, 0);   // dp[j]: 第 i 张卡属于第 j 段（0-based）
    for (int i = 0; i < n; i++) {
        vector<long long> ndp(C, NEG);
        for (int j = 0; j < C; j++) {
            long long best = dp[j];
            if (j > 0) best = max(best, dp[j - 1]);
            if (best == NEG) continue;
            // 第 j+1 段：j 为偶数 → 奇数段 → 正面 A；j 为奇数 → 偶数段 → 背面 B
            long long val = (j % 2 == 0) ? a[i] : b[i];
            ndp[j] = best + val;
        }
        dp.swap(ndp);
    }
    long long ans = 0;
    for (int j = 0; j < C; j++) ans = max(ans, dp[j]);
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(NK)$（段数 $2K+1$，$K\le 10$）
• 空间复杂度：$O(K)$

---

F - Many Mod Calculation

题目链接：https://atcoder.jp/contests/abc466/tasks/abc466_f

题目大意

给定 $N,X$ 和正整数序列 $A_1,\ldots,A_N$，定义

$$f(x)=(\cdots((x\bmod A_1)\bmod A_2)\cdots)\bmod A_N .$$

对每个测试用例，求 $x\in\{1,2,\ldots,X\}$ 中满足 $f(x)=0$ 的 $x$ 的个数。

思路

把"一个个数"改成"区间多重集"

直接枚举 $x$ 显然不行（$X\le 10^{18}$）。换一个视角：维护"当前所有可能取值"组成的多重集，初始为 $\{1,2,\ldots,X\}$。每应用一次 $\bmod\ A_i$，就相当于把多重集中每个值 $v$ 替换成 $v\bmod A_i$。

为了利用区间结构，我们改考虑 $\{0,1,\ldots,X\}$ 这 $X+1$ 个数（即区间 $[0,X+1)$ 内的所有整数），最后再减去 $x=0$ 的贡献——因为 $0\bmod m=0$，$x=0$ 恒满足 $f(x)=0$，但它不在 $[1,X]$ 范围内。

关键表示：把多重集表示为若干"$c$ 份 $[0,x)$"的形式，其中 $[0,x)$ 表示整数 $0,1,\ldots,x-1$，$c$ 表示该区间出现的份数（即该区间内每个值都被 $c$ 个互不相同的原始取值映射到）。

现在考虑对"$c$ 份 $[0,x)$"整体应用 $\bmod\ v$（设 $v=A_i$）：

• 若 $x\le v$：区间内每个数都小于 $v$，取模后不变，仍然是 $c$ 份 $[0,x)$；
• 若 $x>v$：把 $[0,x)$ 按模 $v$ 分成 $\lfloor x/v\rfloor$ 段 $[0,v)$ 和最后一段 $[0,\ x\bmod v)$，取模后

  $$c\text{ 份 }[0,x)\ \xrightarrow{\ \bmod\ v\ }\ c\cdot\lfloor x/v\rfloor\text{ 份 }[0,v)\ +\ c\text{ 份 }[0,\ x\bmod v).$$

  若 $x\bmod v=0$，第二项为空区间，直接丢弃。

用优先队列模拟

用最大堆（按区间右端 $x$ 排序）维护所有区间。对每个 $v=A_i$，反复取出堆顶、把右端 $x>v$ 的区间按上式分裂；相同右端的区间合并计数（保证堆内右端互不相同）。

复杂度：每次分裂产生的残余区间 $[0,x\bmod v)$ 满足 $x\bmod v \le x/2$（因为当 $v\le x$ 时，$x\bmod v< v$，且 $x\bmod v\le x-v$，两者均不超过 $x/2$）。所以每个区间经历 $O(\log X)$ 次"缩小一半"，产生的区间总数是 $O(N\log X)$，再乘上堆操作 $O(\log N)$，总复杂度 $O(N\log N\log X)$。

统计答案

处理完所有 $A_i$ 后，堆中每个区间 $[0,x)$（$x\ge 1$）恰好贡献一个取值为 $0$ 的结果（即区间内的 $0$），所以 $f(y)=0$ 的 $y\in[0,X]$ 的个数等于各区间份数之和。答案还要减去 $x=0$ 这一项，故

$$\text{答案} = -1 + \sum_{\text{区间 }[0,x)} c .$$

注意 $X+1\le 10^{18}+1$，全部用 64 位整数计算。

参考代码

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

using ll = long long;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        ll x;
        cin >> n >> x;
        vector<ll> a(n);
        for (ll &v : a) cin >> v;

        // 最大堆，按区间右端点 x 排序，pair.second 为该区间份数
        priority_queue<pair<ll, ll>> pq;
        pq.push({x + 1, 1});   // 1 份 [0, X+1)，即 0..X

        for (ll v : a) {
            while (!pq.empty() && pq.top().first > v) {
                auto [val, cnt] = pq.top();
                pq.pop();
                while (!pq.empty() && pq.top().first == val) {  // 合并同右端
                    cnt += pq.top().second;
                    pq.pop();
                }
                pq.push({v, val / v * cnt});              // (val/v) 份 [0, v)
                if (val % v != 0) pq.push({val % v, cnt}); // 1 份 [0, val%v)
            }
        }

        ll ans = -1;  // 减去 x=0（它恒有 f(x)=0）
        while (!pq.empty()) {
            ans += pq.top().second;
            pq.pop();
        }
        cout << ans << '\n';
    }
    return 0;
}

官方题解给出的 Python 实现如下（使用最小堆存放 $-x$ 以模拟最大堆）：

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    pq = [(-(x + 1), 1)]
    for v in a:
        while pq and -pq[0][0] > v:
            val, cnt = heappop(pq)
            val = -val
            while pq and -pq[0][0] == val:
                cnt += heappop(pq)[1]
            heappush(pq, (-v, (val // v) * cnt))
            if val % v:
                heappush(pq, (-(val % v), cnt))
    ans = -1
    while pq:
        ans += heappop(pq)[1]
    print(ans)

复杂度分析

• 时间复杂度：每个测试用例 $O(N\log N\log X)$
• 空间复杂度：$O(N\log X)$

---

G - Segment Sum Constraints

题目链接：https://atcoder.jp/contests/abc466/tasks/abc466_g

题目大意

给定 $M$ 个三元组 $(L_i,R_i,S_i)$，考虑满足如下条件的 $N$ 元正整数元组 $A=(A_1,\ldots,A_N)$：

$$A_{L_i}+A_{L_i+1}+\cdots+A_{R_i}=S_i,\qquad i=1,2,\ldots,M .$$

若满足条件的元组有无穷多个，输出 Infinity；否则输出满足条件的元组个数 $\bmod\ 998244353$。

思路

这是全场最难的一题，分为"化简条件"与"二进制按位 DP 计数"两大步。$N\le 8$ 是核心约束，让按位 DP 可行。

第一步：转成非负整数 + 前缀和表示

条件给的是正整数。令

$$S_i' = S_i - (R_i-L_i+1),$$

则 $A$ 为正整数等价于 $B=A-(1,1,\ldots,1)$ 为非负整数，且约束变为 $B_{L_i}+\cdots+B_{R_i}=S_i'$。若某 $S_i'<0$，显然无解，输出 $0$。

记前缀和 $P_0=0,\ P_k=P_{k-1}+B_k$，则约束写成

$$P_{R_i}-P_{L_i-1}=S_i' .$$

第二步：带偏移的并查集（找出条件之间的线性关系）

我们希望把每条约束化成"$P_j=P_k+D$"的形式。维护数组 $k_j$ 与 $D_j$，满足恒等式 $P_j=P_{k_j}+D_j$。初始 $k_j=j,\ D_j=0$。

按输入顺序处理每条约束，设 $a=L_i-1,\ b=R_i$：

• 若 $k_a=k_b$：由已有关系可得 $P_b=P_a+(D_b-D_a)$，因此当且仅当 $D_b-D_a=S_i'$ 时约束自动满足，否则矛盾，输出 $0$。
• 若 $k_a<k_b$：由 $P_b-P_a=S_i'$ 得

  $$P_{k_b}=P_{k_a}+(D_a-D_b+S_i'),$$

  于是把所有 $k_j=k_b$ 的下标 $j$ 改为 $k_a$，并令 $D_j\mathrel{+}=D_a-D_b+S_i'$。
• 若 $k_a>k_b$：对称地，把所有 $k_j=k_a$ 的下标 $j$ 改为 $k_b$，并令 $D_j\mathrel{+}=D_b-D_a-S_i'$。

由于 $N\le 8$，每次直接 $O(N)$ 扫描更新即可。

第三步：提取化简后的独立方程

处理完全部 $M$ 条约束后，对每个 $i=0,1,\ldots,N-1$，找到最小的 $j>i$ 使得 $k_j=k_i$，则

$$B_{i+1}+B_{i+2}+\cdots+B_j = P_j-P_i = D_j-D_i$$

是一个必要且充分的独立方程（若 $D_j-D_i<0$ 则无解，输出 $0$）。这样得到至多 $N$ 个方程，且每个方程左端起点 $i$ 互不相同；可以证明它们等价于原约束系统。

同时用 used 数组标记哪些 $B$ 变量出现在方程中。若某个 $B_j$ 不出现在任何方程里，则它不受任何约束：

• 若其余变量存在至少一个可行解，则该变量可取任意非负整数，答案为 Infinity；
• 若其余变量无解，答案为 $0$。

第四步：二进制按位 DP 计数

所有 $S_i'\le 10^9<2^{30}$，且出现在方程中的每个 $B_j$ 都不超过它所在方程的和 $S_i'\le 10^9$，所以 30 位二进制足够。

设 $dp_{i}[C]$ 表示：考虑 $B_1,\ldots,B_N$ 的低 $i$ 位，满足所有方程低 $i$ 位相等、且第 $j$ 个方程产生的"进位"为 $C_j$ 时的方案数。这里

$$C_j=\frac{(B_{L'_j}+\cdots+B_{R'_j})\bmod 2^i - (S_j'\bmod 2^i)}{2^i},$$

由于总和不超过 $10^9$，进位 $C_j\in[0,\ R'_j-L'_j]\subseteq[0,7]$。

初始 $dp_0[(0,\ldots,0)]=1$。对第 $i$ 位（$0\le i<30$），枚举 $2^N$ 种数字组合 $X=(X_1,\ldots,X_N)\in\{0,1\}^N$（即每个 $B_j$ 的第 $i$ 位），对每个方程 $j$，若

$$C_j+\sum_{k\in[L'_j,R'_j]}X_k \equiv \text{第 }i\text{ 位 }S_j'\pmod 2,$$

则新进位

$$C'_j=\frac{C_j+\sum_{k}X_k - \text{第 }i\text{ 位 }S_j'}{2},$$

并把 $dp_{i+1}[C']$ 累加上 $dp_i[C]$。

实现技巧：$2^N\le 256$ 种数字组合与进位组合可以预先枚举好。按"每个方程数字和 $x_j$ 的奇偶向量 $p$"分组，预处理出所有"奇偶向量为 $p$ 的数字组合"对应的 $\lfloor x_j/2\rfloor$ 向量及其数量，DP 时直接查表，避免每层重复枚举。

最终答案 $=dp_{30}[(0,\ldots,0)]\bmod 998244353$（进位全为 $0$ 表示所有方程的和精确等于 $S_j'$）。注意要单独维护"该状态是否可达"（即 $dp>0$），因为计数取模后可能恰为 $0$ 但方案数仍为正。

参考代码

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

using ll = long long;
const ll MOD = 998244353;

int n, m;
int base[9];      // k_j：代表元下标
ll offset[9];     // D_j：满足 P_j = P_{base[j]} + offset[j]
vector<int> dmask;   // 每个化简方程覆盖的 B 变量集合（bitmask，bit i 表示 B_{i+1}）
vector<ll> ds;       // 每个化简方程的右端 S'_j

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

    cin >> n >> m;
    for (int i = 0; i <= n; i++) { base[i] = i; offset[i] = 0; }

    // 处理原始约束，维护 P_j = P_{base[j]} + offset[j]
    for (int i = 0; i < m; i++) {
        int l, r; ll S;
        cin >> l >> r >> S;
        l--;                          // L_i - 1
        S -= (r - l);                 // 转成非负整数版本
        if (S < 0) { cout << 0 << '\n'; return 0; }
        int a = l, b = r;             // 约束：P_b - P_a = S
        if (base[a] == base[b]) {
            if (offset[b] - offset[a] != S) { cout << 0 << '\n'; return 0; }
            continue;                 // 已被已有条件自动满足
        }
        int ob, oa; ll add;
        if (base[a] < base[b]) {
            ob = base[b]; oa = base[a];
            add = offset[a] - offset[b] + S;    // P_{base[b]} = P_{base[a]} + add
        } else {
            ob = base[a]; oa = base[b];
            add = offset[b] - offset[a] - S;
        }
        for (int j = 0; j <= n; j++) if (base[j] == ob) {
            base[j] = oa;
            offset[j] += add;
        }
    }

    // 提取化简后的独立方程
    bool used[8] = {};
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (base[i] == base[j]) {
                if (offset[j] - offset[i] < 0) { cout << 0 << '\n'; return 0; }
                int mask = 0;
                for (int ii = i; ii < j; ii++) { mask |= 1 << ii; used[ii] = true; }
                dmask.push_back(mask);
                ds.push_back(offset[j] - offset[i]);
                break;
            }
        }
    }
    int K = (int)dmask.size();        // M'

    // 预处理：按"方程内数字和的奇偶向量"分组
    // groups[p] = { (zpart, count) }，其中 p[j] = (x_j mod 2)，zpart[j] = x_j >> 1
    vector<vector<pair<int, int>>> groups(1 << K);
    {
        unordered_map<int, int> tmp[1 << 8];
        for (int mask = 0; mask < (1 << n); mask++) {
            int x[8] = {};
            for (int j = 0; j < K; j++) {
                for (int ii = 0; ii < n; ii++) if (dmask[j] >> ii & 1) x[j] += (mask >> ii) & 1;
            }
            int parity = 0, zpart = 0;
            for (int j = 0; j < K; j++) {
                parity |= (x[j] & 1) << j;
                zpart |= (x[j] >> 1) << (3 * j);
            }
            tmp[parity][zpart]++;
        }
        for (int p = 0; p < (1 << K); p++)
            for (auto &pr : tmp[p]) groups[p].push_back(pr);
    }

    // 二进制按位 DP：dpkey 用每 3 位存一个进位 C_j（0..7）
    vector<int> dpkey = {0};
    vector<ll> dpcnt = {1};
    for (int bit = 0; bit < 30; bit++) {
        unordered_map<int, ll> mp;
        for (size_t idx = 0; idx < dpkey.size(); idx++) {
            int key = dpkey[idx];
            ll cnt = dpcnt[idx];
            int y[8] = {};
            for (int j = 0; j < K; j++) y[j] = (key >> (3 * j)) & 1;            // C_j mod 2
            int pre = 0;
            for (int j = 0; j < K; j++) pre |= ((key >> (3 * j + 1)) & 3) << (3 * j); // C_j >> 1
            int add_key = 0;
            for (int j = 0; j < K; j++) {
                int sbit = (ds[j] >> bit) & 1;                                  // S'_j 的第 bit 位
                add_key |= (sbit ^ y[j]) << j;                                  // 需要的 x_j 奇偶性
                if (sbit == 0 && y[j] == 1) pre += 1 << (3 * j);                // (C_j+1)/2 中的 +1
            }
            for (auto &pr : groups[add_key]) {
                mp[pre + pr.first] = (mp[pre + pr.first] + (ll)pr.second * cnt) % MOD;
            }
        }
        dpkey.clear(); dpcnt.clear();
        for (auto &pr : mp) {
            dpkey.push_back(pr.first);
            dpcnt.push_back(pr.second);
        }
    }

    bool found = false;
    ll ans = 0;
    for (size_t i = 0; i < dpkey.size(); i++) {
        if (dpkey[i] == 0) { found = true; ans = dpcnt[i]; }
    }
    if (!found) {
        cout << 0 << '\n';              // 约束变量无可行解
    } else {
        for (int i = 0; i < n; i++)
            if (!used[i]) { cout << "Infinity\n"; return 0; }   // 有自由变量
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

• 第一步的并查集部分：$O(NM)$（$N\le 8$，实际可视为 $O(M)$）
• 预处理部分：$O(2^N \cdot N \cdot M')$
• 按位 DP：进位组合数至多 $\prod_j (R'_j-L'_j+1)\le 1024$，每层枚举 $2^N$ 种数字组合，共 $30$ 层，即 $O(30\cdot 1024\cdot 2^N)$（约 $8\times 10^6$ 量级）
• 空间复杂度：$O(1024+2^N)$

---

以上就是 ABC466 的全部七题题解。本场以 F、G 两题最有含金量：F 考察"区间多重集 + 优先队列"的抽象能力，G 综合了带权并查集与按位 DP，值得反复推敲。