NOIP2015普及T3 求和

题面：https://www.luogu.org/problem/P2671

条件1：color_x=color_z

条件2：$y-x=z-y\Rightarrow x+z=2y$

对于颜色i，预处理出v[i]表示颜色为i的所有格子

则v[i]中的任意两个格子，满足条件1

x，y，z为整数 $\Rightarrow$ x，z奇偶性相同

对于v[i]，处理出v1，v2表示编号为奇数/偶数的格子

对于v1，v2中的任意两个格子，满足条件1和条件2

计算贡献：$(x+z)(number_x+number_z)$

若直接枚举两个格子，复杂度为$O(n^2)$，无法通过

拆开式子得：$x*number_x+z*number_z+x*number_z+z*number_x$

令 $sum1=sum(v1),sum2=sum(v2)$

v1中与x有关的所有贡献为 $x*number_x*(v1.size()-1)+x*(sum1-number_x)+number_x*(\sum_{i=1}^{v1.size()-1}v1[i])$，其中v[i]是格子编号

第三项的贡献可以归于v1中其他格子的第二项贡献

因此贡献计算方法优化为 $\sum_{i=0}^{v1.size()-1}(v1[i]*number[v1[i]]*(v1.size()-1)+v1[i]*(sum1-number[v1[i]]))$

总复杂度为$O(n)$

代码：

#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define rint register int
#define It set<node>::iterator
#define endl '\n'
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
const int mod=10007;

struct Node{
    int number,color,value;
}node[maxn];

int n,m,ans;
vector<int> v[maxn];

inline void calc(vector<int> arr){
    vector<int> v1,v2;
    int sum1=0,sum2=0;
    for(rint i=0;i<arr.size();++i)
        if(arr[i]%2==0) v1.pb(arr[i]),sum1+=node[arr[i]].number,sum1%=mod;
        else v2.pb(arr[i]),sum2+=node[arr[i]].number,sum2%=mod;
    for(rint i=0;i<v1.size();++i){
        ans+=(v1.size()-1)*node[v1[i]].value;
        ans=(ans+mod)%mod;
        ans+=v1[i]*(sum1-node[v1[i]].number);
        ans=(ans+mod)%mod;
    }
    for(rint i=0;i<v2.size();++i){
        ans+=(v2.size()-1)*node[v2[i]].value;
        ans=(ans+mod)%mod;
        ans+=v2[i]*(sum2-node[v2[i]].number);
        ans=(ans+mod)%mod;
    }
}

signed main(){
    fastio;
    cin>>n>>m;
    for(rint i=1;i<=n;++i) cin>>node[i].number;
    for(rint i=1;i<=n;++i) cin>>node[i].color;
    for(rint i=1;i<=n;++i) node[i].value=i*node[i].number%mod;
    for(rint i=1;i<=n;++i) v[node[i].color].pb(i);
    for(rint i=1;i<=m;++i) calc(v[i]);
    cout<<(ans+mod)%mod<<endl;
    return 0;
}