P2671 [NOIP2015 普及组] 求和

题目#

[NOIP2015 普及组] 求和#

题目背景#

NOIP2015 普及组 T3

题目描述#

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

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

$xyz$ 是整数，$x<y<z,y-x=z-y$
$colorx=colorz$

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

（$n, m <= 100000$）

题解#

首先一眼看出结果和 y 没有半毛钱关系，y 唯一限制的地方是 x，z 的奇偶性必须相同

所以我们可以得出要想统计进入答案的格子之间必须同奇偶且同颜色，我们把有相同奇偶性和颜色的格子分成一组。

我们考虑其中的一组，考虑差值法，看一下每加入一个新的数会对答案产生多少的贡献

画出图表容易知道

number\ 编号	1	2	3	4
n_1	1			1
n_2		1		1
n_3			1	1
n_4	1	1	1	1+1+1

例如加入了该组的第四个，产生的贡献如下
然后前缀和统计，计算即可

代码#

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, m;

const int N = 100100;
const int mod = 10007;

int counta[N][2], sum_n[N][2], sum_f[N][2], sum_fn[N][2];//count i,j 表示颜色为i，编号为j的数量，sum i,j 表示颜色为i，编号为j的 
int a[N], b[N];

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

signed main()
{
	n = read(), m = read();
	long long ans = 0;
	for(int i = 1;i <= n;i++)
	{
		a[i] = read();//数字——n 
	}

	for(int i = 1;i <= n;i++)
	{
		b[i] = read();//颜色——b 
	}

	for(int i = 1;i <= n;i++)
	{
		ans = (ans + sum_fn[b[i]][i % 2]) % mod;
		counta[b[i]][i % 2] ++;
		sum_f[b[i]][i % 2] = (sum_f[b[i]][i % 2] + i) % mod;
		sum_n[b[i]][i % 2] = (sum_n[b[i]][i % 2] + a[i]) % mod;
		sum_fn[b[i]][i % 2] = (sum_fn[b[i]][i % 2] + (i * a[i]) % mod) % mod;
		ans = (ans + (i * sum_n[b[i]][i % 2]) % mod) % mod;
		ans = (ans + (a[i] * sum_f[b[i]][i % 2]) % mod) % mod;
		ans = (ans + ((  (counta[b[i]][i % 2] - 3) * i * a[i]) % mod + mod ) % mod) % mod;
	}
	printf("%lld", ((ans % mod) + mod) % mod);
	return 0;
}