問題
長さ $L$ の文字列 $S$（英小文字のみ）を考える。$S$ に 禁止パターン $p_1, p_2, \ldots, p_K$（英小文字のみ）がいずれも部分文字列として含まれない確率を求めたい。
ただし $S$ は各位置を一様ランダムに英小文字 $26$ 文字から独立に選んで生成されるとする。
確率を $\bmod 10^9+7$ で出力せよ。
制約
| パラメータ | 範囲 |
|---|---|
| $L$ | $1 \le L \le 10^5$ |
| $K$ | $1 \le K \le 10$ |
| $\sum |p_i|$ | $\le 500$ |
| 出力 | 確率を $\bmod 10^9+7$ で（分子 × 分母の逆元） |
入出力例
入力例 1
5 2
ab
cd出力例 1
（mod 10^9+7 で出力）長さ5の文字列で "ab" も "cd" も含まない確率。分母 = $26^5$、分子 = Aho-Corasick + DP で計算。
概念図: Aho-Corasick オートマトン（例: p={"ab","cd"}）
ヒント（段階的開示）
ヒント1: 方向性
Aho-Corasick オートマトンを構築し、「禁止パターンにマッチしない遷移」だけ残した DFA 上でDPを行う。DFAの状態数 $\le \sum |p_i| \le 500$。各状態は「現在までの文字列の接尾辞がオートマトンの何番ノードか」を表す。
ヒント2: アプローチ
- Aho-Corasick の各ノードに 禁止フラグ（自分または suffix link 先が禁止パターンの末端）を付ける
- $dp[i][v]$: $i$ 文字決めた時点でオートマトム状態が $v$ にある場合の数
- 遷移: 26文字それぞれについて、遷移先が禁止でなければ加算
- 計算量: $O(L \cdot 26 \cdot |\text{状態数}|)$
ヒント3: コード骨格
# fail リンク構築後、完全遷移関数を事前計算
trans = [[0]*26 for _ in range(N_states)]
for v in range(N_states):
for ci in range(26):
c = chr(ord('a') + ci)
u = v
while u != 0 and c not in goto[u]:
u = fail[u]
trans[v][ci] = goto[u].get(c, 0)
# DP
dp = [0] * N_states
dp[0] = 1
for step in range(L):
ndp = [0] * N_states
for v in range(N_states):
if dp[v] == 0 or is_bad[v]: continue
for ci in range(26):
u = trans[v][ci]
if not is_bad[u]:
ndp[u] = (ndp[u] + dp[v]) % MOD
dp = ndp模範解答 (Python)
import sys
from collections import deque
input = sys.stdin.readline
MOD = 10**9 + 7
def solve():
L, K = map(int, input().split())
patterns = [input().strip() for _ in range(K)]
goto = [{}]
fail = [0]
is_bad = [False]
def add(s):
v = 0
for c in s:
if c not in goto[v]:
goto[v][c] = len(goto)
goto.append({})
fail.append(0)
is_bad.append(False)
v = goto[v][c]
is_bad[v] = True
for p in patterns:
add(p)
q = deque()
for c, u in goto[0].items():
fail[u] = 0
q.append(u)
while q:
v = q.popleft()
if is_bad[fail[v]]:
is_bad[v] = True
for c, u in goto[v].items():
f = fail[v]
while f != 0 and c not in goto[f]:
f = fail[f]
fail[u] = goto[f].get(c, 0)
q.append(u)
N = len(goto)
trans = [[0]*26 for _ in range(N)]
def get_trans(v, c):
while v != 0 and c not in goto[v]:
v = fail[v]
return goto[v].get(c, 0)
for v in range(N):
for ci in range(26):
trans[v][ci] = get_trans(v, chr(ord('a') + ci))
dp = [0] * N
dp[0] = 1
for _ in range(L):
ndp = [0] * N
for v in range(N):
if dp[v] == 0 or is_bad[v]: continue
for ci in range(26):
u = trans[v][ci]
if not is_bad[u]:
ndp[u] = (ndp[u] + dp[v]) % MOD
dp = ndp
total = pow(26, L, MOD)
ans_num = sum(dp) % MOD
ans = ans_num * pow(total, MOD-2, MOD) % MOD
print(ans)
solve()
Step-by-Step 解説
1Aho-Corasick オートマトンの構築
複数パターンを trie に追加し、BFS で失敗リンク（suffix link）を構築する。失敗リンクは「現在のパターン接頭辞の最長真接尾辞がオートマトン上でどの状態か」を指す。
複数パターンを trie に追加し、BFS で失敗リンク（suffix link）を構築する。失敗リンクは「現在のパターン接頭辞の最長真接尾辞がオートマトン上でどの状態か」を指す。
2禁止フラグの伝播
BFS 順に
BFS 順に
is_bad[v] |= is_bad[fail[v]] とすることで、suffix link 経由でパターンに一致する状態も禁止フラグを持つ。これがAho-Corasickの「辞書リンク」の役割。
3完全遷移関数の事前計算
26文字×各状態の遷移を事前計算し $O(1)$ で引けるようにする。遷移先が存在しない場合は fail リンクを辿って補完する。
26文字×各状態の遷移を事前計算し $O(1)$ で引けるようにする。遷移先が存在しない場合は fail リンクを辿って補完する。
4DP → 確率変換
$dp[v]$ = 禁止なしでオートマトム状態 $v$ に到達できる文字列数。全状態の和 / $26^L$ = 求める確率（mod逆元で計算）。
$dp[v]$ = 禁止なしでオートマトム状態 $v$ に到達できる文字列数。全状態の和 / $26^L$ = 求める確率（mod逆元で計算）。
計算量
Aho-Corasick 構築: $O(\sum|p_i| \cdot |\Sigma|)$ — $|\Sigma| = 26$
DP: $O(L \cdot S \cdot |\Sigma|)$ — $S = |\text{状態数}| \le 500$, $L \le 10^5$
全体: $O(L \cdot 500 \cdot 26) = O(1.3 \times 10^9)$ → 遷移の定数を小さく保つことで実用的
DP: $O(L \cdot S \cdot |\Sigma|)$ — $S = |\text{状態数}| \le 500$, $L \le 10^5$
全体: $O(L \cdot 500 \cdot 26) = O(1.3 \times 10^9)$ → 遷移の定数を小さく保つことで実用的
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| fail リンク構築前に DP | 不完全なオートマトン | BFS 完了後に trans を構築 |
| suffix 経由の禁止フラグを伝播しない | マッチ見落とし | is_bad[v] |= is_bad[fail[v]] |
| 遷移関数が部分的 | goto にない文字で fail を辿らない | get_trans(v, c) で fail を再帰的に辿る |
| 確率の分母計算ミス | $26^L$ でなく他の値 | pow(26, L, MOD) |
次のステップ
- 発展問題: 行列累乗と組み合わせ、$L$ が最大 $10^{18}$ の場合も $O(S^3 \log L)$ で解ける
- 関連: Aho-Corasick + 最短文字列（禁止パターンを全て含む最短文字列 = BFS on automaton）
- 応用: Aho-Corasick + bitDP（禁止パターンをいくつ使ったかの個数制約）