P2671 [NOIP2015 普及组] 求和

here

看到这个条件，想到等差数列，于是假设了1, 3, 5位置上的颜色一样时，总和是多少，然后发现是：

(1 + 1 + 3 + 5)f(1) + (1 + 3 + 3 + 5)f(3) + (1 + 3 + 5 + 5)f(5)

现在看的很清楚了，有两种可能：

(i + 配对的数之和 + i)f(i)或者(i*配对的数的个数+配对的数之和)f(i)。

看看样例1，发现后者成立，前者不成立。

显然配对的数就是同奇偶的数，所以只要分别统计奇偶数的个数和总和，就可以对每个f(i)（也就是number[i]）单独统计贡献，此题完结。

时间复杂度O(N)。

但是这样是不严谨的，上述方法提供了一个方向，我们来看看为什么会这样。

把式子展开(a+b)(f(a)+f(b)) = (a+b)*f(a)+(a+b)*f(b)。

不难发现，每次有一个配对的数j出现，对于f(i)，系数就多了一个i+j，所以，配对的数的个数就是i的系数，而另外的一部分就是配对的数之和。

另外，由于数对是有序的，(1,3)和(3,1)，1都和3匹配，3都和1匹配，这样带来了方便。

如果上述数对算成两个，答案要乘二。