Submission #1051617


Source Code Expand

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 Info

Submission Time
Task F - Road of the King
User fortoobye
Language Java8 (OpenJDK 1.8.0)
Score 1000
Code Size 1149 Byte
Status AC
Exec Time 687 ms
Memory 81752 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 13
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
all 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
Case Name Status Exec Time Memory
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