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