题3：求和
【题目描述】
一条狭长的纸带被均匀划分出了
n
n
n 个格子，格子编号从
1
1
1 到
n
n
n。每个格子上都染了一种颜色
c
o
l
o
r
i
color_i
colori （用
[
1
，
m
]
[1，m]
[1，m]当中的一个整数表示），并且写了一个数字
n
u
m
b
e
r
i
number_i
numberi。
定义一种特殊的三元组： ( x , y , z ) (x,y,z) (x,y,z)，其中 x ， y ， z x，y，z x，y，z 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：
- x y z xyz xyz 是整数, x < y < z ， y − x = z − y x<y<z，y−x=z−y x<y<z，y−x=z−y
-
c
o
l
o
r
x
=
c
o
l
o
r
z
color_x=color_z
colorx=colorz
满足上述条件的三元组的分数规定为 ( x + z ) × ( n u m b e r x + n u m b e r z ) (x+z)×(number_x+number_z) (x+z)×(numberx+numberz) 。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 10 , 007 10,007 10,007 所得的余数即可。
【输入】
第一行是用一个空格隔开的两个正整数 n n n 和 m ， n m，n m，n 表纸带上格子的个数， m m m 表纸带上颜色的种类数。
第二行有 n n n 用空格隔开的正整数，第 i i i 数字 n u m b e r number number 表纸带上编号为 i i i 格子上面写的数字。
第三行有 n n n 用空格隔开的正整数，第 i i i 数字 c o l o r color color 表纸带上编号为 i i i 格子染的颜色。
【输出】
共一行，一个整数，表示所求的纸带分数除以 10 , 007 10,007 10,007 所得的余数。
【输入样例1】
6 2
5 5 3 2 2 2
2 2 1 1 2 1
【输出样例1】
82
【输入样例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,3,5),(4,5,6) (1,3,5),(4,5,6)。
所以纸带的分数为 ( 1 + 5 ) × ( 5 + 2 ) + ( 4 + 6 ) × ( 2 + 2 ) = 42 + 40 = 82 (1+5)×(5+2)+(4+6)×(2+2)=42+40=82 (1+5)×(5+2)+(4+6)×(2+2)=42+40=82 。
【数据规模】
对于第 1 1 1 组至第 2 2 2 组数据， 1 ≤ n ≤ 100 , 1 ≤ m ≤ 5 1≤n≤100,1≤m≤5 1≤n≤100,1≤m≤5；
对于第 3 3 3组至第 4 4 4 组数据， 1 ≤ n ≤ 3000 , 1 ≤ m ≤ 100 1≤n≤3000,1≤m≤100 1≤n≤3000,1≤m≤100；
对于第 5 5 5 组至第 6 6 6 组数据， 1 ≤ n ≤ 100000 , 1 ≤ m ≤ 100000 1≤n≤100000,1≤m≤100000 1≤n≤100000,1≤m≤100000，且不存在出现次数超过 20 20 20 的颜色；
对于全部 10 10 10 组数据， 1 ≤ n ≤ 100000 , 1 ≤ m ≤ 100000 , 1 ≤ c o l o r i ≤ m ， 1 ≤ n u m b e r i ≤ 100000 1≤n≤100000,1≤m≤100000,1≤colori≤m，1≤numberi≤100000 1≤n≤100000,1≤m≤100000,1≤colori≤m，1≤numberi≤100000。
【代码如下】：
#include<bits/stdc++.h>
using namespace std;
//ifstream cin("sum.in");
//ofstream cout("sum.ans");
const int mn=100000;
const int mm=100000;
const int p=10007;
int n,m,ans;
int number[mn+1],colour[mn+1];
int s[2][mm+1][4];
void init(){
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> number[i];
}
for(int i=1;i<=n;i++){
cin >> colour[i];
}
}
void solve(){
for(int i=1;i<=n;i++){
int z=i%p,numz=number[i]%p,c=colour[i],t=i%2;
int count=s[t][c][0]%=p,x=s[t][c][1]%=p,
numx=s[t][c][2]%=p,x_numx=s[t][c][3]%=p;
ans=(ans+((count*z)%p*numz)%p)%p;
ans=(ans+x_numx)%p;
ans=(ans+x*numz)%p;
ans=(ans+z*numx)%p;
s[t][c][0]++;
s[t][c][1]+=z;
s[t][c][2]+=numz;
s[t][c][3]+=z*numz;
}
}
void output(){
cout << ans;
//fclose(stdin);
//fclose(stdout);
}
int main(){
init();
solve();
output();
return 0;
}