标签：P2671 NOIP2015 求和 sum 纸带 times int cdots color

[NOIP2015 普及组] 求和

题目背景

NOIP2015 普及组 T3

题目描述

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

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

$xyz$是整数,$x<y<z,y-x=z-y$
$colorx=colorz$

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

输入格式

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

第二行有$n$用空格隔开的正整数，第$i$数字$number$表纸带上编号为$i$格子上面写的数字。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

样例 #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

提示

【输入输出样例 1 说明】

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

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

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

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

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

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

对于全部 $10$ 组数据， $1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ color_i ≤ m,1≤number_i≤100000$

思路

一开始想到$O(n^2)$的算法。

$\because y-x=z-$
$\therefore x + z=2\times y$

所以暴力枚举$x,z$就好了。但是肯定会$TLE$。

我们把所有数按颜色分成$m$组，然后为了枚举下标再开两个位置来判断下标的奇偶性（因为前面$x+z=2\times y$，所以$x,z$奇偶性相同）。

假设一组里的数分别是$x_1,x_2,\cdots,x_k$，下标是$y_1,y_2,\cdots,y_k$
那么答案$=(x_1 + x_2) \times (y_1 + y_2) + (x_1 + x_3) \times (y_1 + y_3)+\dots$
$~~~~~~~~~~~~~=x_1\times(y_1 + y_2 + y_1 + y _ 3 + \cdots + y_1 + y_k) + x_2\times(y_2 + y_1 + y_2 + y _ 3 + \cdots + y_2 + y_k) + \cdots + x_k\times(y_k + y_1 + y_k + y _ 2 + \cdots + y_k + y_{k-1})$
$~~~~~~~~~~~~~=x_1\times(y_1 \times (k - 2) + \sum\limits_{i=1}^k{y_i}) + x_2\times(y_2 \times (k - 2) + \sum\limits_{i=1}^k{y_i}) + \cdots + x_k\times(y_k \times (k - 2) + \sum\limits_{i=1}^k{y_i})$

这里每一个式子里都有$\sum\limits_{i=1}^k{y_i})$，所以我们可以提前与处理一下，加快速度。

我们可以枚举所有数，第$i$数都加上$x_i\times(y_i \times (k - 2) + \sum\limits_{i=1}^k{y_i})$即可，最后全部加上模上$10007$即可
可以依据代码来理解，我觉得挺有必要。

代码

#include <iostream>
using namespace std;
const int N = 100010,MOD = 10007;
int n,m;
int a[N],color[N];
int s[N][2],sum[N][2];
int main () {
	cin >> n >> m;
	for (int i = 1;i <= n;i++) cin >> a[i];
	for (int i = 1;i <= n;i++) {
		cin >> color[i];
		s[color[i]][i % 2]++;
		sum[color[i]][i % 2] = (sum[color[i]][i % 2] + i) % MOD;
	}
	int ans = 0;
	for (int i = 1;i <= n;i++) ans = (ans + a[i] * (i * (s[color[i]][i % 2] - 2) % MOD + sum[color[i]][i % 2]) % MOD) % MOD;
	cout << ans << endl;
	return 0;
}

标签：P2671,NOIP2015,求和,sum,纸带,times,int,cdots,color
From： https://www.cnblogs.com/incra/p/16936451.html

P2671 [NOIP2015 普及组] 求和