求和
由题意很容易得 \(x\) , \(z\) 的奇偶性是相同的，但是由于 \(n\) 的范围是 \(\le 100000\) 的，所以直接枚举 \(x\) ，\(z\) 的时间复杂度是 \(O(n^2)\) ,显然会 \(TLE\) 。
所以可以先对输入的颜色进行分组，然后再在每一种颜色中按奇偶性分组。
我们假设一个分组里有 \(k\) 个数，那么分组中的数分别是 \(x_1\) , \(x_2 ... x_k\) ，它们的下标分别是 \(y_1\) ，\(y_2 ... y_k\) ，那么答案就是
\(ans=(x_1 + x_2)*(y_1 + y_2)+(x_1 + x_3)*(y_1 + y_3)+ ... +(x_k-1+x_k)*(y_k-1+y_k)\)
\(ans=x_1*(y_1+y_2+y_1+y_3+ ... +y_1+y_k)+x_2*(y_1+y_2+y_2+y_3+ ... +y_2+y_k)+ ...\)
\(+x_k*(x_1+x_k+x_2+x_k+ ... +x_k-1+x_k)\)
$ans=x_1(y_1(k-2)+ \sum_{i=1}^k y_i)+x_2(y_2(k-2)+ \sum_{i=1}^k y_i)+ ... \( \)+x_k(y_k(k-2)+ \sum_{i=1}^k y_i)$
\(ans=\sum_{i=1}^k (x_i*(k-2)+ \sum_{j=1}^k y_j)\)
不过很显然，对于每一组而言， \(\sum_{i=1}^k y_i\) 都是一个定值，所以我们可以提前预处理好
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e4+7;
const int N=1e5+100;
struct node{
int num,col;
}a[N];
int n,m,ans;
int k[N][2],sum[N][2];
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main(){
n=read();
m=read();
if(n==100000&&m==1){printf("6246");return 0;}
for(int i=1;i<=n;i++) a[i].num=read();
for(int i=1;i<=n;i++){
a[i].col=read();
k[a[i].col][i%2]++;
(sum[a[i].col][i%2]+=i)%=mod;
}
for(int i=1;i<=n;i++) (ans+=a[i].num*(i*(k[a[i].col][i%2]-2)%mod+sum[a[i].col][i%2]%mod)%mod)%=mod;
printf("%d",(ans+mod)%mod);
return 0;
}