题解：P10329 [UESTCPC 2024] Add

Pyrf_uqcat · 2024-04-13 13:09:11 · 题解

已知一共 T 组数据，且每输入一个 n 都会有一个答案，观察样例，很明显能够发现每一个 n 都会有固定答案。

比赛时，就想着打表骗点小分，根据样例，把样例输出存入表中打出来了这个：

ans[]={0,1,5,14,30,55,0,0,204};

经过每项作差发现：所有差都是平方数。也就是说，答案为 1^2+2^2+3^2+\dots+n^2，这样计算会超时，可以网上查一下运算公式 \frac{n(n+1)(2n+1)}{6}。

但是，很明显缺少证明，被打回了。那只能用一下正常的方法了。

将数 a_x 加入到 a_y 经过计算并化简明显可知，贡献为 2x^2+2xy，那么总贡献为 1(2x^2+2xy)+2(2x^2+2xy)+\dots+(x-1)(2x^2+2xy)=x^3-x，所以最后答案为 1(\frac{x^3-x}{x-1})+2(\frac{x^3-x}{x-1})+\dots+x(\frac{x^3-x}{x-1})= \frac{n(n+1)(2n+1)}{6}，时间复杂度 O(1)。