题意
给定一个带有颜色和数字的序列，我们要寻找三元组 \((x,y,z)\) 满足以下条件：
- \(y\) 为 \(x\) 和 \(z\) 的中点且都为整数。
- \(color[x]=color[z]\)。
我们命这样一个三元组对答案的贡献为 \((x+z)*(num[x]+num[z])\)。整个序列的总价值为每个符合要求的三元组的贡献和。现求出这个贡献和，并对 \(10007\) 取余。
思路
显然的结论是：\(x\) 与 \(z\) 同奇同偶
若当前到了一个点 \(i\)，那么设其前面有一个数 \(k\) 满足上述条件。
则贡献表示为：
\[\sum\limits_{k}(i+k)\times (num[i]+num[k]) \\ \sum\limits_{k}(i\times num[i]+k\times num[i]+i\times num[k]+k\times num[k]) \\ inum[i]\times\#k+num[i]\sum\limits_kk+i\sum\limits_k num[k]+\sum\limits_k k\times num[k] \]其中，\(inum[i]\times \#k\) 指当前元素的位置与数字的乘积乘上满足条件的 \(k\) 的个数。
\(\sum\limits_k k\) 指满足条件的 \(k\) 的乘积。
\(\sum\limits_k num[k]\) 指满足条件的 \(k\) 的数字乘积。
\(\sum\limits_k knum[k]\) 指满足条件的 \(k\) 的位置与数组的乘积。
用一个 \(4\) 维数组来对以上数据进行前缀和处理。同时前缀和需要奇偶相同。则要对整个数组开 \(2\) 维。
我们设一个数组 \(sum[q][col][op]\)，\(q\) 指第几类前缀和，\(col\) 指颜色，\(op\) 指奇偶性。
现在前缀和转移易得如下：
sum[0][col[i]][i&1]=sum[0][col[i]][i&1]+(i*num[i])
sum[1][col[i]][i&1]=sum[1][col[i]][i&1]+num[i]
sum[2][col[i]][i&1]=sum[2][col[i]][i&1]+1
sum[3][col[i]][i&1]=sum[3][col[i]][i&1]+i
当前位置 \(k\) 的贡献为：
sum[0][col[i]][i&1]+i*sum[1][col[i]][i&1]+i*x*sum[2][col[i]][i&1]+x*sum[3][col[i]][i&1]
累加计数即可
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
template<typename P>
inline void read(P &x){
P res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
res=res*10+ch-'0';
ch=getchar();
}
x=res*f;
}
using namespace std;
int T=1;
const int mod=10007;
int n,m;
int num[100010];
int col[100010];
int sum[4][100010][2];
signed main(){
read(n),read(m);
for(int i=1;i<=n;++i) read(num[i]);
for(int i=1;i<=n;++i) read(col[i]);
int ans=0;
for(int i=1;i<=n;++i){
int cx=col[i],x=num[i];
ans=(ans%mod+sum[0][col[i]][i&1]%mod+i*sum[1][col[i]][i&1]%mod+i*x*sum[2][col[i]][i&1]%mod+x*sum[3][col[i]][i&1]%mod+mod)%mod;
sum[0][col[i]][i&1]=(sum[0][col[i]][i&1]%mod+(i*num[i])%mod+mod)%mod;
sum[1][col[i]][i&1]=(sum[1][col[i]][i&1]%mod+num[i]%mod+mod)%mod;
sum[2][col[i]][i&1]=(sum[2][col[i]][i&1]%mod+1+mod)%mod;
sum[3][col[i]][i&1]=(sum[3][col[i]][i&1]%mod+i+mod)%mod;
}
cout<<ans%mod<<endl;
return 0;
}