ps:之前做过这题,现在想用一个更简洁的代码
选用的是数学的做法,
由y−x=z−y可以推出x,z奇偶性相同,所以可以进行按颜色和奇偶性进行分组;假设在一组中这些格子数为k,内容分别是u1,u2,...,uk,在整个纸带上的编号分别是d1,d2,...,dk则可以推出这一组的总分数为
(u1+u2)(d1+d2)+(u1+u3)(d1+d3)+...+(u1+uk)(d1+dk)+(u2+u3)(d2+d3)+(u2+u4)(d2+d4)+...+(u2+uk)(d2+dk)+...+(uk−1+uk)(dk−1+dk)= \color{red}u_1d_1+u_1d_2$$+$$\color{blue}u_2d_1+u_2d_2$$+$$\color{red}u_1d_1+u_1d_3$$+u_3d_1+u_3d_3+...+$$\color{red}u_1d_1+u_1d_k$$+$$\color{green}u_kd_1+u_kd_k$$+\\$$\color{blue}u_2d_2+u_2d_3$$+u_3d_2+u_3d_3+$$\color{blue}u_2d_2+u_2d_4$$+u_4d_2+u_4d_4+...+$$\color{blue}u_2d_2+u_2d_k$$+$$\color{green}u_kd_2+u_kd_k$$+\\...+\\u_{k-1}d_{k-1}+u_{k-1}d_k+$$\color{green}u_kd_{k-1}+u_kd_k$$\\=\\u_1(d_1+d_2+d_1+d_3+...+d_1+d_k)+\\u_2(d_2+d_1+d_2+d_3+...+d_2+d_k)+\\...+\\u_k(d_k+d_1+d_k+d_2+...+d_k+d_{k-1})\\=\\u_1(d_1(k-2)+d_1+d_2+...+d_k)+\\u_2(d_2(k-2)+d_1+d_2+...+d_k)+\\...+\\u_k(d_k(k-2)+d_1+d_2+...+d_k)
可以发现只需事先将每一组的∑d和k算好,再遍历numberi就可以算出答案,思路应该没错,不过为什么过不了qwq
#include<bits/stdc++.h>
using namespace std;
long long k[100005][2],sum_d[100005][2],c[100005],x[100005];
long long n,m,ans;
int main(){
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++)scanf("%lld",x+i);
for (int i=1;i<=n;i++){
scanf("%lld",c+i);
k[c[i]][i%2]++;
sum_d[c[i]][i%2]+=i;
}
for (int i=1;i<=n;i++)
ans+=x[i]*(i*(k[c[i]][i%2]-2)%10007+sum_d[c[i]][i%2])%10007;
printf ("%lld",ans);
return 0;
}