histcat

Problem#

[NOIP2015 Popular Group] Sum#

Problem Background#

NOIP2015 Popular Group T3

Problem Description#

A narrow strip of paper is evenly divided into $n$ squares, numbered from $1$ to $n$. Each square is dyed a color $color_i$ represented by an integer from $[1,m]$, and has a number $number_i$ written on it.

Define a special triplet: $(x,y,z)$, where $x,y,z$ all represent the square numbers on the paper strip, and this triplet must satisfy the following two conditions:

1. $xyz$ are integers, $x<y<z$, $y-x=z-y$
2. $color_x=color_z$

The score of a triplet that satisfies the above conditions is defined as $(x+z) \times (number_x+number_z)$. The total score of the entire paper strip is the sum of the scores of all triplets that meet the conditions. This score can be very large; you only need to output the remainder of the total score of the entire paper strip divided by $10,007$.

($n, m <= 100000$)

Solution#

At first glance, it is clear that the result has nothing to do with $y$; the only restriction on $y$ is that $x$ and $z$ must have the same parity.

Thus, we can conclude that to count the squares that enter the answer, they must have the same parity and color. We group the squares with the same parity and color.

We consider one of these groups and use the difference method to see how much contribution each new number adds to the answer.

It is easy to see from the chart:

For example, adding the fourth element of this group produces the following contribution, and then we can calculate using prefix sums.

Code#

#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 represents the quantity of color i, index j; sum i,j represents the sum of color i, index 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();//number——n 
	}

	for(int i = 1;i <= n;i++)
	{
		b[i] = read();//color——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;
}