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」力

P1447:[NOI2010]能量采集题解

解法

这道题是一道裸题,考察莫比乌斯反演和 Dirichlet 卷积的知识。

在这里我们规定\(n<m\),这两者调换不会对答案产生影响。然后我们来观察这个计数规律,发现每一个点对答案的贡献至少为\(1\),附加的贡献其实就是当前线段上除了本身的整点(整数坐标点)个数的两倍,换句话说就是:

\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]

继续阅读P1447:[NOI2010]能量采集题解

莫比乌斯反演与杜教筛

简述

省选级别以上的 OI 赛事中的数学题,相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲:

继续阅读莫比乌斯反演与杜教筛