BZOJ3527:「ZJOI2014」力

主要思路

首先知道:

\[E_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2} – \sum_{j = i + 1}^{n}\frac{q_j}{(i – j)^2} \]

现在要求所有的。我们可以考虑分成前后两个部分分别计算。先考虑前面的部分:

\[a_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2}\]

我们发现这一部分还是很好计算的:当多项式指数为\(i\)时,对应\(a_i\),发现\(q_j\)和\((i – j)^2\)的下标相加恰好为\(i\)。正好是卷积的形式。后面那一个部分也可以直接这样算。

继续阅读BZOJ3527:「ZJOI2014」力