CODE FESTIVAL 2016 Final

Submission #1051613

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);
					dp[(i + 1) % 2][j][k] %= MODULO;
					dp[(i + 1) % 2][k][k] += dp[i % 2][j][k] * j;
					dp[(i + 1) % 2][k][k] %= MODULO;
					dp[(i + 1) % 2][j][k + 1] += dp[i % 2][j][k] * (N - k);
					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ソースコード長 988 Byte
File nameファイル名
Exec time実行時間 570 ms
Memory usageメモリ使用量 78944 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 126 ms 9676 KB
01-02.txt AC 128 ms 9680 KB
01-03.txt AC 125 ms 9812 KB
01-04.txt AC 146 ms 11728 KB
01-05.txt AC 135 ms 10060 KB
01-06.txt AC 211 ms 25952 KB
01-07.txt AC 542 ms 76140 KB
01-08.txt AC 570 ms 78568 KB
01-09.txt AC 565 ms 78312 KB
01-10.txt AC 567 ms 78944 KB
sample-01.txt AC 126 ms 9676 KB
sample-02.txt AC 267 ms 27232 KB
sample-03.txt AC 371 ms 47848 KB