[NOIP 2015 普及组] 求和

GitHub跳转原题关系图返回列表

把三元组化成同颜色同奇偶的端点对，再按颜色和奇偶分组维护四个历史统计量线性求和。

OJ: luogu

题目 ID: P2671

难度:普及/提高-

标签:数学计数推导模拟noippython

日期: 2026-06-20 13:15

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

纸带上有 n 个位置，每个位置有一个数字 number_i 和一种颜色 color_i。

三元组 (x,y,z) 合法，当且仅当：

  • x < y < z
  • y - x = z - y
  • color_x = color_z

合法三元组的得分是：

  • (x + z) * (number_x + number_z)

要求所有合法三元组得分总和，对 10007 取模。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;
const int MOD = 10007;

int n, m;
int number_val[MAXN];
int color_val[MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> number_val[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> color_val[i];
    }

    int answer = 0;

    // 直接枚举左右端点 x,z。
    // 只要它们同颜色、并且中点 y 是整数，就会对应一个合法三元组。
    for (int x = 1; x <= n; x++) {
        for (int z = x + 1; z <= n; z++) {
            if (((x + z) & 1) != 0) continue;
            if (color_val[x] != color_val[z]) continue;

            int y = (x + z) / 2;
            if (!(x < y && y < z)) continue;

            int score = 1LL * (x + z) * (number_val[x] + number_val[z]) % MOD;
            answer += score;
            answer %= MOD;
        }
    }

    cout << answer % MOD << '\n';
    return 0;
}

关键观察是：题目里的中点 y 其实不是重点，真正决定合法性的只有两端点 x,z。

因为：

  • y - x = z - y

等价于：

  • y = (x + z) / 2

所以只要 x < z 且 x + z 为偶数，就存在唯一的整数中点 y。 也就是说，合法三元组等价于：

  1. x < z
  2. x,z 同奇偶
  3. color_x = color_z

于是我们只需要统计“同颜色、同奇偶”的端点对贡献。

固定当前位置 i 作为右端点 z， 它能配对的左端点，全部来自同一个 (颜色, 奇偶) 分组。

设这些历史左端点的总贡献为：

  • sum (x + i) * (number_x + number_i)

展开后得到四项：

  • sum(x * number_x)
  • i * sum(number_x)
  • number_i * sum(x)
  • cnt * i * number_i

所以对每个 (颜色, 奇偶) 分组，只要维护：

  1. 个数 cnt
  2. 位置和 sum_pos
  3. 数值和 sum_num
  4. 位置 * 数值 的和 sum_pos_num

就能在 O(1)O(1) 时间算出当前位置作为右端点时的全部贡献。

从左到右扫一遍，先算贡献，再把当前点加入统计即可。

Python 知识

  • zip(numbers, colors) 并行遍历两个属性序列，enumerate(..., 1) 提供一基位置。
  • 用 key = 2 * color + position % 2 把 (颜色, 奇偶) 压成一个列表下标。
  • 四个列表分别保存计数、位置和、数值和与乘积和，比嵌套字典更节省对象开销。

代码

python
import sys


MOD = 10007
input = sys.stdin.buffer.readline
n, m = map(int, input().split())
numbers = list(map(int, input().split()))
colors = map(int, input().split())
size = 2 * (m + 1)
count = [0] * size
sum_position = [0] * size
sum_number = [0] * size
sum_product = [0] * size
answer = 0

for position, (number, color) in enumerate(zip(numbers, colors), 1):
    key = 2 * color + position % 2
    answer += (sum_product[key] + position * sum_number[key]
               + number * sum_position[key]
               + count[key] * position * number)
    count[key] += 1
    sum_position[key] = (sum_position[key] + position) % MOD
    sum_number[key] = (sum_number[key] + number) % MOD
    sum_product[key] = (sum_product[key] + position * number) % MOD

print(answer % MOD)

复杂度

每个位置只处理一次，时间复杂度 O(n)O(n)； 按颜色和奇偶维护统计量，空间复杂度 O(m)O(m)。

总结

这题最关键的是先把三元组条件化简成端点对条件：

  • 同颜色
  • 同奇偶

一旦去掉了中点 y 这个表面信息，后面就是一个很自然的分组统计题。