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，表示这个数

以下是解决该问题的Python代码： ```python MOD = 109 + 7 # 读取输入 n, k = map(int, input().split()) # 构建初始数组 arr = [] for _ in range(k): a, b = map(int, input().split()) arr.extend([b] * a) # 进行数组变换 while len(arr) > 2: new_arr = [] for i in range(0, len(arr), 2): if i + 1 < len(arr): new_arr.append(arr[i] + arr[i + 1]) else: new_arr.append(arr[i]) arr = new_arr # 计算最后的两个数字的平方和并取模 result = (arr[0]2 + arr[1]2) % MOD print(result) ``` 代码解释 1. 读取输入：首先读取数组的长度`n`和信息的条数`k`，然后根据每条信息构建初始数组`arr`。 2. 数组变换：使用一个`while`循环，只要数组的长度大于2，就继续进行变换。在每次变换中，将相邻的两个数字相加，构建新的数组`new_arr`。 3. 计算平方和并取模：当数组的长度变为2时，计算这两个数字的平方和，并对`MOD`取模。 4. 输出结果：输出最后的结果。 复杂度分析 - 时间复杂度：每次变换数组的长度至少减半，因此变换的次数为$O(log n)$。每次变换需要遍历数组，时间复杂度为$O(n)$。总的时间复杂度为$O(n log n)$。 - 空间复杂度：主要的空间开销是存储数组，因此空间复杂度为$O(n)$。 [2026-02-07 18:24:18 | AI问答 | 416点数解答]