Одновимірний клітинний автомат#5414

Одновимірний клітинний автомат

30 секунд

128 мегабайтів

Легка

Існує одномірний клітинний автомат, що складається з $N$ клітинок. Клітинки пронумеровані від $0$ до $N - 1$ N-1.

Кожна клітинка має стан, представлений як невід'ємне ціле число, менше ніж $M$ . Стани клітинок змінюються через дискретні кроки часу. Ми позначаємо стан $i$ -ї клітинки в момент часу $t$ як $S (i, t)$ S(i, t). Стан у момент часу $t + 1$ t+1 визначається рівнянням

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

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

де $A$ , $B$ та $C$ є невід'ємними цілими константами. Для $i < 0$ i < 0 або $N \leq i$ N \le i, ми визначаємо $S (i, t) = 0$ S(i, t) = 0.

Маючи визначення автомата та початкові стани клітинок, ваше завдання - написати програму, яка обчислює стани клітинок у заданий момент часу $T$ .

Вхідні дані

Вхідні дані складаються з кількох наборів. Кожен набір даних має такий формат:

$N$ $M$ $A$ $B$ $C$ $T$

$S (0, 0)$ S(0, 0) $S (1, 0)$ S(1, 0) $\dots$ $S (N - 1, 0)$ S(N-1, 0)

Перший рядок набору даних містить шість цілих чисел: $N$ , $M$ , $A$ , $B$ , $C$ та $T$ . $N$ - це кількість клітинок. $M$ - це модуль у рівнянні (1). $A$ , $B$ та $C$ - коефіцієнти у рівнянні (1). Нарешті, $T$ - це час, для якого потрібно обчислити стани.

Ви можете припустити, що $0 < N \leq 50$ 0 < N \le 50, $0 < M \leq 1000$ 0 < M \le 1000, $0 \leq A, B, C < M$ 0 \le A, B, C < M та $0 \leq T \leq 1 0^{9}$ 0 \le T \le 10^9.

Другий рядок складається з $N$ цілих чисел, кожне з яких є невід'ємним і менше ніж $M$ . Вони представляють стани клітинок у момент часу нуль.

Рядок, що містить шість нулів, вказує на кінець введення.

Вихідні дані

Для кожного набору даних виведіть рядок, що містить стани клітинок у момент часу $T$ . Формат виводу такий:

$S (0, T)$ S(0, T) $S (1, T)$ S(1, T) $\dots$ $S (N - 1, T)$ S(N-1, T)

Кожен стан має бути представлений як ціле число, а числа мають бути розділені пробілом.

Приклади

Приклад 1