分析: 这哪是前缀和呀这题，这明明是数学，纯纯的数学公式推导 根据以下这两个条件: 1. xyzxyzxyz是整数, x<y<zx<y<zx<y<z, y−x=z−yy-x=z-yy−x=z−y 2. colorxcolorxcolorx = colorzcolorzcolorz 可以很清楚的看出来实际上 yyy 在这里根本没起作用, 只要x+z=2yx+z=2yx+z=2y，colorxcolorxcolorx = colorzcolorzcolorz就行了。也就是只要x,zx,zx,z的奇偶相同，颜色相同就OK。 所以，很自然的就想到可以把奇偶和颜色分开，分别计算。 在此基础上再做优化就是数学推导，三元组规定为(x+z)(x+z)(x+z) x (numberx+numberz)(number_x+number_z)(numberx +numberz ),把式子展开来看就是: xxx x numberx+xnumber_x+xnumberx +x x numberz+znumber_z+znumberz +z x numberx+znumber_x+znumberx +z x numberznumber_znumberz 在对颜色和奇偶进行分类后，对我们的每一个集合内的数来分析就有： (i1+i2)(i_1+i_2)(i1 +i2 ) x (ni1+ni2)+(i1+i3)(n_{i1}+n_{i2})+(i_1+i_3)(ni1 +ni2 )+(i1 +i3 ) x (ni1+ni3)+......+(il+ik)(n_{i1}+n_{i3})+......+(i_l+i_k)(ni1 +ni3 )+......+(il +ik ) x (nil+nik)+(i2+i3)(n_{il}+n_{ik})+(i_2+i_3)(nil +nik )+(i2 +i3 ) x (ni2+(ni3))+(i2+i4)(n_{i2}+(n_{i3}))+(i_2+i_4)(ni2 +(ni3 ))+(i2 +i4 ) x ni2+ni4+......+(i2+ik)n_{i2}+n_{i4}+......+(i_2+i_k)ni2 +ni4 +......+(i2 +ik ) x (ni2+nik)+......+(ik+ik−1)(n_{i2}+n_{ik})+......+(i_k+i_k-1)(ni2 +nik )+......+(ik +ik −1) x nik+nik−1n_{ik}+n_{ik-1}nik +nik−1 后面再继续乘开来我们就会发现 (k−1)(k-1)(k−1) x (i1(i_1(i1 x ni1)+i1n_{i1})+i_1ni1 )+i1 x ∑t=2knit+\sum_{t=2}^k n_{it}+∑t=2k nit +一些后面的内容,请各位动动自己的聪明的脑瓜和可爱的小手自己算吧 然后(k−1)(k-1)(k−1) x (i1(i_1(i1 x ni1)+i1n_i1)+i_1ni 1)+i1 x ∑t=2knit\sum_{t=2}^k n_{it}∑t=2k nit 就可以进一步写成(k−2)(k-2)(k−2) x (i1(i_1(i1 x ni1)+i1n_i1)+i_1ni 1)+i1 x ∑t=1knit\sum_{t=1}^k n_{it}∑t=1k nit 这里我们终于看到了前缀和，感天动地。把后面的内容展开的话就会发现他们最后可以归成一个形式类似的式子也就是 (k−2)×(ir×nir)+ir×∑t−1knit(k-2) × (i_r × n_{ir})+i_r × \sum_{t-1}^k n_{it} (k−2)×(ir ×nir )+ir ×t−1∑k nit 所以我们就可以先处理出前缀和和相同颜色，相同奇偶的数的个数，这样只要O(n)O(n)O(n)的时间复杂度就可以处理出来所有的结果了。 AC代码 欢迎加入团队 > 打公式真的好辛苦,求一个免费的赞

