P2671 [NOIP2015 普及组] 求和

 1 //(x+z)*(num[x]+num[z])=
 2 //(x1+x2)*(y1+y2)+(x1+x3)*(y1+y3)+(x2+x3)*(y2+y3) 
 3 //=x1*(y1*(n-2)+y1+y2+...+yn) 
 4 //+x2*(y2*(n-2)+y1+y2+...+yn)
 5 //+xn*(yn*(n-2)+y1+y2+...+yn)
 6 //即求出y1到yn的前缀和然后循环计算即可 
 7 
 8 //题目要求格子颜色相同，可以把相同颜色的格子分在一个组
 9 //且z-y=y-x，得x+z=2y，所以x和z为同奇或同偶
10 //所以相同格子中又可以奇数分一组偶数分一组
11 //操作时只针对每个组组内操作就行 
12 #include <bits/stdc++.h>
13 using namespace std;
14 const int maxn=1e5+5;
15 //数据范围 
16 const int mol=1e4+7;
17 //模数 
18 int n,m,ans;
19 //m为颜色种数，没啥用 
20 struct node{
21     int id,num,col;
22     //id为下表，没有用
23     //num为格子上的数字
24     //col为格子颜色 
25 }p[maxn];
26 int geshu[maxn][2];
27 //相同颜色格子且下标同奇或同偶格子的个数 
28 int tot[maxn][2];
29 //相同颜色格子且下标同奇或同偶格子的数字和 
30 int main(){
31     scanf("%d%d",&n,&m);
32     for(int i=1;i<=n;i++){
33         scanf("%d",&p[i].num);
34         p[i].id=i;
35     }
36     for(int i=1;i<=n;i++){
37         scanf("%d",&p[i].col);
38         geshu[p[i].col][i%2]++;
39         tot[p[i].col][i%2]=(tot[p[i].col][i%2]+p[i].num)%mol;
40         //时刻模 
41     }
42     for(int i=1;i<=n;i++){
43         ans=(ans+i*((geshu[p[i].col][i%2]-2)*p[i].num%mol+tot[p[i].col][i%2])%mol)%mol;
44         
45     }
46     printf("%d",ans);
47     return 0;
48 }