A – Range Flip Find Route
思博题。考虑最后的路径肯定是多个黑白子路径的拼接，那么路径的代价就是进入黑色子路径的次数，那么我们只需要建图的时候给白色入黑色的边赋 \(1\) 的权即可。
Continue reading →思博题。考虑最后的路径肯定是多个黑白子路径的拼接，那么路径的代价就是进入黑色子路径的次数，那么我们只需要建图的时候给白色入黑色的边赋 \(1\) 的权即可。
Continue reading →就这？思博题。
总觉得做过啊。答案很显然跟字符无关，我们需要固定最左边的子序列，然后枚举最后一位，得出结论（子序列 \(T\)、目标串长 \(n\)）：
\[ ans = \sum_{i = |T|}^n 25^{i – |T|} \times 26^{n – i} {i – 1 \choose k – 1} \]
考虑把 \(n\) 提出来：
\[ ans = 26^n \sum_{i = |T|}^n 25^{i – |T|} \times 26^{-i} {i – 1 \choose k – 1} \]
发现一个重要性质：\(\sum |T| \leq 10^5\)，所以对于不同的 \(|T|\)，最好情况下个数为 \(\Theta(\sqrt{n})\)。那么既然 \(n\) 可以被独立出来，那么最后复杂度就是 \(\Theta(|T|\sqrt{n})\)。
Continue reading →首先可以发现这个东西可以被认为是一个二分图的模型，只不过现在我们需要快速算其最大匹配。那么根据 Hall 定理，如果对于任意一个左部点 \(x \in U, |U| < |V|\)，其连接的右端点集合 \(M\) 满足 \(|M| > |U|\)，那么就存在完美匹配。
这个题有个性质：区间互不包含。所以满足 Hall 定理其实就需要满足对于每个线段都存在 \(\sum_{i = l}^r b_i \leq \sum_{i = L[l]}^{R[r]} a_i\)，其中 \(b_i\) 是对于第 \(i\) 根线段我们取了 \(b_i\) 个石子。
我们可以写成一个前缀和进行移项：
\[ p^b = \sum b_i, p^a = \sum a_i \\ p^b_{r} – p^b_{l – 1} \leq p^a_{R[r]} – p^b_{L[l] – 1} \\ p^b_{r} – p^a_{R[r]} \leq p^b_{l – 1} – p^b_{L[l] – 1} \]
这个东西用线段树维护即可。
Continue reading →这个题还蛮有意思。
首先有个暴力，\(l\) 在 \(10^7\) 内可以直接 two-pointers；如果在 \(10^7\) 以上，那么发现 \(f(r) – f(l) \leq 1\)。那么我们可以考虑枚举这个连续段的长 \(L = x + y\)，其中 \(x\) 是 \(i\) 个 \(0\) 的部分，而 \(y\) 是 \(i + 1\) 个 \(0\) 的部分。有个等式：\(x \times i + y \times (i + 1) = (x + y)i + y = Li + y = S\)。所以枚举 \(L\) 的时候，如果 \(S \bmod L \equiv 0\)，那么说明 \(y = 0\)，你就把 \(10^i\) 内的左端点个数算出来（其实就是多减一个 \(L – 1\)）。如果 \(S \bmod L \neq 0\)，那么说明 \(x, y\) 确定了，那么就直接 ++ 即可。
Continue reading →硬推就完事了：
\[ \begin{aligned} g(n) &= \sum_{i = 1}^n \frac{n}{\gcd(i, n)} = n \sum_{d|n} \frac{1}{d} \sum_{i = 1}^n [\gcd(n, i) = d] \\ &= n \sum_{d|n} \frac{1}{d} \sum_{i = 1}^{\frac{n}{d}} [\gcd(\frac{n}{d}, i) = 1] = \sum_{d|n} \frac{n}{d} \varphi(\frac{n}{d}) = \sum_{d|n} d \varphi(d) \\ &= \sum_{d|n} d^2 \prod_{p_i} (1 – \frac{1}{p_i}) = \prod_{p_i} (1 + \sum_{g = 1}^{e_i} p_i^{2g} (1 – \frac{1}{p_i}) ) \\ &= \prod_{p_i} (1 + \sum_{g = 1}^{e_i} p_i^{2g} – \sum_{g = 1}^{e_i} p_i^{2g – 1}) = \prod_{p_i} (1 + \sum_{g = 1}^{e_i} p_i^{2g} – \frac{ \sum_{g = 1}^{e_i} p_i^{2g} }{p_i} ) \\ &= \prod_{p_i} (1 + (1 – \frac{1}{p_i}) (\sum_{g = 1}^{e_i} p_i^{2g}) ) = \prod_{p_i} (1 + (1 – \frac{1}{p_i}) \frac{p_i^2 (1 – p_i^{2e_i})}{1 – p_i^2}) \\ &= \prod_{p_i} (1 + \frac{(p_i – 1)}{p_i} \frac{p_i^2 (1 – p_i^{2e_i})}{(1 – p_i)(1 + p_i)} ) \\ &= \prod_{p_i} (1 – \frac{p_i (1 – p_i^{2e_i})}{1 + p_i} ) = \prod_{p_i} \frac{1 + p_i – p_i + p_i^{2e_i + 1}}{1 + p_i} \\ &= \prod_{p_i} \frac{p_i^{2e_i + 1} + 1}{1 + p_i} \end{aligned} \]
最后上下除一下，得到：
\[ \frac{f(n)}{g(n)} = \prod_{p_i} (1 + p_i) \]
Continue reading →