F - Strivore Editorial by miscalculation53
\(|S| = N\) とおきます。
求めるものは、次を満たす長さ \(N + K\) の文字列 \(T\) の個数です。
- \(T\) は \(S\) を（連続するとは限らない）部分列として含む。
この個数は、\((25 + x)^{N + K}\) の \(x^N\) 次以降の係数の和になります。
これは、部分列判定は前から貪欲にとっていけばよいことに注意して、\(T\) を前から作ると考えればわかります。各項において、
- \(x^1\) を選ぶ場合が、\(S\) の次の文字と同じ文字を選ぶ場合に対応し、
- \(25x^0\) を選ぶ場合が、それ以外の文字を選ぶ場合に対応しています。
ただし、\(S\) が部分列であることが確定してからも同様の場合分けを行うことになる都合上、「\(x^N\) 次以降の係数の和」という形になっています。
二項定理より \(\displaystyle (25 + x)^{N + K} = \sum_{i = 0}^{N + K} \binom{N + K}{i} 25^{N + K - i} x^i\) なので、答えは \(\displaystyle \sum_{i = N}^{N + K} \binom{N + K}{i} 25^{N + K - i}\) です。
余談
もうひとつの表式 \(\displaystyle \sum_{i = 0}^K 26^i 25^{K-i} \binom{N + K - 1 - i}{N - 1}\) を、ここからの式変形で導くこともできます。
\(\dfrac{1}{1 - x}\) をかけることと累積和をとることが対応するので、答えは \([x^{N+K}] \dfrac{(25 + x)^{N+K}}{1 - x} - [x^{N-1}] \dfrac{(25 + x)^{N+K}}{1 - x}\) と書けます。
ここで
\[ \begin{aligned} \frac{(25 + x)^n}{1 - x} &= \frac{25 + x}{1 - x}(25 + x)^{n-1} \\ &= \left(\frac{26}{1 - x} - 1\right)(25 + x)^{n-1} \\ &= 26 \cdot \frac{(25 + x)^{n-1}}{1 - x} - (25 + x)^{n-1} \end{aligned} \]
より、\(a_{n,m} = [x^m] \dfrac{(25 + x)^n}{1 - x}\) とおくと、漸化式
\[\displaystyle a_{n,m} = 26a_{n-1,m} - \binom{n-1}{m} 25^{n - 1 - m}\]
が成り立ちます。これを解くと、
\[a_{n,m} = 26^n - \sum_{i = 0}^{n - 1 - m} 26^i 25^{n - 1 - m - i} \binom{n - 1 - i}{m}\]
です。よって、答えは
\[\displaystyle a_{N+K,N+K} - a_{N+K,N-1} = \sum_{i = 0}^K 26^i 25^{K-i} \binom{N + K - 1 - i}{N - 1}\]
です。
posted:
last update: