【题解】Luogu P2671 【求和】

因为人傻常数大写了一天的题目。

原题传送门

题目意思另一种表达：

定义特殊二元组\((x,z)\)。

1.\(x<z\)。

2.\(x\)与\(z\)要么都为奇数要么都为偶数。

（即\(x \ mod \ 2 = z \ mod \ 2\)）

3.\(c_x=c_z\)

4.该二元组的分数为\((x+z)\times(a_x+a_z)\)

给定所有\(c_i\)与\(a_i\)，求满足条件的二元组的分数和。

以上的\(x\)，\(z\)在下文表述为\(id_x\)，\(id_y\)。（\(y\)代替\(z\)）

80分做法

以\(v[i][0]\)来存储颜色为\(i\)的所有偶数下标的\(num_i\)与\(a_i\)。\(v[i][1]\)来存储奇数下标。

有以下结论：

对于所有的\((x,y)\)，\(v[i][j][x]\)与\(v[i][j][y]\)都两两为合法二元组。

然后枚举所有颜色\(i\)，接着枚举\(x\)，\(y\)暴力统计答案就可以了。

时间复杂度应该是\(O(n^2)\)，不知道为啥有\(80pts\)（

\(80pts:\)

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

#define MAXN (int)(1e5+233)

#define int long long

struct qwq

{

	int a,c,id;

}e[MAXN];

vector<qwq> v[MAXN][2];

#define mod (10007)

signed main()

{

	int n,m;

	scanf("%lld%lld",&n,&m);

	for (int i=1;i<=n;i++) scanf("%lld",&e[i].a);

	for (int i=1;i<=n;i++) scanf("%lld",&e[i].c),e[i].id=i;

	for (int i=1;i<=n;i++)

	{

		v[e[i].c][i%2].push_back(e[i]);

	}

	int ans=0;

	for (int i=1;i<=m;i++)

	{

		for (int j=0;j<v[i][0].size();j++)

		{

			for (int k=j+1;k<v[i][0].size();k++)

			{

				ans+=((v[i][0][j].id+v[i][0][k].id)*(v[i][0][j].a+v[i][0][k].a))%mod;

				ans%=mod;

			}

		}

		for (int j=0;j<v[i][1].size();j++)

		{

			for (int k=j+1;k<v[i][1].size();k++)

			{

				ans+=((v[i][1][j].id+v[i][1][k].id)*(v[i][1][j].a+v[i][1][k].a))%mod;

				ans%=mod;

			}

		}

	}

	printf("%lld\n",ans%mod);

	return 0;

}

100分做法

\(80\)分做法中提到的\(v[i][j][]\)这样的一个数组，我们简写为\(s[]\)，考虑每次往数组后面加一个数，这个数对答案的贡献。

拆式（题目中的贡献式）

\[(id_x+id_y)\times(a_x+a_y)
\]
\[(id_x \times a_x)+(id_x \times a_y)+(id_y \times a_x)+(id_y\times a_y)
\]

于是原式就拆为四个式子的和。

反思结论（\(x\)，\(y\)指在统计数组中的下标）

对于所有的\((x,y)\)，\(s[x]\)与\(s[y]\)都两两为合法二元组。

那么每在\(s[]\)末尾位置\(y\)多加入一个值，这个\(y\)就要与所有\(0 < x < y\)相匹配并累计贡献。（说简单点就和\(y\)之前的所有数匹配为合法二元组）

分别考虑拆式中四个式子

1.\((id_x \times a_x)\)

对于所有\(x\)，答案加上\(id_x \times a_x\)。用\(sumul\)数组记录\(\sum_{x=1}^{y-1}id_x \times a_x\)的和，累计进答案贡献。

2.\((id_x \times a_y)\)

\(sumid\)记录\(\sum_{x=1}^{y-1}{id_x}\)，答案贡献加上\(sumid \times a_y\)。

3.\((id_y \times a_x)\)

\(suma\)记录\(\sum_{x=1}^{y-1}{a_x}\)，答案贡献加上\(suma \times id_y\)

4.\((id_y \times a_y)\)

我们知道在末尾位置\(y\)加一个数就增加了\((y-1)\)个合法二元组。那么也就是会增加\((y-1)\)个\((id_y \times a_y)\)。用一个\(sum\)数组来记录末尾下标\(y\)。

5.总结贡献

\(ans+=(sumul+sumid \times a_y +suma \times id_y +sum \times (id_y \times a_y))\)

\(100pts:\)

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define int long long

#define MAXN (int)(1e5+233)

using namespace std;

int a[MAXN],c[MAXN],suma[MAXN][2],sumid[MAXN][2],sumul[MAXN][2],sum[MAXN][2];

struct qwq {

	int a,c,id;

}e[MAXN];

#define mod (10007)

signed main() {

	int n,m;

	scanf("%lld%lld",&n,&m);

	for (int i=1;i<=n;i++) scanf("%lld",&e[i].a);

	for (int i=1;i<=n;i++) scanf("%lld",&e[i].c),e[i].id=i;

	int ans=0;

	for (int i=1;i<=n;i++)

	{

		ans+=sumul[e[i].c][i&1]+i*e[i].a*sum[e[i].c][i&1]+sumid[e[i].c][i&1]*e[i].a+suma[e[i].c][i&1]*i;

		sumul[e[i].c][i&1]+=i*e[i].a;//处理a_i*i前缀和

		suma[e[i].c][i&1]+=e[i].a;//处理a_i前缀和

		sumid[e[i].c][i&1]+=i;//处理number_i前缀和

		sum[e[i].c][i&1]++;//处理（不存在的）数组末尾下标

		ans%=mod;

	}

   printf("%lld\n",ans);

	return 0;

}