P2671 求和 题解

令$Score_i$表示以$i$为三元组第一个数的得分。 让我们来看看得分公式： $$Score=(x+z)\cdot (number_x+number_z)$$ 由乘法分配率可知: $$Score=x\cdot number_x+x\cdot number_z+z\cdot number_x+z\cdot number_z$$ 我们设可以以$x,y$的形式出现在同一三元组里的集合$\{i\}$ 可得集合$\{i\}$的得分为： $$(i1\cdot num[i1]+i1\cdot num[i2]+i2\cdot num[i1]+i2\cdot num[i3])+(i1\cdot num[i1]+i1\cdot num[i3]+i3\cdot num[i1]+i3\cdot num[i3])+...$$ 整理可得: $$Score_{i_n}=i_n\cdot \sum_{d=1}^nnumber_{i_d}+(n-2)\cdot(i_n\cdot number_{i_n})$$ 我们把$i_n$提出来，就得到了如下公式： $$Score_{i_n}=i_n\cdot[\sum_{d=1}^nnumber_{i_d}+(n-2)\cdot number_{i_n}]$$ 再看题目要求： 这个分数可能会很大，你只要输出整个纸带的分数**除以**10,007所得的**余数**即可。 所以我们应该利用同余定理改写这个公式： 记住下面这个恒等式： $$(\sum_{i=1}^n a_i)(mod\ M)≡\sum_{i=1}^n[a_i (mod\ m)]$$ 设$m=10007$,我们有： $$Score_{i_n}(mod\ m)=i_n(mod\ m)\cdot\{\sum_{d=1}^nnumber_{i_d}+[(n-2)(mod\ m)\cdot number_{i_n}+m](mod\ m)\}$$ 由题意得： $$ans=\sum_{i=1}^nScore_i$$ 我们利用前缀和优化这个公式，可将时辅优化到$O(n)$ 可能你对集合$\{i\}$的定义还不是很清楚。 特殊三元组$(x,y,z)$满足以下性质： 由题意得： - $x<y<z$ - $z-y=y-x$ - $color_x=color_z$ 为了方便，我们设$y=x+k$则$z=y+k$ 则有： $$2y=x+z→(x+y)(mod\ 2)=0$$ ~~那该三元组和y还有什么关系~~ 所以我们只要满足$x,z$同奇偶,颜色相同，便确认他们同在集合$\{i\}$ 前缀和优化如下： 设$sum[color_i][g]$表示同为颜色$color_i$,$(mod\ 2)=g$的所有数的数字和，即公式中的$\sum_{d=1}^nnumber_{i_d}$ 再设$nt[color_i][g]$表示这个集合的个数，即公式中的$n$ 一边输入颜色，就可一边累加，然后你就可以AC掉本题了。 完整代码如下： #include <cstdio> const int N = 100000; const int M = 10007; int n, m; int sum[N + 1][2], nt[N + 1][2]; int color[N + 1], number[N + 1]; long long ans = 0; int main() { scanf(" %d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &number[i]); number[i] %= M; } for(int i = 1; i <= n; i++) { scanf("%d", &color[i]); int c = color[i]; int g = i % 2; nt[c][g]++; sum[c][g] += number[i]; sum[c][g] %= M; } for(int i = 1; i <= n; i++) { int c = color[i]; int g = i % 2; ans += i % M * ((sum[c][g] + (nt[c][g] - 2) % M * number[i] + M) % M); ans %= M; } printf("%lld", ans); return 0; }