求和

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

1. $x,y,zx,y,z$是整数，且
2. $colo{r}_x=colo{r}_{z}color\_x=color\_z$

其中

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

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

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

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

其中由于每个格子的颜色与分数是分开给出的，所以还需要定义一个结构体与该结构体的数组，来存每个格子的：下标$idxidx$,颜色$colorcolor$，与分数$pointpoint$

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\le n\le 100000,1\le m\le 100000,1\le colo{r}_i\le m,1\le numbe{r}_i\le 1000001\le n\le 100000,1\le m\le 100000,1\le color\_i\le m,1\le number\_i\le 100000$

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

我们可以发现

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

那么根据公式$sum=(a+b)(x+y)sum=(a+b)(x+y)$

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

$sum=(a+b)\ast (x+y)+(a+c)\ast (x+z)+(b+c)\ast (y+z)sum=(a+b)*(x+y)+(a+c)*(x+z)+(b+c)*(y+z)$

$=(ax+ay+bx+by)+(ax+az+cx+cz)+(by+bz+cy+cz)=(ax+ay+bx+by)+(ax+az+cx+cz)+(by+bz+cy+cz)$

$=a(x+y+z)+b(x+y+z)+c(x+y+z)+ax+by+cz=a(x+y+z)+b(x+y+z)+c(x+y+z)+ax+by+cz$

$=(a+b+c)(x+y+z)+ax+by+cz=(a+b+c)(x+y+z)+ax+by+cz$

以此类推 四个格子的

$sum=(a+b+c+d)(x+y+z+u)+2(ax+by+cz+du)sum=(a+b+c+d)(x+y+z+u)+2(ax+by+cz+du)$

规律就出来了

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

	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;
}