最近文章

440 Articles

OI

「Codeforces 666C」Codeword – 题解

Posted by kal0rona on

主要思路

就这?思博题。

总觉得做过啊。答案很显然跟字符无关,我们需要固定最左边的子序列,然后枚举最后一位,得出结论(子序列 \(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})\)。

OI

BZOJ2138:stone – 题解

Posted by kal0rona on

主要思路

首先可以发现这个东西可以被认为是一个二分图的模型,只不过现在我们需要快速算其最大匹配。那么根据 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} \]

这个东西用线段树维护即可。

OI

「AtCoder Regular Contest 090F」Number of Digits – 题解

Posted by kal0rona on

主要思路

这个题还蛮有意思。

首先有个暴力,\(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\) 确定了,那么就直接 ++ 即可。

OI

「QuestOJ」Product – 题解

Posted by kal0rona on

主要思路

硬推就完事了:

\[ \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) \]