AtCoder Beginner Contest 378 解题思路与算法实现
A - Pairing
本题考察基础的模拟操作。根据题目给定的配对规则，直接遍历并统计符合条件的对数即可，时间复杂度为 \(O(N)\)。
B - Garbage Collection
目标是寻找一个不小于 \(d\) 的最小整数 \(x\)，使得 \(x \bmod q = r\)。可以通过分类讨论或数学推导直接计算。首先计算 \(d \bmod q\) 的值，然后根据其与 \(r\) 的大小关系，调整 \(d\) 使其满足同余条件，从而在 \(O(1)\) 时间内得出答案。
C - Repeating
这是一道直接的模拟题。按照题目描述的过程，使用哈希表或数组记录每个元素上一次出现的位置，并在遍历过程中实时更新答案，确保每个元素都能快速找到其前一个相同元素的位置。
D - Count Simple Paths
本题要求计算图中的简单路径数量。由于数据规模较小，可以采用深度优先搜索（DFS）进行暴力枚举。从每个可能的起点出发，使用回溯法遍历所有不重复访问节点的路径，并累加合法路径的总数。需要注意在递归返回时恢复节点的访问状态。
E - Mod Sigma Problem
题目要求计算所有子数组和对 \(M\) 取模的总和。
设前缀和数组 \(S_i = (\sum_{k=1}^i A_k) \bmod M\)，且 \(S_0 = 0\)。子数组和取模可以表示为 \((S_r - S_{l-1}) \bmod M\)。
由于 \(0 \le S_{l-1}, S_r < M\)，上式可展开为：
这样就去除了取模运算。对于固定的右端点 \(r\)，我们需要计算 \(\sum_{l=1}^r (S_r - S_{l-1} + M \cdot [S_{l-1} > S_r])\)。这可以拆分为三部分：
- \(r \times S_r\)
- \(-\sum_{l=1}^r S_{l-1}\)
- \(M \times (\text{满足 } S_{l-1} > S_r \text{ 的 } l \text{ 的个数})\)
前两部分可以通过维护前缀和的累加值来 \(O(1)\) 计算。第三部分需要统计历史前缀和中大于 \(S_r\) 的元素个数，这可以通过值域树状数组（Fenwick Tree）来高效维护。
关键细节：树状数组的下标不能为 0，因此在将 \(S_i\) 插入树状数组时，需要将所有值统一加 1（即维护 \(S_i + 1\)），以避免 lowbit(0) 导致的死循环。
#include <iostream>
#include <vector>
using namespace std;
class FenwickTree {
private:
vector<long long> tree;
int size;
int lowbit(int x) const {
return x & (-x);
}
public:
FenwickTree(int n) : size(n), tree(n + 1, 0) {}
void update(int index, long long delta) {
for (int i = index; i <= size; i += lowbit(i)) {
tree[i] += delta;
}
}
long long query(int index) const {
long long sum = 0;
for (int i = index; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
long long m;
if (!(cin >> n >> m)) return 0;
vector<long long> a(n + 1);
vector<long long> prefix_mod(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
prefix_mod[i] = (prefix_mod[i - 1] + a[i]) % m;
}
FenwickTree bit(m + 1);
long long prefix_sum_mod = 0;
long long result = 0;
// Insert S_0 = 0 (mapped to 1 in BIT)
bit.update(1, 1);
for (int r = 1; r <= n; ++r) {
long long sr = prefix_mod[r];
// r * S_r
result += sr * r;
// - sum(S_{l-1})
result -= prefix_sum_mod;
// + M * count(S_{l-1} > S_r)
long long count_greater = bit.query(m + 1) - bit.query(sr + 1);
result += count_greater * m;
// Update states for next iterations
prefix_sum_mod += sr;
bit.update(sr + 1, 1);
}
cout << result << "\n";
return 0;
}
F - Add One Edge 2
题目要求统计满足特定条件的顶点对 \((u, v)\)（其中 \(u < v\)）的数量。条件如下：
- \(u\) 和 \(v\) 的度数均为 2。
- \(u\) 和 \(v\) 之间的简单路径上，除 \(u, v\) 外的所有中间顶点的度数均为 3。
我们可以将图中所有度数均为 3 的相邻顶点用并查集（Disjoint Set Union, DSU）合并，形成若干个连通块。这些连通块代表了由度数为 3 的顶点组成的"核心路径"。
对于每个连通块，我们统计与其直接相连且度数为 2 的顶点数量，记为 \(C_i\)。满足条件的点对 \((u, v)\) 必然属于同一个连通块的外部连接点。因此，对于第 \(i\) 个连通块，它能贡献的合法点对数量为 \(\frac{C_i \times (C_i - 1)}{2}\)。最后将所有连通块的贡献值求和即可。
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
struct DSU {
vector<int> parent;
DSU(int n) : parent(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int i) {
return parent[i] == i ? i : parent[i] = find(parent[i]);
}
void unite(int i, int j) {
parent[find(i)] = find(j);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
if (!(cin >> n)) return 0;
vector<pair<int, int>> edges(n - 1);
vector<int> deg(n, 0);
for (int i = 0; i < n - 1; ++i) {
cin >> edges[i].first >> edges[i].second;
edges[i].first--; edges[i].second--;
deg[edges[i].first]++;
deg[edges[i].second]++;
}
DSU dsu(n);
for (int i = 0; i < n - 1; ++i) {
int u = edges[i].first, v = edges[i].second;
if (deg[u] == 3 && deg[v] == 3) {
dsu.unite(u, v);
}
}
vector<long long> c2(n, 0);
for (int i = 0; i < n - 1; ++i) {
int u = edges[i].first, v = edges[i].second;
if (deg[u] == 3 && deg[v] == 2) c2[u]++;
else if (deg[u] == 2 && deg[v] == 3) c2[v]++;
}
vector<long long> comp_c2(n, 0);
for (int i = 0; i < n; ++i) {
comp_c2[dsu.find(i)] += c2[i];
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
if (dsu.find(i) == i) {
ans += comp_c2[i] * (comp_c2[i] - 1) / 2;
}
}
cout << ans << "\n";
return 0;
}
G - Everlasting LIDS
本题涉及复杂的动态规划与组合数学推导，难度较高。建议直接查阅 AtCoder 官方提供的题解文档与标准代码，以获取最严谨的数学证明与状态转移方程解析。
