시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 38 22 18 62.069%

문제

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

각 세포는 상태를 가지고 있다. 상태는 M보다 작은 음이 아닌 정수이다. 세포의 상태는 시간이 1씩 지날때마다 진화한다. 시간 t에서 i번째 세포의 상태를 S(i,t)로 나타낸다. t+1일 때의 상태는 다음과 같은 방정식을 통해 구할 수 있다.

S(i,t+1) = (A × S(i-1,t) + B × S(i,t) + C × S(i+1,t)) mod M

위의 식에서 A, B, C는 음이 아닌 정수이다. i<0 또는 N ≤ i인 경우에 S(i,t) = 0이다.

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

입력

각 테스트 케이스는 다음과 같은 형식으로 이루어져 있다.

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

0 < N ≤ 50, 0 < M ≤ 1000, 0 ≤ A,B,C < M, 0 ≤ T ≤ 109

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

출력

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

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

각 세포의 상태는 정수이고, 공백으로 구분되어야 한다.

예제 입력

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

힌트

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2012 in Tokyo C번

  • 잘못된 조건을 찾은 사람: august14
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: ntopia