일차원 세포 자동자

시간 제한2초메모리 제한128 MB

요약

N개의 셀이 모듈로 M 연산으로 갱신되는 선형 점화식을 행렬 거듭제곱으로 T 시간 뒤 상태까지 빠르게 계산하는 문제입니다.

난이도: 보통10점 중 6점
유형: 행렬, 수학, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

$N$ 개의 세포로 이루어진 일차원 세포 자동자(cellular automaton)가 있다. 세포에는 $0$ 번부터 $N-1$ 번까지 번호가 매겨져 있다.

각 세포는 상태를 가지며, 상태는 $M$ 보다 작은 음이 아닌 정수이다. 세포의 상태는 시간이 $1$ 씩 지날 때마다 진화한다. 시간 $t$ 에서 $i$ 번 세포의 상태를 $S(i, t)$ 로 나타낸다. 시간 $t+1$ 에서의 상태는 다음 식으로 구한다.

$S(i, t+1) = (A \times S(i-1, t) + B \times S(i, t) + C \times S(i+1, t)) \bmod M$

여기서 $A$ , $B$ , $C$ 는 음이 아닌 정수이다. $i < 0$ 또는 $i \ge N$ 인 경우에는 $S(i, t) = 0$ 으로 둔다.

일차원 세포 자동자의 초기 상태가 주어졌을 때, 시간이 $T$ 만큼 지난 뒤의 세포 상태를 구하는 프로그램을 작성하시오.

입력

각 테스트 케이스는 다음과 같은 형식이다.

N M A B C T
S(0,0) S(1,0) ... S(N-1,0)

제약은 $0 < N \le 50$ , $0 < M \le 1000$ , $0 \le A, B, C < M$ , $0 \le T \le 10^9$ 이다.

입력의 마지막 줄에는 $0$ 이 여섯 개 주어진다.

출력

각 테스트 케이스에 대해, 시간 $T$ 에서의 세포 상태를 다음 형식으로 출력한다.

S(0,T) S(1,T) ... S(N-1,T)

각 세포의 상태는 정수이며, 값들은 공백으로 구분한다.

예제3

예제 1

입력

5 4 1 3 2 0
0 1 2 0 1
5 7 1 3 2 1
0 1 2 0 1
5 13 1 3 2 11
0 1 2 0 1
5 5 2 0 1 100
0 1 2 0 1
6 6 0 2 3 1000
0 1 2 0 1 4
20 1000 0 2 3 1000000000
0 1 2 0 1 0 1 2 0 1 0 1 2 0 1 0 1 2 0 1
30 2 1 0 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
30 2 1 1 1 1000000000
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
30 5 2 3 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0

예상 출력

0 1 2 0 1
2 0 0 4 3
2 12 10 9 11
3 0 4 2 1
0 4 2 0 4 4
0 376 752 0 376 0 376 752 0 376 0 376 752 0 376 0 376 752 0 376
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 3 2 2 2 3 3 1 4 3 1 2 3 0 4 3 3 0 4 2 2 2 2 1 1 2 1 3 0

예제 2
입력
```
1 5 0 3 0 4
2
0 0 0 0 0 0
```
예상 출력
```
2
```

예제 3

입력

4 10 5 5 5 0
3 7 1 9
0 0 0 0 0 0

예상 출력

3 7 1 9