[noip2015-普及] 求和

题目描述

$n$ 格纸带各有颜色 $color_i$ 与数字 $number_i$ ，求所有满足 $x<y<z$ 、 $x+z=2y$ 、 $color_x=color_z$ 的三元组分数 $(x+z)(number_x+number_z)$ 之和模 10007（ $n \le 10^5$ ）。

思路

$x+z=2y$ 要求 $x,z$ 同奇偶，按奇偶、颜色分组后，枚举每组内配对并累计 $(x+z)(number_x+number_z)$ ；展开后维护 $\sum x$ 、 $\sum number$ 等前缀量即可 $O(n)$ 合计，对 10007 取模。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 11:20
# update_at: 2026-10-02 11:20

import sys
from collections import defaultdict

MOD = 10007  # 题面要求的取模值


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    numbers = [next(data) for _ in range(n)]
    colors = [next(data) for _ in range(n)]

    # 三元组 (x,y,z) 要求 x+z=2y，即 x、z 同奇偶，且 color[x]=color[z]。
    # 于是按 (颜色, 下标奇偶) 分桶，每桶统计 [个数 k, 下标和, 数字和, 下标x数字积和]。
    acc: dict[tuple[int, int], list[int]] = defaultdict(lambda: [0, 0, 0, 0])
    for i, (num, col) in enumerate(zip(numbers, colors), 1):
        g = acc[(col, i & 1)]
        g[0] += 1                        # k
        g[1] += i                        # S_i = sum i
        g[2] += num                      # S_a = sum number_i
        g[3] += i * num                  # S_ia = sum i*number_i

    # 桶内无序对 {i,j} 的贡献 (i+j)(a_i+a_j) 求和展开：
    # 每个 i*a_i 在 k-1 个对里各出现一次，i*a_j + j*a_i 交叉项合计 S_i*S_a - S_ia，
    # 合起来即 (k-2)*S_ia + S_i*S_a。
    ans = sum((k - 2) * s_ia + s_i * s_a for k, s_i, s_a, s_ia in acc.values()) % MOD
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:25
 * update_at: 2026-10-06 15:25
 */

#include <cstdio>
using namespace std;

typedef long long ll;

const int MOD = 10007;
const int MAXM = 100005;

// 桶结构：按 (颜色, 奇偶) 分组，每组维护 [个数k, 下标和, 数字和, 下标x数字积和]
// 奇偶用 0/1 表示，颜色范围 [1, m]
struct Bucket {
    int cnt;    // k
    ll sum_i;   // Σi
    ll sum_a;   // Σa_i
    ll sum_ia;  // Σi*a_i
    Bucket(): cnt(0), sum_i(0), sum_a(0), sum_ia(0) {}
};

// 颜色最多 1e5，奇偶 2 种，开二维数组
Bucket bucket[MAXM][2];

int n, m;
ll num[MAXM]; // number_i，下标从 1 开始
int col[MAXM]; // color_i，下标从 1 开始

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &num[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &col[i]);

    // 按 (颜色, 下标奇偶) 分桶，统计 4 个量
    for (int i = 1; i <= n; i++) {
        int c = col[i];
        int p = i & 1; // 0 表示偶数下标，1 表示奇数下标
        bucket[c][p].cnt++;
        bucket[c][p].sum_i += i;
        bucket[c][p].sum_a += num[i];
        bucket[c][p].sum_ia += (ll)i * num[i];
    }

    // 桶内无序对 {i,j} 的贡献 (i+j)(a_i+a_j) 求和展开：
    // 每个 i*a_i 在 k-1 个对里各出现一次，交叉项合计 sum_i * sum_a - sum_ia，
    // 合起来即 (k-2)*sum_ia + sum_i*sum_a。
    ll ans = 0;
    for (int c = 1; c <= m; c++) {
        for (int p = 0; p <= 1; p++) {
            Bucket &b = bucket[c][p];
            if (b.cnt < 2) continue; // k<2 时贡献为 0
            ll contrib = (ll)(b.cnt - 2) * b.sum_ia + b.sum_i * b.sum_a;
            ans += contrib;
        }
    }

    ans %= MOD;
    if (ans < 0) ans += MOD;
    printf("%lld\n", ans);
    return 0;
}

[noip2015-普及] 求和

目录

题目描述

思路

参考代码