/Lucky_Glass/ #include<cstdio> #include<vector> #include<algorithm> using namespace std; int read() //读入优化走起 { int x=0;char ch=getchar(); while(ch<'0' || ch>'9') ch=getchar(); while('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } const int Mod=10007; int num[100005],color[100005],ans[100005][2],len[100005][2]; int main() { int n=read(),m=read(); for(int i=1;i<=n;i++) num[i]=read(); for(int i=1;i<=n;i++) { int Color=color[i]=read(); ans[Color][i%2]+=num[i]; len[Color][i%2]; ans[Color][i%2]%=Mod; len[Color][i%2]%=Mod; } long long Ans=0; for(int i=1;i<=n;i) Ans+=(ans[color[i]][i%2]+(len[color[i]][i%2]-2)num[i]%Mod)%Modi,Ans%=Mod; printf("%lld\n",Ans); return 0; }

首先我们明确这个三元组更y没有关系 第一个条件实则是说x%2==z%2 第二个条件就是颜色相同 那么我们不妨在拿到一个数以后就把它按颜色，%2的结果分类 (x+z)*(number_x+number_z) = x * number_x + x * number_z + z * number_x + z * number_z 那如果已知z，考虑所有x就可以看做： p表示该分组的个数 第一部分：代码里的sum1 （(x1 * number_x1) + (x2 * number_x2) + ... + (xp * number_xp)） 第二部分： （编号（1）...编号（p））*(number_z) 第三部分 （number_1...number_p）* (z ) 第四部分 p*（z * number_z）

#include <bits/stdc++.h> using namespace std; int s[100005][2], sum[100005][2], c[100005], x[100005]; int n, m, ans; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> x[i]; } for (int i = 1; i <= n; i++) { cin >> c[i]; s[c[i]][i % 2]; sum[c[i]][i % 2] = (sum[c[i]][i % 2] + x[i]) % 10007; } 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; } cout<<ans; return 0; }

我们得了解如何计算得分。 显然， ∑x∈s(x+y)(Ax+Ay)=∑x∈s(x×Ax+x×Ay+y×Ax+y×Ay)=∑x∈sx×Ax+Ay×∑x∈sx+y×∑x∈sAx+∑x∈s×y×Ay\sum_{x\in s} (x+y)(A_x+A_y)\\ =\sum_{x\in s} (x\times A_x+x\times A_y+y\times A_x+y\times A_y)\\ =\sum_{x\in s} x\times A_x+A_y\times \sum_{x\in s} x+y\times \sum_{x\in s} A_x+\sum_{x\in s} \times y\times A_y x∈s∑ (x+y)(Ax +Ay )=x∈s∑ (x×Ax +x×Ay +y×Ax +y×Ay )=x∈s∑ x×Ax +Ay ×x∈s∑ x+y×x∈s∑ Ax +x∈s∑ ×y×Ay ，其中 yyy 为要计算得分的数。 所以我们只需要预处理出每种颜色的 ∑x∈s1,x,Ax,x×Ax\sum_{x\in s}1,x,A_x,x\times A_x∑x∈s 1,x,Ax ,x×Ax 即可。 注意把奇偶分开。

CP002798 [NOIP2015 普及组] 求和 题解 前言 此篇题解不是正解，如果想看正解请前往其他题解。 题目传送门 可能更好的阅读体验 别说我是抄袭的，同步在洛谷的文章的作者也是我。 为什么题解中没有一个是说明解题步骤的啊 QWQ 讲解 题都看了吧，第一个反应是暴力求解。 我是这样暴力的：先输入数据，在输入颜色的时候就顺便枚举到了 zzz 了，然后从后往前遍历，考虑到 y−x=z−yy − x = z − yy−x=z−y 这个条件，说明了要么 xxx 和 zzz 都是奇数，要么 xxx 和 zzz 都是偶数，所以说从后往前遍历的时候是依次减二的。 505050 分代码： 我们考虑优化，不丢弃只遍历 xxx 和 zzz 的思路，把所有颜色相同的每一个下标放在一个地方，当输入到这个颜色的时候遍历之前跟自己同一个颜色的格子，然后进行是否奇偶性相同的判断，如果符合就加在一起。 808080 分代码： 继续在上一步优化下想，因为每次都要遍历一遍又要判断，会多遍历很多次，于是我们将奇数和偶数区分开来放，每次就省去了判断的过程。 100100100 分代码： 时间复杂度：神仙复杂度，计算是 O(1)O(1)O(1) 的，所以优化过后较为快。 幸好ACGO的评测机较为强大，没有卡我常，在洛谷上要卡我常，所以在洛谷上要开O2。 踩着点过的，好像是960ms左右。

