P2671 [NOIP2015 普及组] 求和

发布时间 2023-04-24 21:54:57作者: Zlc晨鑫

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匹配,这样带来了方便。

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