求和

[NOIP2015]求和

https://ac.nowcoder.com/acm/problem/16492

首先关注三元组的两个条件

$x, y, z$ 是整数，且 $x < y < z, y - x = z - y$
$c o l o r_{x} = c o l o r_{z}$

其中

条件 $1$ 要求三元组的下标为等差数列，即 $x, z$ 必须存在中点，即 $(z-x)\%2=0$
条件 $2$ 要求两端的格子颜色相同

两个条件其实都只对两端的格子进行要求，而不管中间的格子是什么

所以总结起来，就是要我们寻找两个下标奇偶相同，颜色相同的格子

那么我们可以对所有格子按奇偶与颜色进行分类，而我采用的是用vector来存

其中由于每个格子的颜色与分数是分开给出的，所以还需要定义一个结构体与该结构体的数组，来存每个格子的：下标 $i d x$ ,颜色 $c o l o r$ ，与分数 $p o i n t$

struct node
{
	int idx, color, point;
};

constexpr int N = 1e5 + 10, mod = 10007;
vector<node> v[N][2];
node tem[N];

其中vector数组的两维分别表示，颜色与奇偶

然后读取数据

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		tem[i].idx = i;
		cin >> tem[i].point;
	}
	for (int i = 1; i <= n; i++)
		cin >> tem[i].color;

然后分类存好

	for (int i = 1; i <= n; i++)
	{
		int c = tem[i].color, idx = tem[i].idx;
		v[c][idx & 1].push_back(tem[i]);
	}

然后就是对每一类的格子两两求公式的和

但是由于题目数据范围最大为为

$1 \leq n \leq 100000, 1 \leq m \leq 100000, 1 \leq c o l o r_{i} \leq m, 1 \leq n u m b e r_{i} \leq 100000 1≤n≤100000,1≤m≤100000,1≤color_i≤m,1≤number_i≤100000$

所以我们肯定不能对每一类两重循环，而只能采用时间复杂度为 $O (n)$ 或者 $O (n l o n g n)$ 的算法

我们可以发现

假设有一类只有两个格子，下标为 $a, b$ ，分数为 $x, y$

那么根据公式 $s u m = (a + b) (x + y)$

而另一类有三个格子，下标为 $a, b, c$ ，分数为 $x, y, z$

$s u m = (a + b) * (x + y) + (a + c) * (x + z) + (b + c) * (y + z)$

$= (a x + a y + b x + b y) + (a x + a z + c x + c z) + (b y + b z + c y + c z)$

$= a (x + y + z) + b (x + y + z) + c (x + y + z) + a x + b y + c z$

$= (a + b + c) (x + y + z) + a x + b y + c z$

以此类推四个格子的

$s u m = (a + b + c + d) (x + y + z + u) + 2 (a x + b y + c z + d u)$

规律就出来了

所以对于每一类只需要遍历一遍，求出相应括号中的值，再按公式就可以求出该类的总和了，同时将所有类的总和相加，就得出结果了

	long long res = 0;
	for (int i = 1; i <= m; i++)
		for (int j = 0; j <= 1; j++)
		{
			auto& t = v[i][j];
			long long sum1 = 0, sum2 = 0, sum3 = 0;
			for (int k = 0; k < t.size() & t.size() >= 2; k++)
			{
				sum1 += t[k].point;
				sum2 += t[k].idx;
				sum3 = (sum3 + t[k].point * t[k].idx) % mod;
			}
			res = (res + sum1 % mod * (sum2 % mod) + sum3 * (t.size() - 2)) % mod;				
		}
	cout << res;

最后贴出完整代码

#include<iostream>
#include<vector>

using namespace std;

struct node
{
	int idx, point, color;
};

constexpr int N = 1e5 + 10, mod = 10007;
vector<node> v[N][2];
node tem[N];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		tem[i].idx = i;
		cin >> tem[i].point;
	}
	for (int i = 1; i <= n; i++)
		cin >> tem[i].color;
	for (int i = 1; i <= n; i++)
	{
		int c = tem[i].color, idx = tem[i].idx;
		v[c][idx & 1].push_back(tem[i]);
	}
	long long res = 0;
	for (int i = 1; i <= m; i++)
		for (int j = 0; j <= 1; j++)
		{
			auto& t = v[i][j];
			long long sum1 = 0, sum2 = 0, sum3 = 0;
			for (int k = 0; k < t.size() & t.size() >= 2; k++)
			{
				sum1 += t[k].point;
				sum2 += t[k].idx;
				sum3 = (sum3 + t[k].point * t[k].idx) % mod;
			}
			res = (res + sum1 % mod * (sum2 % mod) + sum3 * (t.size() - 2)) % mod;				
		}
	cout << res;
}