시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3281578244.809%

문제

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)

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

예제 입력 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

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjM4MjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3N2NcdWNjMjhcdWM2ZDAgXHVjMTM4XHVkM2VjIFx1Yzc5MFx1YjNkOVx1Yzc5MCIsImRlc2NyaXB0aW9uIjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWMxMzhcdWQzZWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1Yzc3Y1x1Y2MyOFx1YzZkMCBcdWMxMzhcdWQzZWMgXHVjNzkwXHViM2Q5XHVjNzkwKENlbGx1bGFyIEF1dG9tYXRvbilcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWMxMzhcdWQzZWNcdWIyOTQgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBOLTFcdWJjODhcdWFjMDBcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWMxMzhcdWQzZWNcdWIyOTQgXHVjMGMxXHVkMGRjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1ZDBkY1x1YjI5NCBNXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjMTM4XHVkM2VjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgMVx1YzUyOSBcdWM5YzBcdWIwYTBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjOWM0XHVkNjU0XHVkNTVjXHViMmU0LiBcdWMyZGNcdWFjMDQgdFx1YzVkMFx1YzExYyBpXHViYzg4XHVjOWY4IFx1YzEzOFx1ZDNlY1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgUyhpLHQpXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gdCsxXHVjNzdjIFx1YjU0Y1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWM4MTVcdWMyZGRcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5TKGksdCsxKSA9IChBICZ0aW1lczsgUyhpLTEsdCkgKyBCICZ0aW1lczsgUyhpLHQpICsgQyAmdGltZXM7IFMoaSsxLHQpKSBtb2QgTTxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVjMmRkXHVjNWQwXHVjMTFjIEEsIEIsIENcdWIyOTQgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIGkmbHQ7MCBcdWI2MTBcdWIyOTQgTiAmbGU7IGlcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFMoaSx0KSA9IDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3Y1x1Y2MyOFx1YzZkMCBcdWMxMzhcdWQzZWMgXHVjNzkwXHViM2Q5XHVjNzkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMmRjXHVhYzA0XHVjNzc0IFRcdWI5Y2NcdWQwN2MgXHVjOWMwXHViMDljIFx1YjRhNCwgXHVjMTM4XHVkM2VjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbk4gTSBBIEIgQyBUXHJcblMoMCwwKSBTKDEsMCkgLi4uIFMoTi0xLDApPFwvcHJlPlxyXG5cclxuPHA+MCAmbHQ7IE4gJmxlOyA1MCwgMCAmbHQ7IE0gJmxlOyAxMDAwLCAwICZsZTsgQSxCLEMgJmx0OyBNLCAwICZsZTsgVCAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzVlY1x1YzEyZiBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMmRjXHVhYzA0IFRcdWM1ZDBcdWMxMWMgXHVjMTM4XHVkM2VjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuUygwLFQpIFMoMSxUKSAuLi4gUyhOLTEsVCk8XC9wcmU+XHJcblxyXG48cD5cdWFjMDEgXHVjMTM4XHVkM2VjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWFjZTAsIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM4MjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPbmUtRGltZW5zaW9uYWwgQ2VsbHVsYXIgQXV0b21hdG9uIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIG9uZS1kaW1lbnNpb25hbCBjZWxsdWxhciBhdXRvbWF0b24gY29uc2lzdGluZyBvZiBOIGNlbGxzLiBDZWxscyBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIE4gLSAxLjxcL3A+XHJcblxyXG48cD5FYWNoIGNlbGwgaGFzIGEgc3RhdGUgcmVwcmVzZW50ZWQgYXMgYSBub24tbmVnYXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gTS4gVGhlIHN0YXRlcyBvZiBjZWxscyBldm9sdmUgdGhyb3VnaCBkaXNjcmV0ZSB0aW1lIHN0ZXBzLiBXZSBkZW5vdGUgdGhlIHN0YXRlIG9mIHRoZSBpLXRoIGNlbGwgYXQgdGltZSB0IGFzIFMoaSwgdCkuIFRoZSBzdGF0ZSBhdCB0aW1lIHQgKyAxIGlzIGRlIG5lZCBieSB0aGUgZXF1YXRpb248XC9wPlxyXG5cclxuPHA+UyhpLHQrMSkgPSAoQSAmdGltZXM7IFMoaS0xLHQpICsgQiAmdGltZXM7IFMoaSx0KSArIEMgJnRpbWVzOyBTKGkrMSx0KSkgbW9kIE0gKDEpPFwvcD5cclxuXHJcbjxwPndoZXJlIEEsIEIgYW5kIEMgYXJlIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIGNvbnN0YW50cy4gRm9yIGkgJmx0OyAwIG9yIE4gJmxlOyBpLCB3ZSBkZSBuZSBTKGksIHQpID0gMC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gYXV0b21hdG9uIGRlIG5pdGlvbiBhbmQgaW5pdGlhbCBzdGF0ZXMgb2YgY2VsbHMsIHlvdXIgbWlzc2lvbiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjb21wdXRlcyB0aGUgc3RhdGVzIG9mIHRoZSBjZWxscyBhdCBhIHNwZWNpIGVkIHRpbWUgVC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGRhdGFzZXRzLiBFYWNoIGRhdGFzZXQgaXMgZm9ybWF0dGVkIGFzIGZvbGxvd3MuPFwvcD5cclxuPHByZT5cclxuTiBNIEEgQiBDIFRcclxuUygwLDApIFMoMSwwKSAuLi4gUyhOLTEsMCk8XC9wcmU+XHJcblxyXG5cclxuPHA+VGhlIGZpIHJzdCBsaW5lIG9mIGEgZGF0YXNldCBjb25zaXN0cyBvZiBzaXggaW50ZWdlcnMsIG5hbWVseSBOLCBNLCBBLCBCLCBDIGFuZCBULiBOIGlzIHRoZSBudW1iZXIgb2YgY2VsbHMuIE0gaXMgdGhlIG1vZHVsdXMgaW4gdGhlIGVxdWF0aW9uICgxKS4gQSwgQiBhbmQgQyBhcmUgY29lXHVmYjAzY2llbnRzIGluIHRoZSBlcXVhdGlvbiAoMSkuIEZpbmFsbHksIFQgaXMgdGhlIHRpbWUgZm9yIHdoaWNoIHlvdSBzaG91bGQgY29tcHV0ZSB0aGUgc3RhdGVzLjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IDAgJmx0OyBOICZsZTsgNTAsIDAgJmx0OyBNICZsZTsgMTAwMCwgMCAmbGU7IEEsIEIsIEMgJmx0OyBNIGFuZCAwICZsZTsgVCAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29uc2lzdHMgb2YgTiBpbnRlZ2VycywgZWFjaCBvZiB3aGljaCBpcyBub24tbmVnYXRpdmUgYW5kIGxlc3MgdGhhbiBNLiBUaGV5IHJlcHJlc2VudCB0aGUgc3RhdGVzIG9mIHRoZSBjZWxscyBhdCB0aW1lIHplcm8uPFwvcD5cclxuXHJcbjxwPkEgbGluZSBjb250YWluaW5nIHNpeCB6ZXJvcyBpbmRpY2F0ZXMgdGhlIGVuZCBvZiB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgb3V0cHV0IGEgbGluZSB0aGF0IGNvbnRhaW5zIHRoZSBzdGF0ZXMgb2YgdGhlIGNlbGxzIGF0IHRpbWUgVC4gVGhlIGZvcm1hdCBvZiB0aGUgb3V0cHV0IGlzIGFzIGZvbGxvd3MuPFwvcD5cclxuPHByZT5cclxuUygwLFQpIFMoMSxUKSAuLi4gUyhOLTEsVCk8XC9wcmU+XHJcbjxwPkVhY2ggc3RhdGUgbXVzdCBiZSByZXByZXNlbnRlZCBhcyBhbiBpbnRlZ2VyIGFuZCB0aGUgaW50ZWdlcnMgbXVzdCBiZSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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