【题解】求和
题目背景
NOIP2015 普及组 T3
题目描述
一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色
用[1,m]当中的一个整数表示），并且写了一个数字
定义一种特殊的三元组：(x,y,z)，其中x,y,z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：
- xyz是整数,x<y<z,y-x=z-y
- colorx=colorz
满足上述条件的三元组的分数规定为
。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。
输入格式
第一行是用一个空格隔开的两个正整数n和m,n表纸带上格子的个数，m表纸带上颜色的种类数。
第二行有n用空格隔开的正整数，第i数字number表纸带上编号为i格子上面写的数字。
第三行有n用空格隔开的正整数，第i数字color表纸带上编号为i格子染的颜色。
输出格式
一个整数，表示所求的纸带分数除以10007所得的余数。
输入输出样例
输入 #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+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，且不存在出现次数超过2020的颜色；
对 于 全 部 10 组 数 据 ， 1≤n≤100000,1≤m≤100000,1≤colori≤m,
题目分析
题目要求的满足条件的三元组的分数和。
三元组需要满足的条件是：
- xyz是整数,x<y<z,y-x=z-y
- colorx=colorz
那么我们只需要统计每个颜色对应奇偶位置的信息即可。
我们再寻找下计算过程中的相关规律，设序列
为同颜色，位置奇偶性相同的五个元素，我们来算一下相关分数。
再看加起来的总和：
此时可以发现每个元素对总和做出的贡献。
那么可以提前预处理以下同颜色同奇偶位置的元素个数与元素分数和。
定义cnt[x][2] ，第一个下标表示颜色，第二个表示位置奇偶性。定义sum[x][2] ,第一个下标表示颜色，第二个表示位置奇偶性。
预处理部分
for(int i:1~n){
cin>>color[i];
cnt[color[i]][i%2]++;//统计个数
sum[color[i]][i%2]+=score[i];//累加分数
}代码实现
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int M=1e4+7;
ll color[N],num[N];
ll cnt[N][2];
ll sum[N][2];
//cnt[x][0] 颜色x，位置为偶数的个数 cnt[x][1] 颜色x，位置为奇数的个数
//sum[x][0] 颜色x，位置为偶数的总分 sum[x][1] 颜色x，位置为奇数的总分
//
int n,m;
int main(){
ll ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&num[i]);
}
for(int i=1;i<=n;i++){
scanf("%lld",&color[i]);
cnt[color[i]][i%2]++;
sum[color[i]][i%2]=(sum[color[i]][i%2]+num[i])%M;
}
for(int i=1;i<=n;i++){
int c=color[i];
ans+=i*((cnt[c][i%2]-1)*num[i]%M+(sum[c][i%2]%M-num[i]%M+M)%M)%M;
ans%=M;
}
printf("%lld",ans);
return 0;
}Q.E.D.