금지어를 피하는 문자열
다이아몬드 IV의견: 0
앞에서부터 \(\sigma\)개의 소문자 알파벳(a, b, \(\dots\))만을 사용하여 길이 \(L\)인 문자열을 만들려 한다. 단, 금지어 목록에 있는 문자열 중 어느 것도 연속한 부분 문자열로 포함하지 않아야 한다.
이러한 '안전한' 문자열의 개수를 \(10^9 + 7\)로 나눈 나머지를 구하여라.
\(L\)이 매우 크므로 길이에 대한 단순 DP는 통과할 수 없다.
\(1 \le \sigma \le 5\)
\(1 \le K \le 50\)
\(1 \le L \le 10^{18}\)
금지어 길이의 합 \(\le 60\)
첫 줄에 알파벳 크기 \(\sigma\), 금지어 개수 \(K\), 문자열 길이 \(L\)이 주어진다.
다음 \(K\)개의 줄에 각 금지어가 주어진다. 금지어는 첫 \(\sigma\)개의 소문자만 사용한다.
안전한 길이 \(L\) 문자열의 개수를 \(10^9+7\)로 나눈 나머지를 출력한다.
2 1 3
aa
5길이 3, 알파벳 {a,b}, 금지어 aa. 전체 8개 중 aa를 포함하는 aaa, aab, baa를 빼면 aba, abb, bab, bba, bbb로 5개이다.
2 2 4
ab
ba
2금지어 ab, ba를 모두 피하려면 인접한 두 글자가 달라선 안 된다. 따라서 aaaa, bbbb 두 개만 안전하다.
플래티넘 Vriseoj 작성
출처 Original
평가 및 의견
금지어를 피하는 문자열
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
금지어를 피하는 문자열