一条狭长的纸带被均匀划分出了 \(n\) 个格子，格子编号从 \(1\) 到 \(n\) 。每个格子上都染了一种颜色 \(color_i\) 用 \([1,m]\) 当中的一个整数表示），并且写了一个数字 \(number_i\) 。
定义一种特殊的三元组：\((x,y,z)\)，其中 \(x，y，z\) 都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：
\(x,y,z\) 是整数, \(x<y<z\)，\(y-x=z-y\)
\(color_x=color_z\)
满足上述条件的三元组的分数规定为 \((x+z)\times (number_x+number_z)\)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以 \(10,007\) 所得的余数即可。
Input第一行是用一个空格隔开的两个正整数 \(n\) 和 \(m\) ， \(n\) 表纸带上格子的个数， \(m\) 表纸带上颜色的种类数。
第二行有 \(n\) 用空格隔开的正整数，第 \(i\) 数字 \(number\) 表纸带上编号为 \(i\) 格子上面写的数字。
第三行有 \(n\) 用空格隔开的正整数，第 \(i\) 数字 \(color\) 表纸带上编号为 \(i\) 格子染的颜色。
Output共一行，一个整数，表示所求的纸带分数除以 \(10,007\) 所得的余数。
Hint对 于 全 部 \(10\) 组 数 据 ， \(1\leq n\leq 100000, 1\leq m\leq 100000, 1\leq color_i\leq m，1\leq number_i\leq 100000\)
Solution首先能够推导出 \(x\) 和 \(z\) 的编号一定是奇偶性相同的。
所以想到对于奇数点和偶数点分开统计答案。
拆一下 \((x,y,z)\) 三元组对答案产生的贡献：\((x+z)\times (number_x+number_z)=x\times number_x+x\times number_z+z\times number_x+z\times number_z\)
观察拆完的式子，发现后边三项中与 \(x\) 无关的项都能用前缀和维护。
比如说第二项中的 \(x\times number_z,number_z\) 显然能用前缀和统计。即扫描到 \(x\) 节点时它和后面某个点 \(z\) 对答案在第二项的贡献即为 \((qzh\_number[z]-qzh\_number[x])\times x\)。
所以得到了以下这个基本完成的算法：
对于每个颜色，分别开两个数组，存储奇数节点和偶数节点的编号，记为 \(odd\) 和 \(even\)。
对于每个颜色中的 \(even\) 和 \(odd\)，再开三个前缀和数组分别维护 \(number_z,z,z\times number_z\) 的和。
然后扫描每个颜色，对每个颜色中存储的每个编号从头到尾扫一遍，答案加上这个点之后的所有点与这个点组成的三元组的贡献即可。
Code#include<cstdio> #include<vector> #include<cctype> #define N 100005 #define mod 10007 #define int long long int ans; int n,m; int num[N]; int col[N]; bool vis[N]; std::vector<int> even[N],odd[N]; std::vector<int> qzh1[N],qzh2[N],qzh3[N]; std::vector<int> qzh4[N],qzh5[N],qzh6[N]; inline char nc(){ static const int BS=1<<22; static unsigned char buf[BS],*st,*ed; if(st==ed) ed=buf+fread(st=buf,1,BS,stdin); return st==ed?EOF:*st++; } //#define nc getchar inline int getint(){ char ch; int res=0; while(!isdigit(ch=nc())); while(isdigit(ch)){ res=(res<<1)+(res<<3)+(ch^48); ch=nc(); } return res; } signed main(){ n=getint(),m=getint(); for(int i=1;i<=n;i++) num[i]=getint(); for(int i=1;i<=n;i++){ col[i]=getint(); if(i&1){ odd[col[i]].push_back(i); int a=qzh1[col[i]].size(); if(!qzh1[col[i]].empty()) qzh1[col[i]].push_back((qzh1[col[i]][a-1]+num[i])); else qzh1[col[i]].push_back(num[i]); a=qzh2[col[i]].size(); if(!qzh2[col[i]].empty()) qzh2[col[i]].push_back((qzh2[col[i]][a-1]+i)); else qzh2[col[i]].push_back(i); a=qzh3[col[i]].size(); if(!qzh3[col[i]].empty()) qzh3[col[i]].push_back((qzh3[col[i]][a-1]+i*num[i])); else qzh3[col[i]].push_back((i*num[i])); } else{ even[col[i]].push_back(i); if(!qzh4[col[i]].empty()) qzh4[col[i]].push_back((qzh4[col[i]][qzh4[col[i]].size()-1]+num[i])); else qzh4[col[i]].push_back(num[i]); if(!qzh5[col[i]].empty()) qzh5[col[i]].push_back((qzh5[col[i]][qzh5[col[i]].size()-1]+i)); else qzh5[col[i]].push_back(i); if(!qzh6[col[i]].empty()) qzh6[col[i]].push_back((qzh6[col[i]][qzh6[col[i]].size()-1]+i*num[i])); else qzh6[col[i]].push_back((i*num[i])); } } for(int k=1;k<=n;k++){ if(vis[col[k]]) continue; vis[col[k]]=1; for(int i=0;i<odd[col[k]].size();i++){ int p=odd[col[k]].size()-i-1; (ans+=odd[col[k]][i]%mod*num[odd[col[k]][i]]%mod*p%mod)%=mod; (ans+=odd[col[k]][i]%mod*(qzh1[col[k]][qzh1[col[k]].size()-1]-qzh1[col[k]][i])%mod)%=mod; (ans+=num[odd[col[k]][i]]%mod*(qzh2[col[k]][qzh2[col[k]].size()-1]-qzh2[col[k]][i])%mod)%=mod; (ans+=qzh3[col[k]][qzh3[col[k]].size()-1]-qzh3[col[k]][i])%=mod; } for(int i=0;i<even[col[k]].size();i++){ int p=even[col[k]].size()-i-1; (ans+=even[col[k]][i]%mod*num[even[col[k]][i]]%mod*p%mod)%=mod; (ans+=even[col[k]][i]%mod*(qzh4[col[k]][qzh4[col[k]].size()-1]-qzh4[col[k]][i])%mod)%=mod; (ans+=num[even[col[k]][i]]%mod*(qzh5[col[k]][qzh5[col[k]].size()-1]-qzh5[col[k]][i])%mod)%=mod; (ans+=qzh6[col[k]][qzh6[col[k]].size()-1]-qzh6[col[k]][i])%=mod; } } printf("%lld\n",ans%mod); return 0; }