正文部分：

首先考虑部分分：

$10pts:O(n^3)$枚举

$40pts:O(n^2)$枚举：

移项得知:$2y=x+z$，那么对于$x+z$为偶数的时候，一定有$y$存在，否则相反，于是复杂度就降了一维：

$100pts:O(n)$

同样继续$40pts$做法：将$y$移项：

那么原式就成了:\[x+z=2y\]

于是我们就可以讨论$x$与$z$的奇偶性：

奇+偶=奇奇+奇=偶偶+偶=偶偶+奇=奇

发现没有：$x$与$z$的奇偶性必须是相同的

那么我们不妨定义一个集合$i$，它有$n$个元素，并且这个集合里的数都是同奇偶且颜色相同的。（为方便，之后英文$number$统一写成$num$）

于是这个集合所造成的贡献就是：

$(i_1+i_2)(num_{i1}+num_{i2})+(i_1+i_3)(num_{i1}+num_{i3})+...+(i_{n-1}+i_n)*(num_{i_{n-1}}*num_{i_n})$

好晕啊。。那我们不妨就单拿$i_1$来举例子，即只考虑与$i_1$有关的项：于是式子就变成了：

$(i_1+i_2)(num_{i_1}+num{i_2})+..+(i_1+i_n)*(num_{i_1}+num_{i_n})$

似乎毫无头绪，那么尝试把与$i_1$有关的式子展开一下：

$i1*num_{i_2}+i1*num_{i1}...+i1*num_{in}+i1*num_{i1}$

发现没有，似乎有些规律：

继续尝试，将式子整理一下：

$i1*(num_{i2}+...+num_{in})+(n-1)*i_1*num_{i1}$

我们来解释一下为什么是$n-1$组，因为$i_1$与$i_1$不能组合为一组，但是与集合中的其他元素都能组合，顾为$n-1$组。

当做到这一步时，恭喜你，你已经离成功很近了。

这时还差最后一步，很明显：$(num_{i2}+...+num_{in})$这个东西是不确定的，比如当统计$i_2$时这个东西就变成了$(num_{i1}+num_{i3}+...+num_{in})$，但是我们要预处理出来的一定是一个可以计算的数，于是就要考虑有没有什么方法可以变形出一个等价的式子。

发现这个东西是不是跟$i_1+i_2+...+i_n$很像？没错，我们把这个东西加上$i_1*num_{i1}$，在最后面再减掉$i_1*num_{i1}$，于是原式就变成了这样：

$i1*(num_{i1}+num_{i2}+...+num_{in})+(n-1)*i_1*num_{i1}-{i_1}*{num_{i1}}$

合并一下同类项：

原式=$i1*(num_{i1}+num_{i2}+...+num_{in})+(n-2)*i_1*num_{i1}$

=$i_1*[num_{i1}+num_{i2}+...+num_{in}+(n-2)*num_{i_1}]$

呼呼，终于归纳完了。

于是我们就可以求出一个关于$i_n$的公式：

$i_n*[num_{i1}+num_{i2}+...+num_{in}+(n-2)*num_{i_n}]$

很明显$num_{i1}+num_{i2}+...+num_{in}$是可以预处理出来的，于是这道题就做完了。。~~真毒瘤啊。~~应该已经很清楚了吧，那我就不放代码啦$qwq$。

转载于:https://www.cnblogs.com/Sai0511/p/10360601.html

你可能感兴趣的文章