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