목록Z 알고리즘 (1)
블로그 옮겼습니다
Codeforces Round #299 (Div. 2) D. Tavas and Malekas
http://codeforces.com/contest/535/problem/D 길이가 n인 어떤 문자열 s 가있고, 이 s안에서 k번 등장하는 어떤 패턴 p가 있다.패턴 p가 등장하는 위치를 오름차순으로 정렬한 sequence 에서 m개의 숫자로 이루어진임의의 subsequence 를 sub 이라고하자.입력으로 n, m, p, sub 가 주어질 때, 가능한 원래의 문자열 s의 가짓수를 구하는 문제이다.\(1 \le n \le 10^6\)\(0 \le m \le n - |p| + 1\)\(1 \le |p| \le n\) 우선, 길이 n인 연속된 빈 칸을 생각해 보자 여기에 p가 등장하는 위치에 p를 넣고 난 뒤빈 칸의 개수를 x라고 할 때 \(26^x\) 를 \(10^9+7\) 로 나눈 나머지를 구하는 문..
Algorithm/Problem Solving
2017. 9. 8. 20:40