P1007小核桃与数组变换 普及/提高- CSP-J组 模拟 标准IO 传统题 来源 TomAnderson 时间限制 1000ms 内存限制 256MB 通过/尝试次数 1188/3750 题目描述 一个长度为 n n 的数组，每秒都在发生变换。 每一次变换，第 1 1 个位置的数字将会和第 2 2 个位置的数字合并，第 3 3 个位置的数字将会和第 4 4 个位置的数字合并，以此类推。。 这个数组会一直变换到只剩两个数字为止。 合并数字时，将会使得两个数字相加。例如数组 [1,2,3,4,5] 第一秒会变成 [3,7,5]（前两个数字合并，第三和第四个数字合并，由于没有第六个数字，所以第五个数字不变）第二秒会变成 [10, 5]，此时数组中只剩两个数字，变换结束。 现在小核桃想知道最后的两个数字的平方和是多少。例如上述数组，平方和为 10 ∗ 10 + 5 ∗ 5 = 125 10∗10+5∗5=125 由于这个数组长度很大，所以小核桃在给你数据时采用了一种新的方式。小核桃总共会给出 k k 条信息，每条信息包含两个正整数 a , b a,b，表示这个数组中有一段长度为 a a 的

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> const int MOD = 1e9 + 7; // 合并数组直到只剩下两个数字 std::vector<long long> mergeArray(const std::vector<long long>& arr) { std::vector<long long> newArr; for (int i = 0; i < arr.size(); i += 2) { if (i + 1 < arr.size()) { newArr.push_back((arr[i] + arr[i + 1]) % MOD); } else { newArr.push_back(arr[i]); } } return newArr; } // 计算最终两个数字的平方和 long long calculateSquareSum(std::vector<long long> arr) { while (arr.size() > 2) { arr = mergeArray(arr); } long long num1 = arr[0]; long long num2 = arr[1]; return (num1 * num1 % MOD + num2 * num2 % MOD) % MOD; } int main() { long long n, k; std::cin >> n >> k; std::vector<long long> arr; for (int i = 0; i < k; ++i) { long long a, b; std::cin >> a >> b; for (long long j = 0; j < a; ++j) { arr.push_back(b); } } long long result = calculateSquareSum(arr); std::cout << result << std::endl; return 0; } ``` 代码解释： 1. `mergeArray` 函数：该函数接受一个 `std::vector<long long>` 类型的数组，将数组中相邻的元素两两合并，若最后一个元素没有相邻元素，则直接保留。合并后的元素对 `MOD` 取模，避免溢出。 2. `calculateSquareSum` 函数：该函数不断调用 `mergeArray` 函数，直到数组中只剩下两个元素。最后计算这两个元素的平方和，并对 `MOD` 取模。 3. `main` 函数：读取输入的 `n` 和 `k`，然后读取 `k` 组 `a` 和 `b`，将 `a` 个 `b` 加入到数组 `arr` 中。调用 `calculateSquareSum` 函数计算最终结果并输出。 复杂度分析： - 时间复杂度：每次合并数组的时间复杂度为 $O(n)$，最多需要合并 $\log n$ 次，因此总的时间复杂度为 $O(n \log n)$。 - 空间复杂度：主要使用了一个数组来存储元素，空间复杂度为 $O(n)$。 [2026-02-07 18:25:02 | AI问答 | 651点数解答]