속독 강좌

Byteasar는 속독 강좌를 수강했고, 그곳에서 지각 능력을 향상시키는 여러 훈련을 배웠다. 그가 가장 좋아하는 훈련은 기호열에서 패턴을 찾는 것이다. 이 훈련을 위해 Byteasar는 컴퓨터로 0과 1로 이루어진 아주 긴 수열을 다음과 같이 생성한다. 서로소인 두 정수 $n$과 $a$, 그리고 정수 $b$, $p$를 고르면 컴퓨터는 $c_0, c_1, \dots, c_{n-1}$을 생성하는데, $(ai+b) \bmod n < p$일 때 그리고 그때만 $c_i = 0$이다. 마지막으로 Byteasar는 더 짧은 $m$개의 기호로 이루어진 수열 $w_0, w_1, \dots, w_{m-1}$을 생각한다. 여기까지 준비한 뒤, 그의 과제는 컴퓨터가 생성한 수열에서 짧은 수열이 나타나는 모든 위치를 최대한 빠르게 찾는 것이다. 그는 자신이 정말로 모든 위치를 찾았는지 확인하는 프로그램을 작성하는 데 도움을 요청했다.

첫째 줄에 다섯 정수 $n$, $a$, $b$, $p$, $m$이 하나의 공백으로 구분되어 주어진다 ($2 \le n \le 1\,000\,000\,000$, $1 \le p, a, b, m < n$, $1 \le m \le 1\,000\,000$). $a$와 $n$은 서로소이다. 둘째 줄에는 0 또는 1인 $m$개의 기호로 이루어진 단어 $w_0, w_1, \dots, w_{m-1}$이 주어진다. 다음의 상호 배타적인 부류들이 전체 테스트 입력의 부분집합을 이룬다.

• 전체 점수의 8%에 해당하는 테스트에서는 $n \le 1000$이다.
• 전체 점수의 8%에 해당하는 다른 테스트에서는 $n \le 1\,000\,000$이다.
• 전체 점수의 66%에 해당하는 또 다른 테스트에서는 $m \le 1000$이다.

첫째 줄이자 유일한 줄에 수열 $c_0, c_1, \dots, c_{n-1}$에서 수열 $w_0, w_1, \dots, w_{m-1}$이 나타나는 횟수를 출력한다.

$n = 9$, $a = 5$, $b = 6$, $p = 4$일 때 컴퓨터는 다음과 같이 수열을 생성한다.

수열 101011010에서 101은 세 번 나타난다.