主要思路
好题目啊。
发现 \(f(x)\) 对于有平方因子的数都没有效益，所以我们只考虑 \(f(x) = \prod_{i = 1}^m p_i\)。那么很容易发现 \(f(x) = \prod_{r = 0}^m (-1)^{2^{(r – 1)}}\)，所以：
\[ f(x) = \begin{cases} -1, x \in primes or x = 1 \\ 1, otherwise \end{cases} \]
Continue reading →好题目啊。
发现 \(f(x)\) 对于有平方因子的数都没有效益，所以我们只考虑 \(f(x) = \prod_{i = 1}^m p_i\)。那么很容易发现 \(f(x) = \prod_{r = 0}^m (-1)^{2^{(r – 1)}}\)，所以：
\[ f(x) = \begin{cases} -1, x \in primes or x = 1 \\ 1, otherwise \end{cases} \]
Continue reading →这也太他妈毒瘤了吧。
这个题首先肯定是要离线的，在线肯定没发做。事实上，我们可以对这个匹配分为三类：在上升链上、过 LCA 或者是在下降链上。这三者可以分开进行统计。上升链和下降链可以通过对询问字符串正反建 AC 自动机、然后在原树上做 DFS 即可；经过 LCA 的链有点难处理，发现能参与匹配的字符个数是与 \(|\text{询问串}|\) 相关的，所以我们把左右链的两个部分拼起来，然后单独跑 KMP 即可。
代码好长，狗屎一般。
Continue reading →这个题看上去像是 \(\Theta(n^3)\) 的。一眼想到设置 \(dp[i][a][b][c]\) 进行转移，然而发现不仅空间开不下而且还需要额外的时间。
考虑设计 \(dp[a][b][c]\)，其中 \(a, b, c\) 为 \(R, G, B\) 出现的最晚时间，显然有 \(i = \max(a, b, c)\)。通过这个，我们可以遍历一下要求然后做转移。
Continue reading →先考虑莫比乌斯反演？
\[ \begin{aligned} ans &= \sum_{i = 1}^n \sum_{j = 1}^n f(\gcd(i, j))^k \\ &= \sum_{d = 1}^n f(d)^k \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d] \end{aligned} \]
经典化简：
\[ \begin{aligned} ans &= \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor^2 \sum_{x|T} \mu(x) f(\frac{T}{x})^k \end{aligned} \]
我们可以对这个 \(\lfloor \frac{n}{T} \rfloor^2\) 进行整除分块，所以问题的重心转移到了求后面那个 Dirichlet 卷积的前缀和身上。
Continue reading →这个处理方式很妙啊。根据 yyb 的博客介绍，这种处理方式被称作是「最大值分治」。
我们可以考虑设计状态 \(dp[i][j]\) 为长度为 \(i\)、最大值不超过 \(j\) 的方案数。那么，我们可以枚举一个 \(k\) 作为 \(j\) 的位置，然后强制这个 \(k\) 在这一段里面是最右边的 \(j\)，具体写出转移就是：
\[ dp[i][j] = dp[i][j – 1] + \sum_{k = 1}^i dp[k – 1][j] \times dp[i – k][j – 1] \times w^c \]
注意右侧的 \(dp[i – k][j – 1]\)，可以保证该位置为最右侧的 \(j\)，这样就不会算重复了。其中 \(c\) 是当前序列里包含这个数的区间个数，画个图，算最右和最左的区间左边缘之差即可。
Continue reading →