传送门
解题思路
比较巧的一道题。
把(y−x=z−y)化简一下得(x+z=2y)，这要求x和z一定要同为奇数或偶数。
所以很明显我们首先要对他们分类：
- 按照奇数偶数点
- 按照颜色
这样就化成了若干个集合，而我们需要快速求出每个集合对答案的贡献。
把数学式子列一下：
[sum_{i=1}^{n}sum_{j=i+1}^{n}(d[i]+d[j]) imes(num[d[i]]+num[d[j]])
]
其中 (n) 为集合元素个数，(d) 中存的是集合中每个元素的编号，(num) 和题目中一致。
然后化简式子（去括号），得：
[sum_{i=1}^{n}sum_{j=i+1}^{n}(d[i] imes num[d[i]]+d[j] imes num[d[j]]+d[i] imes nun[d[j]]+num[d[i]] imes d[j])
]
在这个式子上做文章就很简单了。
对于每个 (i)，对答案的贡献为 ((n-1) imes d[i] imes num[i]+d[i] imes(b[n]-b[i])+num[d[i]] imes(a[n]-a[i]))
其中 (a) 为 (d[i]) 的前缀和，(b) 为 (num) 的前缀和。
AC代码
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=1e5+5;
const int mod=10007;
int n,m,color[maxn];
long long a[maxn],b[maxn],num[maxn],d[maxn];
long long ans1,ans2;
vector<int> v[maxn];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>num[i];
for(int i=1;i<=n;i++) cin>>color[i];
for(int i=1;i<=n;i+=2){
v[color[i]].push_back(i);
}
for(int i=1;i<=m;i++){
if(v[i].size()>1){
int n=v[i].size();
for(int j=1;j<=n;j++){
d[j]=v[i][j-1];
a[j]=a[j-1]+d[j];
b[j]=b[j-1]+num[d[j]];
}
for(int j=1;j<=n;j++){
ans1=(ans1+d[j]*(b[n]-b[j])%mod+num[d[j]]*(a[n]-a[j])%mod)%mod;
ans1=(ans1+(n-1)*d[j]*num[d[j]]%mod)%mod;
}
}
v[i].clear();
}
for(int i=2;i<=n;i+=2){
v[color[i]].push_back(i);
}
for(int i=1;i<=m;i++){
if(v[i].size()>1){
int n=v[i].size();
for(int j=1;j<=n;j++){
d[j]=v[i][j-1];
a[j]=a[j-1]+d[j];
b[j]=b[j-1]+num[d[j]];
}
for(int j=1;j<=n;j++){
ans2=(ans2+d[j]*(b[n]-b[j])%mod+num[d[j]]*(a[n]-a[j])%mod)%mod;
ans2=(ans2+(n-1)*d[j]*num[d[j]]%mod)%mod;
}
}
v[i].clear();
}
cout<<(ans1+ans2)%mod;
return 0;
}
//NOIP2015普及组 t3