AOJ 1327: One-Dimensional Cellular Automaton

問題

One-Dimensional Cellular Automaton | Aizu Online Judge

との漸化式が与えられるので、からを求める。

解法

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

よってを考える。

などの計算はまともにループすると絶対に間に合わないので、のようにTを2の累乗の和に分解して考える。より、ループは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();
		}
	}
}