Archie

这是个什么东西呢

一看数据范围，肯定$o(n)$，带个$log$都不太肯能，再一看体面，y似乎没大有用

移项，发现$x+y=2z$这是啥意思呢，就是说，x+y需要是偶数，x，y奇偶性相同，颜色相同，那么我们何不把这些东西扔到一块去

然后，每与每一对数推式子，发现对于有k个数的堆，他的贡献是$sum_{i=1}^k({inumber_i(k-1)+i*(sum_{i-1}^knumber_i-number_i)})$

就可以$o(n)$了

记得多mod

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn=1e6+5;
int sum[maxn][2];
int num[maxn];
int col[maxn];
int cnt[maxn][2];
int ans;
const int mod=10007;
int n,m;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&num[i]);
        num[i]%=mod;
    }
    for(int i=1;i<=n;++i){
        scanf("%lld",&col[i]);
        sum[col[i]][i%2]+=num[i]%mod;
        sum[col[i]][i%2]%=mod;
        cnt[col[i]][i%2]+=1;
        cnt[col[i]][i%2]%=mod;
    }
    for(int i=1;i<=n;++i){
        if(cnt[col[i]][i%2]>1){
        ans+=(i%mod*num[i]%mod*((cnt[col[i]][i%2]-1)%mod)+i%mod*((sum[col[i]][i%2]-num[i])%mod)%mod)%mod;
        ans%=mod;
        }
    }
    cout<<ans%mod;
    return 0;
}