CODE FESTIVAL 2016 Final

Submission #1051617

Source codeソースコード

import java.util.*;

public class Main {
	final static long MODULO = 1_000_000_000 + 7;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		long[][][] dp = new long[2][N + 2][N + 2];// [何日目][1を含む連結成分のサイズ][全体の訪れた町のサイズ]
		dp[0][1][1] = 1;
		for (int i = 0; i + 1 <= M; ++i) {
			dp[(i + 1) % 2] = new long[N + 2][N + 2];
			for (int j = 0; j <= N; ++j) {
				for (int k = j; k <= N; ++k) {
					dp[(i + 1) % 2][j][k] += dp[i % 2][j][k] * (k - j) % MODULO;
					if (dp[(i + 1) % 2][j][k] >= MODULO)
						dp[(i + 1) % 2][j][k] -= MODULO;
					dp[(i + 1) % 2][k][k] += dp[i % 2][j][k] * j % MODULO;
					if (dp[(i + 1) % 2][k][k] >= MODULO)
						dp[(i + 1) % 2][k][k] -= MODULO;
					dp[(i + 1) % 2][j][k + 1] += dp[i % 2][j][k] * (N - k) % MODULO;
					if (dp[(i + 1) % 2][k][k] >= MODULO)
						dp[(i + 1) % 2][j][k + 1] -= MODULO;
				}
			}
		}
		System.out.println(dp[M % 2][N][N]);
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Submission

Task問題 F - Road of the King
User nameユーザ名 fortoobye
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 1000
Source lengthソースコード長 1149 Byte
File nameファイル名
Exec time実行時間 687 ms
Memory usageメモリ使用量 81752 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 1000 / 1000 sample-01.txt,sample-02.txt,sample-03.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 124 ms 9812 KB
01-02.txt AC 124 ms 9680 KB
01-03.txt AC 126 ms 9796 KB
01-04.txt AC 145 ms 11848 KB
01-05.txt AC 135 ms 10064 KB
01-06.txt AC 246 ms 27628 KB
01-07.txt AC 614 ms 79072 KB
01-08.txt AC 687 ms 81444 KB
01-09.txt AC 636 ms 81244 KB
01-10.txt AC 636 ms 81752 KB
sample-01.txt AC 127 ms 9680 KB
sample-02.txt AC 304 ms 29032 KB
sample-03.txt AC 430 ms 50648 KB