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