P2671 求和

题目背景

NOIP2015 普及组 T3

题目描述

一条狭长的纸带被均匀划分出了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) \times (number_x+number_z)$。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以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) \times (5 + 2) + (4 + 6) \times (2 + 2) = 42 + 40 = 82$。

对于第 1 组至第 2 组数据， $1 \le n \le 100, 1 \le m \le 5$；

对于第3 组至第 4 组数据， $1 \le n \le 3000, 1 \le m \le 100$；

对于第 5 组至第6组数据， $1 \le n \le 100000, 1 \le m \le 100000$，且不存在出现次数超过2020的颜色；

对 于 全 部 10 组 数 据 ， $1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ color_i ≤ m,1≤number_i≤100000$

题目分析

题目要求的满足条件的三元组的分数和。

三元组需要满足的条件是：

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

暴力方式就是三重循环，每个循环对应一个元素，时间复杂度$O(n^3)$ ，很明显会超时。稍稍优化下，将式子$y-x=z-y$ 变形为$2y=z+x$也就是$y=\frac{z+x}{2}$ ，此时只需要遍历两个元素z和x就好，时间复杂度降为$O(n^2)$ 。前四组测试点可以过了，但是后面的依然会超时。

此时，需要继续优化。观察式子$y=\frac{z+x}{2}$ ，三个元素都是整数，若该式子成立，我们只要保证$z+x$为偶数就好，此时y就不用管了，它是必定存在的。那么也就意味着，只需保证z、x奇偶性相同即可使它们的和为偶数。再保证对应位置的颜色相同即可。

那么我们只需要统计每个颜色对应奇偶位置的信息即可。

我们再寻找下计算过程中的相关规律，设序列$a=\{a1,a2,a3,a4,a5\}$ 为同颜色，位置奇偶性相同的五个元素，我们来算一下相关分数。

计算分数的表达式为：$(x+z) \times (number_x+number_z)$ 分解一下变为$x\times number_x+x\times number_z+z\times number_x+z\times number_z$

x\z	1	2	3	4	5
1		$a_1+a_2+2\times a_1+\\2\times a_2$	$a_1+ a_3+ \\3\times a_1+3\times a_3$	$a_1+a_4+\\ 4\times a_1+4\times a_4$	$a_1+a_5+\\ 5\times a_1+5\times a_5$
2			$2\times a_2+2\times a_3+\\3\times a_2+3\times a_3$	$2\times a_2+2\times a_4+\\ 4\times a_2+4\times a_4$	$2\times a_2+2\times a_5+\\ 5\times a_2+5\times a_5$
3				$3\times a_3+3\times a_4+\\ 4\times a_3+4\times a_4$	$3\times a_3+3\times a_5+\\ 5\times a_3+5\times a_5$
4					$4\times a_4+4\times a_5+\\ 5\times a_4+5\times a_5$
5

再看加起来的总和：

系数
1	$4\times a_1+(a_2+a_3+a_4+a_5)$=$4\times a_1+(a_1+a_2+a_3+a_4+a_5)-a_1$
2	$4\times a_2+(2\times a_1+2\times a_3+2\times a_4+2\times a_5)$=$4\times a_2+(2\times a_1+2\times a_2+2\times a_3+2\times a_4+2\times a_5)-2\times a_2$
3	$4\times a_3+(3\times a_1+3\times a_2+3\times a_4+3\times a_5)$=$4\times a_3+(3\times a_1+3\times a_2+3\times a_3+3\times a_4+3\times a_5)-3\times a_3$
4	$4\times a_4+(4\times a_1+4\times a_2+4\times a_3+4\times a_5)$=$4\times a_4+(4\times a_1+4\times a_2+4\times a_3+4\times a_4+4\times a_5)-4\times a_4$
i	$(n-1)\times i\times a_i+i\times(sum-a_i)$

此时可以发现每个元素对总和做出的贡献。

那么可以提前预处理以下同颜色同奇偶位置的元素个数与元素分数和。

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