题解 P2671 【求和】
pengyule
·
·
题解
概述
一道数学题，用暴力做复杂度 O(n^2)，但是可以发现存在一些性质，从而把复杂度降到 O(n)。
分析
看看题目怎么说：
-
x<y<z$，且 $y-x=z-y
-
color_x=color_y
对于第二个条件，很好想，我们可以把相同颜色的元素归到一组，然后在每一个“组”中寻找“三元组”。
对于第一个条件，乍一看就是说要找到三个等距离的元素，其实我们发现，在满足第二个条件的情况下，其实就是要找到 x,z 奇偶性相同的二元组 (x,z)。
我们于是想到，对于每一个相同颜色的“组”中，再把它分成下标为奇数和下标为偶数的两个组，对于每一个组，去计算所有 (x,z) 的分数。
怎么计算分数呢？一个有 n 个元素的颜色相同、下标奇偶相同的“组”，它的总分数等于
\sum_{i=1}^n x_i\times (y_i\times(n-2)+\sum_{j=1}^n y_j)
我们看一看式子的推导过程。
记答案为 ans，y_i 为组中第 i 个数的下标，x_i 为 number\_y_i。
ans=(x_1+x_2)(y_1+y_2)+(x_1+x_3)(y_1+y_3)+\cdots+(x_1+x_n)(y_1+y_n)
+(x_2+x_3)(y_2+y_3)+\cdots+(x_2+x_n)(y_2+y_n)
\cdots
+(x_{n-1}+x_{n})(y_{n-1}+y_n)
发现第 j 排都有 x_j，可以把所有的 x_j\times x_i^{(i=[1,n],i\neq j)} 提取出来，剩下的就是一些乱七八糟的东西，总之你最后就会发现，你得到了
ans=x_1(y_1+y_2+y_1+y_3+\cdots+y_1+y_n)
+x_2(y_2+y_1+y_2+y_3+\cdots+y_2+y_n)
\cdots
+x_{n-1}(y_{n-1}+y_1+\cdots+y_{n-1}+y_{n-2}+y_{n-1}+y_{n})
我们发现其实第 i 排就是 x_i 乘上 (n-1) 个 y_i 加上 j=[1,n]\&\&j\neq i 的 y_j 的和。其实我们把 (n-1) 个 y_i 中拎一个出来丢到后面的 y_{j=1\sim n,\neq i} 里这排的答案就变成了
x_i\times(y_i\times(n-2)+\sum_{j=1}^{n}y_j)
于是最终的答案就得到了！
所以核心代码就是
```
for(int i=1;i<=n;i++) ans+=x[i]*(sum+y[i]*(n-2));
```
# 代码
```
#include <bits/stdc++.h>
using namespace std;
#define int long long //要开long long
const int N=1e5+5;
struct node {
int num,col,idx;//idx:原来的下标
}t[N];
bool cmp(node a,node b){
return a.col<b.col;//相同的颜色放到一起方便处理
}
int x[N],y[N],ans;
int solve(int l,int r){//[l,r]是相同的颜色
int n=0;
int sum=0,ans=0;
for(int i=l;i<=r;i++) if(t[i].idx&1)x[++n]=t[i].num,y[n]=t[i].idx;//如果下标是奇数那么把他存到x,y里当成一组
for(int i=1;i<=n;i++) sum+=y[i];//预处理sum
for(int i=1;i<=n;i++) ans=(ans+x[i]*(sum+y[i]*(n-2)))%10007;//这里就要取模小心到时候答案不对
n=0,sum=0;
for(int i=l;i<=r;i++) if((t[i].idx&1)==0)x[++n]=t[i].num,y[n]=t[i].idx;//如果下标是偶数那么把他存到x,y里当成一组
for(int i=1;i<=n;i++) sum+=y[i];
for(int i=1;i<=n;i++) ans=(ans+x[i]*(sum+y[i]*(n-2)))%10007;
return ans;
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>t[i].num,t[i].idx=i;
for(int i=1;i<=n;i++) cin>>t[i].col;
sort(t+1,t+n+1,cmp);
int las=1;
for(int i=2;i<=n+1;i++)
if(t[i].col!=t[i-1].col){
ans=(ans+solve(las,i-1))%10007;
las=i;
}
cout<<ans%10007<<endl;
return 0;
}
```