問題
$K$ 個のパターン文字列 $P_1, \ldots, P_K$（いずれも小文字英字）が与えられる。長さ $L$ の小文字英字文字列のうち、$P_1, \ldots, P_K$ のいずれかを部分文字列として含まない文字列の個数を $10^9+7$ で割った余りを求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $K$ | $1 \le K \le 10$ |
| $L$ | $1 \le L \le 10^{18}$ |
| $|P_i|$ | $1 \le |P_i| \le 50$ |
| 全パターン合計文字数 | $\le 500$ |
入出力例
入力例 1
2 5
ab
cd出力例 1
7645184長さ5の文字列から "ab" または "cd" を含むものを除いた個数。
概念図: Aho-Corasick + 遷移行列
ヒント（段階的開示）
ヒント1: 方向性
Aho-Corasick オートマトムを構築し、「禁止パターンをどこにも含まない状態の集合」を遷移グラフとして定義。その上で行列累乗 $O(S^3 \log L)$ でカウントを計算する（S: オートマトンの非禁止状態数）。
ヒント2: アプローチ
- Aho-Corasick オートマトムを構築（BFS で failure link と goto 遷移テーブルを完成）
- 末端フラグ（禁止状態）を failure link 経由で伝播（祖先が禁止なら子も禁止）
- 非禁止状態のみで遷移行列 $T$（S×S）を構成（アルファベット 26 文字分の遷移を合算）
- $T^L \cdot e_0$ の総和が答え
ヒント3: コード骨格
# 非禁止状態のみのインデックスマップ
valid = [i for i in range(n) if not ac.banned[i]]
idx = {v: i for i, v in enumerate(valid)}
S = len(valid)
T = [[0]*S for _ in range(S)]
for s in valid:
si = idx[s]
for c in range(26):
nxt = ac.trans[s][c]
if not ac.banned[nxt]:
T[si][idx[nxt]] += 1
R = mat_pow(T, L, MOD)
ans = sum(R[0]) % MOD模範解答 (Python)
import sys
from collections import deque
input = sys.stdin.readline
MOD = 10**9 + 7
class AhoCorasick:
def __init__(self):
self.goto = [{}]
self.fail = [0]
self.banned = [False]
def add(self, s):
cur = 0
for c in s:
if c not in self.goto[cur]:
self.goto[cur][c] = len(self.goto)
self.goto.append({})
self.fail.append(0)
self.banned.append(False)
cur = self.goto[cur][c]
self.banned[cur] = True
def build(self):
n = len(self.goto)
self.trans = [[0]*26 for _ in range(n)]
q = deque()
for c in range(26):
ch = chr(ord('a')+c)
if ch in self.goto[0]:
nxt = self.goto[0][ch]
self.trans[0][c] = nxt
q.append(nxt)
else:
self.trans[0][c] = 0
while q:
u = q.popleft()
if self.banned[self.fail[u]]:
self.banned[u] = True
for c in range(26):
ch = chr(ord('a')+c)
if ch in self.goto[u]:
v = self.goto[u][ch]
self.fail[v] = self.trans[self.fail[u]][c]
self.trans[u][c] = v
q.append(v)
else:
self.trans[u][c] = self.trans[self.fail[u]][c]
def mat_mul(A, B, mod):
n = len(A)
C = [[0]*n for _ in range(n)]
for i in range(n):
for k in range(n):
if A[i][k] == 0: continue
for j in range(n):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
return C
def mat_pow(M, p, mod):
n = len(M)
R = [[1 if i==j else 0 for j in range(n)] for i in range(n)]
while p:
if p & 1: R = mat_mul(R, M, mod)
M = mat_mul(M, M, mod)
p >>= 1
return R
def solve():
K, L = map(int, input().split())
ac = AhoCorasick()
for _ in range(K):
ac.add(input().strip())
ac.build()
n = len(ac.goto)
valid = [i for i in range(n) if not ac.banned[i]]
idx = {v: i for i, v in enumerate(valid)}
S = len(valid)
T = [[0]*S for _ in range(S)]
for s in valid:
si = idx[s]
for c in range(26):
nxt = ac.trans[s][c]
if not ac.banned[nxt]:
T[si][idx[nxt]] = (T[si][idx[nxt]] + 1) % MOD
R = mat_pow(T, L, MOD)
print(sum(R[0]) % MOD)
solve()Step-by-Step 解説
Step 1: Aho-Corasick オートマトン
KMP の多パターン版。goto 関数と failure link で $O(\text{total\_len} \times |\Sigma|)$ の完全遷移テーブルを構築。各状態は「現在までの文字列の接尾辞として、どのパターンに最長マッチしているか」を表す。
Step 2: 禁止状態の伝播
failure link 経由で祖先ノードが禁止なら子ノードも禁止（どこかでパターンを踏んだなら、それ以降はすべて無効）。BFS 順に処理することで O(S) で伝播できる。
Step 3: 遷移行列の構築
非禁止状態間の遷移のみで S×S 行列 T を作る。T[i][j] = 状態 i から 1 文字で状態 j に遷移できる文字数（0〜26）。
Step 4: 行列累乗
$T^L$ の第 0 行の総和が長さ $L$ の有効文字列の個数。L が最大 $10^{18}$ のため行列累乗 $O(S^3 \log L)$ が必要。
Step 5: 計算量
| 処理 | 計算量 |
|---|---|
| AC 構築 | $O(\Sigma|P| \times 26)$ |
| 遷移行列構築 | $O(S \times 26)$ |
| 行列累乗 | $O(S^3 \log L)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| failure link 経由の禁止伝播を忘れる | パターン終端ノードのみ禁止にする | BFS で fail[u] が banned なら u も banned |
| 全状態で行列累乗する | 禁止状態を含めると遷移が余分 | valid 状態のみで idx マップを使う |
| L=0 の場合 | 行列の 0 乗が単位行列 → 初期状態 = 1 | mat_pow で単位行列を返す部分を確認 |
次のステップ
発展問題: パターンを含まない文字列のうち辞書順 K 番目のものを $O(S^2 \log N + S^3)$ で求めよ（累積和行列 + 二分探索）。