F - abcd

2 secs 1024 MB
shobonvip's icon shobonvip
Tweet
Problem
Submissions
Test cases
Editorial

英小文字からなる長さ NN の文字列を SS とします。まず、そもそも SS に "abcd" が含まれている（条件A）なら明らかに良い文字列です。そうでないなら、「整数 1≤k≤31\le k\le 3 が存在して、 SS の末尾 kk 文字が "abcd" の先頭 kk 文字、そして SS の先頭 4−k4-k 文字が "abcd" の末尾 4−k4-k 文字であること」（条件B）が必要十分です。

"abcd" が含まれている長さ NN の文字列（すなわち、条件Aを満たすものの個数）が ANA_N 通りあるとします。このとき、条件Bを満たす長さ NN の文字列は、末尾-先頭をつなぐ "abcd" でない長さ N−4N-4 の部分で "abcd" を連続部分列として含まなければよいです。これは 3×(26N−4−AN−4)3 \times (26^{N-4} - A_{N-4}) 通りです。

よって、答えを SNS_N とすると

SN=AN+3×(26N−4−AN−4)S_N = A_N + 3 \times (26^{N-4} - A_{N-4})

通りであることが分かります。一般の nn に対して AnA_n を数えればよく、これにはいろいろな方法があります。

DP の方法

いわゆる耳DPと言われる手法でこれを解きます。 dp[i][j]dp[i][j] を、長さ ii の文字列であって、状態が jj であるものの個数とします。ただし、状態は以下のように定めます。

  • 状態 11：文字列の末尾は "a" である
  • 状態 22：文字列の末尾は "ab" である
  • 状態 33：文字列の末尾は "abc" である
  • 状態 44：いままでに文字列の末尾が "abcd" になったことがある
  • 状態 00：状態 11 ～状態 44 のいずれでもない

状態 44 の末尾に何を追加しても状態 44 のままです。状態 11 のとき、末尾に "a" を追加したら状態 11 に、"b" を追加したら状態 22 に、それ以外の文字を追加したら状態 00 に遷移します。

状態 0,2,30, 2, 3 も同様に考えることができ、DP ができます。よって、 "abcd" の文字列長を K=4K=4 として O(NK)O(NK) で解くことができました。（ただし "abcd" の部分が一般の文字列 tt だった場合、さらに工夫が必要です。）

包除原理

「ii から i+3i+3 文字目が "abcd" となっている」という条件で包除原理を適用します. 条件が c1,c2,⋯ ,ckc_1, c_2, \cdots, c_k の位置で満たされているとして, その位置にある "abcd" を "@" の 1 文字と見なすことにします. 例えば c2,c7c_2, c_7 で条件が満たされているとして, "babcdeabcdfaaaabcddd" は "b@e@faaa@dd" に変換されます. 変換後も "abcd" が含まれている場合がありますが, 無視することにします.

c2,c7c_2, c_7 に "abcd" が入るという条件下で, 残りの N−8N-8 文字は自由に決められます. よって, この条件を満たす長さ NN (NN は十分大きい) の文字列の個数は 26N−826^{N-8} 通りあることになります. ここで, "abcd" の位置の制約を外し, 個数が KK 個, という場合, "@" の位置の決め方は (N−4K+KK)\binom{N-4K+K}{K} 通りあり, 残りの文字の決め方は 26N−4K26^{N-4K} 通りあります. 以上から, 包除原理より

AN=∑K=1⌊N/4⌋(−1)K−1(N−3KK)26N−4K\displaystyle A_N = \sum_{K=1}^{\lfloor N/4 \rfloor} (-1)^{K-1} \binom{N-3K}{K} 26^{N-4K}

母関数を用いる方法

"abcd" を含まない長さ NN の文字列の個数を CNC_N とします.

F(x)=C0+C1x+C2x2+⋯\displaystyle F(x) = C_0 + C_1x + C_2x^2 + \cdots

とおきます. 一方, 長さ NN の文字列の個数を DN=26ND_N = 26^N として

G(x)=D0+D1x+D2x2+⋯=11−26x\displaystyle G(x)\\ = D_0 + D_1x + D_2x^2 + \cdots\\ = \frac{1}{1-26x}

とおきます. 長さ NN の文字列の構造は「(長さ0以上の"abcd"を含まない文字列) ("abcd") (長さ0以上の"abcd"を含まない文字列) … (長さ0以上の"abcd"を含まない文字列) ("abcd") (長さ0以上の"abcd"を含まない文字列) 」となるので,

G(x)=F(x)+F(x)x4F(x)+F(x)x4F(x)x4F(x)+⋯=F(x)1−x4F(x)\displaystyle G(x)\\ = F(x) + F(x)x^4F(x) + F(x)x^4F(x)x^4F(x) + \cdots\\ = \frac{F(x)}{1-x^4F(x)}

となります. G(x)=1/(1−26x)G(x) = 1/(1-26x) より, 変形すると

F(x)=11−26x+x4\displaystyle F(x) = \frac{1}{1-26x+x^4}

を得ます. よって

CN=26CN−1−CN−4C_N = 26 C_{N-1} - C_{N-4}

を得ます. AN=26N−CNA_N = 26^N - C_N なので求まりました.