题解 P2671 【求和】
很简单的一道数学题，楼下的代码为什么都那么长，看起来好复杂
题目分析
根据题目，我们可以设有三个下标，他们分别是x,y,z，要满足x<y<z且y-x=z-y
所以我们可以模拟x,y,z，其时间复杂度为O(n^3)，由于n<=100000所以一定会超时
但这个方法是可以优化的
由此我们可以得到2y=z+x
由此可知z+x必须是一个偶数即z,x同为奇数或同为偶数
所以我们其实只要穷举x和z就行了，但这个方法的时间复杂度为O(n^2)所以还是会超时
我们可以用一下分组思想，把每个颜色分为一组，再在每个颜色中按奇偶分组，所以一共有2m组
设一个分组里有k个数，这个分组中的数分别是x[1],x[2]……x[k]，下标分别是y[1],y[2]……y[k]
那么可得
答案=(x[1]+x[2])*(y[1]+y[2])+(x[1]+x[3])*(y[1]+y[3])+……+(x[1]+x[k])*(y[1]+y[k])
+(x[2]+x[3])*(y[2]+y[3])+(x[2]+x[4])*(y[2]+y[4])+……+(x[2]+x[k])*(y[2]+y[k])
+……
+(x[k-1]+x[k])\*(y[k-1]+y[k])
=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]\*(y[1]+y[k]+y[2]+y[k]+……+y[k-1]+y[k])
=x[1]\*(y[1]\*(n-2)+y[1]+y[2]+……+y[k])
+x[2]\*(y[2]\*(n-2)+y[1]+y[2]+……+y[k])+……
+x[k]\*(y[k]\*(n-2)+y[1]+y[2]+……+y[k])然后事先将y[1]+y[2]+……+y[k]求出，用的时候调用就行了，其时间复杂度为O(n)
代码如下：
//--新阶梯工作室防伪水印--
//--By新阶梯工作室 闪现--
#include <cmath>
#include <ctime>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>//头文件准备
using namespace std;
int s[100005][2],sum[100005][2],c[100005],x[100005];.//定义二维数组方便分组
int n,m,ans;
int main(){
scanf ("%d %d",&n,&m);//其实m没有什么用处
for (int i=1;i<=n;i++){
scanf ("%d",&x[i]);
}
for (int i=1;i<=n;i++){
scanf ("%d",&c[i]);
s[c[i]][i%2]++;//求出这个分组中有多少个数
sum[c[i]][i%2]=(sum[c[i]][i%2]+x[i])%10007;//事先求出累加和，注意，要mod10007
}
for (int i=1;i<=n;i++){
ans=(ans+i*((s[c[i]][i%2]-2)*x[i]%10007+sum[c[i]][i%2]))%10007;//依次然后代入，注意，也要mod10007
}
printf ("%d\n",ans);//最后输出
return 0;
}