結果

問題 No.827 総神童数
ユーザー ks2mks2m
提出日時 2019-05-03 23:12:12
言語 Java21
(openjdk 21)
結果
RE  
実行時間 -
コード長 1,960 bytes
コンパイル時間 3,274 ms
コンパイル使用メモリ 80,652 KB
実行使用メモリ 129,284 KB
最終ジャッジ日時 2023-08-30 06:38:24
合計ジャッジ時間 8,785 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
56,212 KB
testcase_01 AC 122 ms
56,368 KB
testcase_02 AC 127 ms
55,608 KB
testcase_03 AC 121 ms
56,360 KB
testcase_04 AC 122 ms
56,024 KB
testcase_05 AC 125 ms
55,900 KB
testcase_06 AC 122 ms
55,816 KB
testcase_07 RE -
testcase_08 AC 126 ms
55,864 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
		for (int i = 0; i < n - 1; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();

			List<Integer> list1 = map.get(u);
			if (list1 == null) {
				list1 = new ArrayList<Integer>();
				map.put(u, list1);
			}
			list1.add(v);

			List<Integer> list2 = map.get(v);
			if (list2 == null) {
				list2 = new ArrayList<Integer>();
				map.put(v, list2);
			}
			list2.add(u);
		}
		sc.close();

		int[] dep = new int[n + 1];
		Queue<Integer> que = new ArrayDeque<Integer>();
		que.add(1);
		dep[1] = 1;
		while (!que.isEmpty()) {
			Integer cur = que.poll();
			List<Integer> list = map.get(cur);
			for (Integer next : list) {
				if (dep[next] == 0) {
					que.add(next);
					dep[next] = dep[cur] + 1;
				}
			}
		}

		TreeMap<Integer, Integer> depMap = new TreeMap<Integer, Integer>();
		for (int i = 1; i <= n; i++) {
			int key = dep[i];
			if (depMap.containsKey(key)) {
				depMap.put(key, depMap.get(key) + 1);
			} else {
				depMap.put(key, 1);
			}
		}

		int mod = 1000000007;
		long p = 1;
		int i = 1;
		long ans = 0;
		while (!depMap.isEmpty()) {
			Entry<Integer, Integer> ent = depMap.pollLastEntry();
			int k = ent.getKey();
			int v = ent.getValue();
			for ( ; i <= n - k; i++) {
				p *= i;
				p %= mod;
			}
			long npr = nPr(n, k);
			ans += npr * p / k % mod * v % mod;
			ans %= mod;
		}
		System.out.println(ans);
	}

	static long nPr(long n, long r) {
		long m = 1000000007;
		long val = 1;
		for (int i = 1; i <= r; i++) {
			val = val * (n - i + 1) % m;
		}
		return val;
	}
}
0