[NOIP 2015 普及组] 求和

题目背景

NOIP2015 普及组 T3

题目描述

一条狭长的纸带被均匀划分出了 $n$ 个格子，格子编号从 $1$ 到 $n$。每个格子上都染了一种颜色 $colo{r}_i$ 用 $[1,m]$ 当中的一个整数表示），并且写了一个数字 $numbe{r}_i$。

编号	1	2	3	4	5	6
颜色和数字	$5$	$5$	$3$	$2$	$2$	$2$

定义一种特殊的三元组：$(x,y,z)$，其中 $x,y,z$ 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

1. $x,y,z$ 都是整数，$x<y<z,y-x=z-y$。

2. $colo{r}_x=colo{r}_z$。

满足上述条件的三元组的分数规定为 $(x+z)\times (numbe{r}_x+numbe{r}_z)$。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 $10007$ 所得的余数即可。

输入格式

第一行是用一个空格隔开的两个正整数 $n$ 和 $m,n$ 表纸带上格子的个数，$m$ 表纸带上颜色的种类数。

第二行有 $n$ 用空格隔开的正整数，第 $i$ 个数字表示纸带上编号为 $i$ 格子上面写的数字 $numbe{r}_i$。

第三行有 $n$ 用空格隔开的正整数，第 $i$ 数字表示纸带上编号为 $i$ 格子染的颜色 $colo{r}_i$。

输出格式

一个整数，表示所求的纸带分数除以 $10007$ 所得的余数。

输入输出样例 #1

输入 #1

6 2
5 5 3 2 2 2
2 2 1 1 2 1

输出 #1

82

输入输出样例 #2

输入 #2

15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

输出 #2

1388

说明/提示

样例 1 解释

纸带如题目描述中的图所示。

所有满足条件的三元组为：$(1,3,5),(4,5,6)$。

所以纸带的分数为 $(1+5)\times (5+2)+(4+6)\times (2+2)=42+40=82$。

对于第 $1$ 组至第 $2$ 组数据， $1\le n\le 100,1\le m\le 5$；

对于第 $3$ 组至第 $4$ 组数据，$1\le n\le 3000,1\le m\le 100$；

对于第 $5$ 组至第 $ 6 $ 组数据，$1\le n\le 100000,1\le m\le 100000$，且不存在出现次数超过 $ 20 $ 的颜色；

对于全部 $10$ 组数据，$1\le n\le 100000,1\le m\le 100000,1\le colo{r}_i\le m,1\le numbe{r}_i\le 100000$。

核心思路分析

如果直接枚举所有可能的 (i, j) 二元组，时间复杂度为 O(n²)，当 n 较大时会超时。因此需要优化计算方式：
通过拆分贡献表达式，用前缀累计的方式记录中间结果，将时间复杂度降至 O(n)。

贡献表达式拆分

对于符合条件的二元组 (i, j)（i < j），其贡献为：

(i + j) * (num[i] + num[j])

展开后可拆分为 4 项：

= i*num[i] + i*num[j] + j*num[i] + j*num[j]

当处理到 j 时，所有满足条件的 i（i < j、同色、同奇偶）已经被处理过。因此可以累计这些 i 的信息，直接计算它们对 j 的贡献，而无需重复枚举。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, m, num[114514], color[114514];
int a1[114514][2], a2[114514][2],a3[114514][2],a4[114514][2]; 
const int p = 10007;

// a1 x * numx // a2 x
// a3 numx // a4 1 
int main(){
	scanf("%d%d", &n, &m); 
	for (int i = 1; i<= n; i++) 
		scanf("%d", &num[i]); 
	for (int i = 1; i <= n; i++)
		scanf("%d", &color[i]); 
	int ans = 0;
	for(int i = 1;i <= n;i++){
		int y = i % 2;
		ans += a1[color[i]][y]; ans %= p;
		ans += a2[color[i]][y] * num[i]; ans %= p;
		ans += a3[color[i]][y] * i; ans %= p;
		ans += a4[color[i]][y] * i % p * num[i] % p; ans %= p;
		a1[color[i]][y] += 1LL * i * num[i] % p;
		a1[color[i]][y] %= p;
		a2[color[i]][y] += i; a2[color[i]][y] %= p;
		a3[color[i]][y] += num[i]; a3[color[i]][y] %= p;
		++a4[color[i]][y]; a4[color[i]][y] %= p;
	}
	printf("%d",ans);
	return 0;
} 

代码变量与数组解析

代码中定义了 4 个核心数组，用于累计「符合条件的 i」的信息（按颜色和奇偶性分组）：

• a1[c][y]：累计颜色为 c、奇偶性为 y 的所有 i 的 i * num[i] 之和；
• a2[c][y]：累计颜色为 c、奇偶性为 y 的所有 i 的 i 之和；
• a3[c][y]：累计颜色为 c、奇偶性为 y 的所有 i 的 num[i] 之和；
• a4[c][y]：累计颜色为 c、奇偶性为 y 的所有 i 的数量（即满足条件的 i 的个数）。

其中 c 表示颜色，y 表示奇偶性（0 为偶，1 为奇）。

代码执行流程详解

1. 输入数据：读入 n（元素个数）、m（颜色数，代码中未直接使用），以及数组 num（数值）和 color（颜色）。

2. 初始化答案：ans = 0，用于累计所有二元组的贡献和。

3. 遍历每个元素 j（从 1 到 n）：

   • 计算 j 的奇偶性 y = j % 2（0 为偶，1 为奇）。

   • 取出 j 的颜色 c = color[j]。

   • 累加当前 j 的贡献：
     对于所有已处理的 i < j（且 color[i] = c、i%2 = y），它们对 j 的贡献是拆分后的 4 项之和：

     ans += a1[c][y];                // 对应 i*num[i] 的和
     ans += a2[c][y] * num[j];       // 对应 i*num[j] 的和（num[j] 是常数，乘以 i 的和）
     ans += a3[c][y] * j;            // 对应 j*num[i] 的和（j 是常数，乘以 num[i] 的和）
     ans += a4[c][y] * j * num[j];   // 对应 j*num[j] 的和（j*num[j] 是常数，乘以 i 的个数）
     

     每步累加后都对 10007 取模，防止溢出。

   • 更新累计数组：
     将当前 j 的信息加入对应分组（颜色 c、奇偶性 y），供后续元素（k > j）计算贡献：

     a1[c][y] += (j * num[j]) % p;   // 累计 i*num[i]（当前 j 作为未来的 i）
     a2[c][y] += j % p;              // 累计 i（当前 j 作为未来的 i）
     a3[c][y] += num[j] % p;         // 累计 num[i]（当前 j 作为未来的 i）
     a4[c][y] += 1;                  // 累计 i 的数量（当前 j 作为未来的 i）
     

     同样每步对 10007 取模。

4. 输出结果：打印最终的 ans % 10007。

总结

这段代码的核心是通过拆分贡献表达式和分组累计前缀信息，将原本 O(n²) 的枚举优化为 O(n) 的线性遍历，高效求解了符合条件的二元组贡献和。关键在于用 4 个数组记录不同维度的累计值，避免重复计算。