P1007 小核桃与数组变换：二进制分割求平方和的高效解法

好的，这是一个非常典型的模拟与数学结合的问题。核心难点在于**数据规模极大**（`n` 可到 `10^18`），不能直接构造整个数组，必须利用输入的压缩表示（区间段）直接进行**模拟合并过程**。 我们来一步步分析并给出高效的 C++ 解法。 --- ## 🧠 问题分析 - 给定一个长度为 `n` 的数组，由 `k` 段组成，每段是连续的相同数字。 - 每秒进行**相邻合并**：`(1,2), (3,4), ...` 相加，数组长度减少一半左右。 - 直到剩下两个数字，求它们的平方和模 `1e9+7`。 --- ### 🔍 关键观察 1. **合并过程是确定性的**，与具体数值无关，只与位置有关。 2. 每次合并将**相邻两个位置**的数字相加，形成新数组。 3. 合并过程可以看作是在**原始数组的索引上**进行 **二叉树合并** 模拟： - 最终的两个数字，分别对应原始数组中**某些连续段的和**。 - 例如：原始数组索引 `0..n-1`，最终左边的数字是 `[0..mid-1]` 的和，右边是 `[mid..n-1]` 的和，其中 `mid` 是某个位置。 4. 具体 `mid` 如何确定？ - 合并过程等价于反复进行 **奇偶位置划分**。 - 每次合并，将相邻两个数相加，相当于在新的数组中，第 `i` 个位置对应原始数组中第 `2*i` 和 `2*i+1` 的和。 - 最终两个数字，实际上对应原始数组中**按二进制位划分左右**的两个大区间。 --- ### 🧮 数学模型 对于长度为 `n` 的数组，最终两个数字分别对应： - **左数** = 原始数组中所有索引 **二进制表示最高位为 0** 的数的和。 - **右数** = 原始数组中所有索引 **二进制表示最高位为 1** 的数的和。 > 更直观：将 `n` 表示为二进制，最高位是 `2^(m-1)`。 > 则： > - 左数对应索引 `[0, 2^(m-1)-1]` 的和 > - 右数对应索引 `[2^(m-1), n-1]` 的和 #### ✅ 举例验证 样例1：`n=5`，`2^(m-1) = 4` - 左: 索引 `0..3` => 数组 [1,2,3,4] 和 = 10 - 右: 索引 `4` => [5] 和 = 5 结果：`10^2 + 5^2 = 125` ✔️ 样例2：`n=7`，`2^(m-1) = 4` - 左: 索引 `0..3` => [1,1,1,2] 和 = 5 - 右: 索引 `4..6` => [2,2,2] 和 = 6 结果：`5^2 + 6^2 = 61` ✔️ --- ### 🚀 算法步骤 1. **确定分割点**： - 找到 `n` 的最高位 `h`，即 `h = 1 << (floor(log2(n-1)))`。 - 分割点就是 `mid = h`。 2. **计算左右区间和**： - 我们已经有压缩表示的数组：`(length, value)` 段。 - 通过遍历这些段，累加索引到 `[0, mid-1]` 范围的值的和 `sum_left`，以及 `[mid, n-1]` 范围的值的和 `sum_right`。 3. **计算平方和**： - `ans = (sum_left % MOD)^2 + (sum_right % MOD)^2` 再取模。 --- ### ⚠️ 注意事项 - 数据范围极大，`n <= 1e18`，要使用 `unsigned long long`。 - 段数 `k <= 1e5`，遍历是可行的。 - 模数是 `1e9+7`，注意溢出，使用 `long long` 并在乘法时取模。 --- ## 💻 C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; using ull = unsigned long long; using ll = long long; const ll MOD = 1e9 + 7; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ull n, k; cin >> n >> k; vector<pair<ull, ull>> segs(k); for (auto &[a, b] : segs) { cin >> a >> b; } // 1. 找到最高位 ull h = 1; while ((h << 1) <= n) { h <<= 1; } // 2. 计算左右区间的和 ull left_sum = 0, right_sum = 0; ull pos = 0; // 当前索引位置 for (auto [len, val] : segs) { ull start = pos; ull end = pos + len - 1; if (start < h) { // 区间与左区间重叠 ull overlap_left = min(h - 1, end) - start + 1; left_sum = (left_sum + overlap_left * val) % MOD; } if (end >= h) { // 区间与右区间重叠 ull overlap_right = end - max(start, h) + 1; right_sum = (right_sum + overlap_right * val) % MOD; } pos += len; } // 3. 计算平方和 ll ans = ((left_sum % MOD) * (left_sum % MOD) + (right_sum % MOD) * (right_sum % MOD)) % MOD; cout << ans << "\n"; return 0; } ``` --- ### 📌 复杂度分析 - **时间复杂度**：`O(k)`，只需遍历一遍压缩段。 - **空间复杂度**：`O(k)`，存储输入的段。 --- ### 💡 开发建议 1. **使用 `unsigned long long`** 处理大长度，避免有符号溢出。 2. **模运算注意顺序**：先取模再相乘，防止 `long long` 溢出。 3. **输入输出优化**：`ios::sync_with_stdio(false)` 和 `cin.tie(nullptr)` 加速。 4. **理解二进制分割规则**：这是解决此类“合并至两个数”问题的通用数学化简方法。 5. **测试用例**：建议多测试边界情况，如 `n=2`，`n=3`，`n=1e18` 等。 --- ######[AI写代码神器 | 1560点数解答 | 2026-07-04 08:25:22]