A – Function

在考场上只推出来 \(f(x) = \mu(x) * \sigma_0^2(x) = \prod_{i = 1}^m (2c_i + 1)\)，显然用 min_25 就可以直接秒杀（但是我忘了板子呜呜呜呜呜）

主要思路

这个题还是比较简单的。

发现在生成树上放一个 \(2\) 之后，剩下与该点距离为偶数的点都已经确定了。所以对于一个连通块而言，被染成 \(2\) 的方式只有两种。

那么我们可以对这些连通块做一个背包，然后来判断是否有 \(n_2\) 的染色方案。

剩下的点随便染色即可。

主要思路

佛了。

让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数，用莫队搞即可；如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数，这个可以 \(\Theta(n)\)，如果是 \(5\) 那就把 \(0, 5\) 染色即可。

主要思路

一眼可以看出一个 \(\Theta(n^3)\) 的 DP。其实用双带权二分就可以用 \(\Theta(n \log^2 n)\) 的时间搞了，但是我没写这个写法。

考虑一下被选择时的贡献。\(p_a, p_b\) 是单元贡献，考虑同时被选的贡献 \(1 – (1 – p_a)(1 – p_b) = p_a + p_b – p_a p_b\)。所以我们可以考虑最大费用最大流，来算这个式子。

需要注意的是，我们需要保证每一次代价都是正的，因为我们其实并不需要最大流，而只是相对的最大费用。