中级天翼
1426 求和
经验值：2000 时间限制：1000毫秒
全国 2015 NOIP 普及组试题
不许抄袭，一旦发现，直接清空经验！
题目描述 Description
一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色color_i用[1，m]当中的一个整数表示），并且写了一个数字number_i。
定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元
组要求满足以下两个条件：
1.xyz是整数,x<y<z，y-x=z-y
2.colorx=colorz
满足上述条件的三元组的分数规定为(x+z)*(number_x+number_z)。整个纸带的分数
规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。
输入描述 Input Description
第一行是用一个空格隔开的两个正整数n和m，n表纸带上格子的个数，m表纸带上颜色的种类数。
第二行有n用空格隔开的正整数，第i数字number表纸带上编号为i格子上面写的数字。
第三行有n用空格隔开的正整数，第i数字color表纸带上编号为i格子染的颜色。
输出描述 Output Description
共一行，一个整数，表示所求的纸带分数除以10,007所得的余数。
样例输入 Sample Input
输入样例#1： 6 2 5 5 3 2 2 2 2 2 1 1 2 1 输入样例#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
样例输出 Sample Output
输出样例#1： 82 输出样例#2： 1388
数据范围及提示 Data Size & Hint
【输入输出样例 1 说明】
纸带如题目描述中的图所示。
所有满足条件的三元组为： (1, 3, 5), (4, 5, 6)。
所以纸带的分数为(1 + 5)*(5 + 2) + (4 + 6)*(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
注意，只要思路
注意，只要思路
注意，只要思路
武建豪在2021-08-07 08:12:37追加了内容
注意，再发代码的举报
我要思路啊啊啊啊啊啊
初级天翼
思路的话
这题一看就是数学问题。求彩带分数和的式子需要运用一点数学思维化简（化简成计算机能快速算出的）
比如说：
设同奇偶且同一种颜色的每个格子中的格子编号为a,b,c,d,....，分数为aa,bb,cc,dd,...
由于这些格子中要两两计算分数并相加，因此我们来看看能不能把这个数学计算化简下
有两个格子满足条件时的分数和是
(a+b)*(aa+bb)
（=0*(a*aa+b*bb)+(a+b)*(aa+bb)）
有三个格子满足条件时的分数和是
(a+b)*(aa+bb)+(a+c)*(aa+cc)+(b+c)*(bb+cc)
=a*aa+b*bb+c*cc+a*(aa+bb+cc)+b*(aa+bb+cc)+c*(aa+bb+cc) 【把上面那个式子的因式全都分解开，再合并一下，就能合成这样，没难度】
=a*aa+b*bb+c*cc+(a+b+c)*(aa+bb+cc)
（=1*(a*aa+b*bb+c*cc)+(a+b+c)*(aa+bb+cc)）
有四个格子满足条件时的分数和是
(a+b)*(aa+bb)+(a+c)*(aa+cc)+(a+d)*(aa+dd)+(b+c)*(bb+cc)+(b+d)*(bb+dd)+(c+d)*(cc+dd)
=2*(a*aa+b*bb+c*cc+d*dd)+a*(aa+bb+cc+dd)+b*(aa+bb+cc+dd)+c*(aa+bb+cc+dd)+d*(aa+bb+cc+dd)
=2*(a*aa+b*bb+c*cc+d*dd)+(a+b+c+d)*(aa+bb+cc+dd)
设ci为格子颜色，j为0时表示这些三元组的x,z均为偶数，j为1时则均为奇数。
设之前出现过的与之同奇偶p同颜色ci的格子数设为cnt[ci][p]，
格子序号和color[ci][0][p]，格子数字和color[ci][1][p]，格子序号与数字之积之和为color[ci][2][p]。
当所有格子（所有颜色的格子）满足条件时，分数和为
for(i=1;i<=m;i++)
for(j=0;j<=1;j++){
sum+=color[i][0][j]*color[i][1][j]+((cnt[i][j]-2)*color[i][2][j]);
sum%=10007;
}
这回行了吧
缔造者之神
这是我们班的作业题吧？
初级天翼
核心：
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
for(int i=1;i<=n;i++)
{
scanf("%lld",&cl);
if(i%2==1)
{
ans=(ans+sum1[0][cl]%10007+i*sum1[1][cl]%10007+num[i]*sum1[2][cl]%10007+cont[0][cl]*i*num[i]%10007)%10007;
sum1[0][cl]=(sum1[0][cl]+num[i]*i)%10007;
sum1[1][cl]=(sum1[1][cl]+num[i])%10007;
sum1[2][cl]=(sum1[2][cl]+i)%10007;
cont[0][cl]++;
}
else
{
ans=(ans+sum2[0][cl]%10007+i*sum2[1][cl]%10007+num[i]*sum2[2][cl]%10007+cont[1][cl]*i*num[i]%10007)%10007;
sum2[0][cl]=(sum2[0][cl]+num[i]*i)%10007;
sum2[1][cl]=(sum2[1][cl]+num[i])%10007;
sum2[2][cl]=(sum2[2][cl]+i)%10007;
cont[1][cl]++;
}
}
输出%lld,ans%10007
缔造者之神
