読者です 読者をやめる 読者になる 読者になる

AOJ 1327: One-Dimensional Cellular Automaton

競技プログラミング AOJ

問題

One-Dimensional Cellular Automaton | Aizu Online Judge

 S_{t+1} S_{t}の漸化式が与えられるので、 S_{0}から S_{T}を求める。

解法

D =
\large\left(
\begin{array}{ccccc}
B&C&0&\cdots&0\\
A&B&C&\cdots&0\\
0&A&B&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&\cdots&B \end{array}\right)

上のような行列Dを考える。問題の操作は下の式のようになるので、最初の状態に行列DをT回かければ良い。


\large\left(
\begin{array}{c}
S_{0, t+1}\\
S_{1, t+1}\\
S_{2, t+1}\\
\vdots\\
S_{N-1, t+1}
 \end{array}\right)
=
\large\left(
\begin{array}{ccccc}
B&C&0&\cdots&0\\
A&B&C&\cdots&0\\
0&A&B&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&\cdots&B \end{array}\right)

\large\left(
\begin{array}{c}
S_{0, t}\\
S_{1, t}\\
S_{2, t}\\
\vdots\\
S_{N-1, t}
 \end{array}\right)

よって S_{T} = D^{T}S_{0}を考える。

 T=10^{9}などの計算はまともにループすると絶対に間に合わないので、 D^{T}S_{0} = D^{1}D^{2}D^{4}\cdots D^{2^{n}}S_{0}のようにTを2の累乗の和に分解して考える。 T<2^{30}より、ループは30のオーダーで済むことが分かる。

コード

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int N = sc.nextInt();
			if (N == 0) {
				sc.close();
				break;
			}
			int M = sc.nextInt();
			int A = sc.nextInt();
			int B = sc.nextInt();
			int C = sc.nextInt();
			int T = sc.nextInt();

			// 行列をつくる
			// D[n]にはD[0]を2^n乗した行列が入ってる
			int[][][] D = new int[30][N + 2][N + 2];
			for (int i = 1; i <= N; ++i) {
				D[0][i][i - 1] = C;
				D[0][i][i] = B;
				D[0][i][i + 1] = A;
			}

			for (int n = 1; (1 << n) <= T; ++n) {
				for (int i = 1; i <= N; ++i) {
					for (int j = 1; j <= N; ++j) {
						for (int l = 1; l <= N; ++l) {
							D[n][i][j] += D[n - 1][i][l] * D[n - 1][l][j];
						}
						D[n][i][j] %= M;
					}
				}
			}

			int[][] c = new int[2][N + 2];
			for (int i = 1; i <= N; ++i) {
				c[0][i] = sc.nextInt();
			}

			int p = 0;
			for (int n = 0; (1 << n) <= T; ++n) {
				if ((T & (1 << n)) != 0) {
					for (int i = 1; i <= N; ++i) {
						c[1 - p][i] = 0;
					}
					for (int i = 1; i <= N; ++i) {
						for (int j = 1; j <= N; ++j) {
							c[1 - p][j] += c[p][i] * D[n][i][j];
						}
					}
					for (int i = 1; i <= N; ++i) {
						c[1 - p][i] %= M;
					}
					p = 1 - p;
				}
			}

			for (int i = 0; i < N; ++i) {
				if (i != 0) {
					System.out.print(" ");
				}
				System.out.print(c[p][i + 1]);
			}
			System.out.println();
		}
	}
}