洛谷：P2671：求和

题目

P2671：求和

分析

这道题目，如果用暴力算法，是会超时的，大概只能得到50/100的分数。

先分析题目的条件。

条件一：\(x\lt y\lt z, y-x=z-y\)。整理得到：\(x+z=2y\)，这表明x和z要么都是奇数，要么都是偶数。这是一个关键的观察，启发我们将x/z进行奇偶分组。

条件二：\(b_x=b_z\)，这表明x和z还需要颜色相同。这启发我们也要进行颜色分组。

再看计算公式\((x+z)\times (a_x+a_z)\)，由于\(x+z=2y\)，所以这一项其实只和y有关。我们做个表格，假定\(a_1, a_2, a_3, a_4, a_5\)是满足上述所有条件的一个序列，那么最终的和应该是多少：

x/z	1	2	3	4	5
1	-	\(1a_1+1a_2+2a_1+2a_2\)	\(1a_1+1a_3+3a_1+3a_3\)	\(1a_1+1a_4+4a_1+4a_4\)	\(1a_1+1a_5+5a_1+5a_5\)
2	-	-	\(2a_2+2a_3+3a_2+3a_3\)	\(2a_2+2a_4+4a_2+4a_4\)	\(2a_2+2a_5+5a_2+5a_5\)
3	-	-	-	\(3a_3+3a_4+4a_3+4a_4\)	\(3a_3+3a_5+5a_3+5a_5\)
4	-	-	-	-	\(4a_4+4a_5+5a_4+5a_5\)
5	-	-	-	-	-

观察：

1. 系数为1的项：\(4\times 1a_1\)，以及\(1\times(a_2+a_3+a_4+a_5)\)。
2. 系数为2的项：\(4\times 2a_2\)，以及\(2\times(a_1+a_3+a_4+a_5\)。

因此，对于所有系数为i的项，其通项是：\((5-1)\times ia_i\)以及\(i(\sum_{j-1}^{5}a_j-a_i)\)。

结合分析，我们用s1数组记录：某种颜色、奇偶性不同的格子的数量；用s2数组记录：某种颜色、奇偶性不同的格子里数字的和¹，可以得到最终的公式，对于每一个i，其对答案的贡献是：

\(i\times((s_2[y][i\%2]-a[i])+a[i]\times (s1[y][i\%2]-1))=i\times((s_2[y][i\%2])+a[i]\times (s1[y][i\%2]-2))\)。

答案

思考

这道题很有挑战！但学会了分析后，可以迎刃而解。