注意：本题解及其时间相近的题解是 Yurchiu 最早的题解。本题解是 Yurchiu 写的第一个题解。其中语言多不够严谨准确，排版不合规，可能甚至有错误，请 dalao 轻喷。
因为这个是第一篇题解，为了纪念，不改排版了。

题干

我们先看题。

题目描述：

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

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

1. $x,y,z$ 是整数,且 $x<y<z,y-x=z-y$
2. $colorx=colorz$

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

输入格式：

第一行是用一个空格隔开的两个正整数 n 和 m，n 表纸带上格子的个数，m 表纸带上颜色的种类数。
第二行有 n 个用空格隔开的正整数，第 i 个数字number表纸带上编号为i格子上面写的数字。
第三行有 n 个用空格隔开的正整数，第 i 个数字color表纸带上编号为i格子染的颜色。

输出格式：

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

数据范围：

对于第 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$

Solution

此题是个膜你模拟题

先说一下代码中变量的含义：

1.m表纸带上格子的个数
2. $p=10007$ ，膜模数
3.n表颜色种类

我们可以先定义个结构体，存编号，颜色，数字

struct node
{
	int hao;//编号
	int col;//颜色
	int num;//数字
}paper[100000+10];

读入数据

cin>>m>>n;
for(int i=1;i<=m;i++)
{
	cin>>paper[i].num;
	paper[i].hao=i;
}
for(int i=1;i<=m;i++)
{
	cin>>paper[i].col;
}

再1个for循环(i)枚举x

根据条件“ $y-x=z-y$ ”

说明从x到y与从y到z的距离相等

所以再一层for循环(j)枚举从x到y的距离(从y到z的距离),若 $i+j+j+2>m$ , $break;$

再按 $(x+z) \times (number_x+number_z)$ 计算即可

for(int i=1;i<=m-2;i++)
{
	for(int j=0;;j++)
	{
		if((i+j+j+2)>m)
		{
			break;
		}
		if(paper[i].col!=paper[i+j+j+2].col)
		{
			continue;
		}
		answer=(answer+ans(paper[i],paper[i+j+j+2]))%p;
	}
}
cout<<answer;

这是 ans 函数（有点鬼畜，勿喷）。

int ans(node x,node z)
{
	int q=x.hao%p;
	int w=z.hao%p;
	int e=x.num%p;
	int r=z.num%p;
	int t=(q+w)%p;
	int y=(e+r)%p;
	int u=(t \times y)%p;
	return u;
}

啥? T飞了?

Solution 100pts

正解如下(语文实在不好):

1

假设纸带只有一种颜色

开始你只有一个格子，编号 $a_1$ ,数字 $n_1$ ;

这样根据运算规则，不会产生运算。

再加一个格子，编号 $a_2$ ,数字 $n_2$ ，不一定相邻，

题干有 $y-x=z-y$ ，得

$2y=x+z$

即当 $a_1+a_2$ 是偶数时，就能产生运算。

所以，当 $a_i$ $a_j$ 同为偶数或奇数时，才能产生运算。

2

运算规则是 $(x+z)×(number_x+number_z)$

即 $(a_i+a_j)×(n_i+n_j)$

朴素的运算代价是 $O(n^2)$

数据 $1<=m<=100000$ ,一定超时

优化：

原式可分为

$a_i \times n_i+a_i \times n_j+a_i \times n_i+a_j \times n_j$

即：

1. $a_i \times n_i$ ->A运算

2. $a_i \times n_j$ ->B运算

3. $a_j \times n_i$ ->C运算

4. $a_j \times n_j$ ->D运算

经分析，这些都可以做优化，这是突破口所在

那么可以做前缀和，只需维护3个变量，运算求解的时间复杂度即可降为 $O(n)$

class node
{
	public:
	int anx;//AD运算
	int ax;//B运算
	int nx;//C运算
	int cnt;
}c[100000+10][2];

其中c数组第一维表颜色

为什么c[100000+10][2]?

因为

$a_i$ $a_j$ 同为偶数或奇数两种情况

另外cnt表示一种颜色有了cnt个偶/奇数位置项

所以可以放心枚举而不超时

下面的代码是计算的代码。请自己加上取模运算。

for(int i=1;i<=n;++i)
{  
	int k=b[i];//颜色
	int j=i%2;//奇偶性
    if(c[k][j].cnt)//运算规则把积分结果积累到 ans 上 
    { 
 		ans+=c[k][j].anx+i*c[k][j].n+i*a[i]*c[k][j].cnt+a[i]*c[k][j].ax;
	   	c[k][j].anx=c[k][j].anx+i*a[i];//更新每一项位置*每一项的数值之和(anx) 
	   	c[k][j].nx=c[k][j].nx+a[i];//更新每一项的数值之和 (nx)
	   	c[k][j].ax=c[k][j].ax+i;//更新每一项的位置之和 (ax)
	   	c[k][j].cnt=c[k][j].cnt+1;// c[k][0].cnt 项表示此时第k种颜色有了cnt个偶数位置项  
	}
	else// 出现的第一个数用来初始化 c 
	{
	   	c[k][j].anx=c[k][j].anx+i*a[i];
	   	c[k][j].nx=c[k][j].nx+a[i];
	   	c[k][j].ax=c[k][j].ax+i;
	   	c[k][j].cnt=c[k][j].cnt+1;	 
	}
}