* * #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int m,n; long long ans; const int p=10007; struct node{ int num,color,n; }a[100010]; long long sum[100010][3];//统计相同颜色相同奇偶的格子的数字和 long long cnt[100010][3];//统计k inline int Read(){ int res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res10+ch-'0'; return flag?-res:res; } inline void Write(int a){ if(a>9) Write(a/10); putchar(a%10+'0'); } int main(){ n=Read();m=Read(); for (int i=1;i<=n;i++){ a[i].num=Read(); a[i].n=i; } for (int i=1;i<=n;i++){ a[i].color=Read(); sum[a[i].color][i%2]=sum[a[i].color][i%2]%p+a[i].num%p; sum[a[i].color][i%2]%=p; cnt[a[i].color][i%2]; } for (int i=1;i<=n;i){ if (cnt[a[i].color][i%2]>1){ ans=ans%p+i%p*(a[i].num%p*(cnt[a[i].color][i%2]-2%p)+sum[a[i].color][i%2]%p)%p;//套用推的式子 ans%=p; } } cout<<ans<<endl; return 0; } ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<cstdio> #define ll long long #define maxn 111111 #define mod 10007 #pragma GCC optimize(3,"Ofast","inline") inline ll read(){ ll r=0,f=1; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+(c^48),c=getchar(); return rf; } int n,m,num[maxn],col[maxn]; ll ans,s_c[maxn][2][4]; int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)num[i]=read()%mod; for(int i=1;i<=n;i++)col[i]=read()%mod; for(int i=1;i<=n;i++){//记得每一步都取模哦 (ans+=(s_c[col[i]][i%2][0](i%mod)*(num[i]%mod))%mod)%=mod; (ans+=s_c[col[i]][i%2][1])%=mod; (ans+=((i%mod)*s_c[col[i]][i%2][2])%mod)%=mod; (ans+=((num[i]%mod)s_c[col[i]][i%2][3])%mod)%=mod; (s_c[col[i]][i%2][0]+=1)%=mod; (s_c[col[i]][i%2][1]+=(i%mod)(num[i]%mod))%=mod; (s_c[col[i]][i%2][2]+=num[i]%mod)%=mod; (s_c[col[i]][i%2][3]+=i%mod)%=mod; } printf("%lld",ans); return 0; }

#include <cstdio> using namespace std; long long sum1[100005][2], sum2[100005][2], sum3[100005][2], sum4[100005][2]; long long number[100005], color[100005]; int main() { int n, m; scanf("%d %d", &n, &m); long long i; for (i = 1; i <= n; i++) scanf("%d", &number[i]); for (i = 1; i <= n; i++) scanf("%d", &color[i]); long long tot = 0; long long t1, t2; for (i = 1; i <= n; i++) { t1 = color[i]; t2 = i % 2; tot += sum1[t1][t2]; tot %= 10007; tot += (sum2[t1][t2] * number[i]) % 10007; tot %= 10007; tot += (((sum3[t1][t2] * i) % 10007) * number[i]) % 10007; tot %= 10007; tot += (sum4[t1][t2] * i) % 10007; tot %= 10007; sum1[t1][t2] += (i * number[i]) % 10007; sum1[t1][t2] %= 10007; sum2[t1][t2] += i; sum2[t1][t2] %= 10007; sum3[t1][t2]++; sum3[t1][t2] %= 10007; sum4[t1][t2] += number[i]; sum4[t1][t2] %= 10007; } printf("%lld", tot); return 0; } 链接描述