因为人傻常数大写了一天的题目。
题目意思另一种表达：
定义特殊二元组((x,z))。
1.(x<z)。
2.(x)与(z)要么都为奇数要么都为偶数。
（即(x mod 2 = z mod 2)）
3.(c_x=c_z)
4.该二元组的分数为((x+z) imes(a_x+a_z))
给定所有(c_i)与(a_i)，求满足条件的二元组的分数和。
以上的(x)，(z)在下文表述为(id_x)，(id_y)。（(y)代替(z)）
80分做法
以(v[i][0])来存储颜色为(i)的所有偶数下标的(num_i)与(a_i)。(v[i][1])来存储奇数下标。
有以下结论：
对于所有的((x,y))，(v[i][j][x])与(v[i][j][y])都两两为合法二元组。
然后枚举所有颜色(i)，接着枚举(x)，(y)暴力统计答案就可以了。
时间复杂度应该是(O(n^2))，不知道为啥有(80pts)（
(80pts:)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define MAXN (int)(1e5+233)
#define int long long
struct qwq
{
int a,c,id;
}e[MAXN];
vector<qwq> v[MAXN][2];
#define mod (10007)
signed main()
{
int n,m;
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",&e[i].a);
for (int i=1;i<=n;i++) scanf("%lld",&e[i].c),e[i].id=i;
for (int i=1;i<=n;i++)
{
v[e[i].c][i%2].push_back(e[i]);
}
int ans=0;
for (int i=1;i<=m;i++)
{
for (int j=0;j<v[i][0].size();j++)
{
for (int k=j+1;k<v[i][0].size();k++)
{
ans+=((v[i][0][j].id+v[i][0][k].id)*(v[i][0][j].a+v[i][0][k].a))%mod;
ans%=mod;
}
}
for (int j=0;j<v[i][1].size();j++)
{
for (int k=j+1;k<v[i][1].size();k++)
{
ans+=((v[i][1][j].id+v[i][1][k].id)*(v[i][1][j].a+v[i][1][k].a))%mod;
ans%=mod;
}
}
}
printf("%lld
",ans%mod);
return 0;
}
100分做法
(80)分做法中提到的(v[i][j][])这样的一个数组，我们简写为(s[])，考虑每次往数组后面加一个数，这个数对答案的贡献。
拆式（题目中的贡献式）
于是原式就拆为四个式子的和。
反思结论（(x)，(y)指在统计数组中的下标）
对于所有的((x,y))，(s[x])与(s[y])都两两为合法二元组。
那么每在(s[])末尾位置(y)多加入一个值，这个(y)就要与所有(0 < x < y)相匹配并累计贡献。（说简单点就和(y)之前的所有数匹配为合法二元组）
分别考虑拆式中四个式子
1.((id_x imes a_x))
对于所有(x)，答案加上(id_x imes a_x)。用(sumul)数组记录(sum_{x=1}^{y-1}id_x imes a_x)的和，累计进答案贡献。
2.((id_x imes a_y))
(sumid)记录(sum_{x=1}^{y-1}{id_x})，答案贡献加上(sumid imes a_y)。
3.((id_y imes a_x))
(suma)记录(sum_{x=1}^{y-1}{a_x})，答案贡献加上(suma imes id_y)
4.((id_y imes a_y))
我们知道在末尾位置(y)加一个数就增加了((y-1))个合法二元组。那么也就是会增加((y-1))个((id_y imes a_y))。用一个(sum)数组来记录末尾下标(y)。
5.总结贡献
(ans+=(sumul+sumid imes a_y +suma imes id_y +sum imes (id_y imes a_y)))
(100pts:)
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define MAXN (int)(1e5+233)
using namespace std;
int a[MAXN],c[MAXN],suma[MAXN][2],sumid[MAXN][2],sumul[MAXN][2],sum[MAXN][2];
struct qwq {
int a,c,id;
}e[MAXN];
#define mod (10007)
signed main() {
int n,m;
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++) scanf("%lld",&e[i].a);
for (int i=1;i<=n;i++) scanf("%lld",&e[i].c),e[i].id=i;
int ans=0;
for (int i=1;i<=n;i++)
{
ans+=sumul[e[i].c][i&1]+i*e[i].a*sum[e[i].c][i&1]+sumid[e[i].c][i&1]*e[i].a+suma[e[i].c][i&1]*i;
sumul[e[i].c][i&1]+=i*e[i].a;//处理a_i*i前缀和
suma[e[i].c][i&1]+=e[i].a;//处理a_i前缀和
sumid[e[i].c][i&1]+=i;//处理number_i前缀和
sum[e[i].c][i&1]++;//处理（不存在的）数组末尾下标
ans%=mod;
}
printf("%lld
",ans);
return 0;
}