結果
| 問題 |
No.827 総神童数
|
| コンテスト | |
| ユーザー |
 kusomushi
|
| 提出日時 | 2019-07-08 20:43:32 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 785 ms / 2,000 ms |
| コード長 | 7,150 bytes |
| コンパイル時間 | 2,647 ms |
| コンパイル使用メモリ | 79,476 KB |
| 実行使用メモリ | 71,260 KB |
| 最終ジャッジ日時 | 2024-10-09 12:49:17 |
| 合計ジャッジ時間 | 20,548 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
import java.io.*;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] A, B;
public static void main(String[] args) {
FastScanner sc = new FastScanner(System.in);
N = sc.nextInt();
A = new int[N-1];
B = new int[N-1];
for (int i = 0; i < N - 1; i++) {
A[i] = sc.nextInt()-1;
B[i] = sc.nextInt()-1;
}
System.out.println(solve());
}
static int solve() {
int[][] G = adjB(N, A, B);
int[] dist = new int[N];
for (Node node : order(N, G, 0, true)) {
for (int b : G[node.a]) {
if( b == node.parent ) continue;
dist[b] = dist[node.a] + 1;
}
}
int nFact = 1;
for (int i = 2; i <= N; i++) {
nFact = mul(i, nFact);
}
int ans = 0;
for (int i = 0; i < N; i++) {
int d = dist[i];
// N! / (d+1)
ans += div(nFact, d+1);
ans %= MOD;
}
return ans;
}
static int MOD = 1_000_000_007;
static int pow(int base, long exp) {
if( exp == 0 ) return 1;
int ans = 1;
base %= MOD;
while( exp > 0 ) {
if( (exp & 1) == 1 ) {
ans = mul(ans, base);
}
base = mul(base, base);
exp = exp >> 1;
}
return ans;
}
static int sub(int a, int b) {
int c = a - b;
if( c < 0 ) c += MOD;
return c;
}
static int div(int a, int b) {
return mul(a, pow(b, MOD-2));
}
static int add(int a, int b) {
int c = a + b;
if( c >= MOD ) c %= MOD;
return c;
}
static int mul(int a, int b) {
long c = (long)a * b;
if( c >= MOD ) c %= MOD;
return (int)c;
}
static class Node {
int parent, a;
public Node(int parent, int a) {
this.parent = parent;
this.a = a;
}
}
static Node[] order(int N, int[][] G, int root, boolean fromRoot) {
Node[] q = new Node[N];
int u = 0, v = 0;
Node[] ret = new Node[N];
int idx = fromRoot ? 0 : N-1;
int d = fromRoot ? 1 : -1;
q[v++] = new Node(-1, root);
while( u != v ) {
Node n = q[u++];
ret[idx] = n;
idx += d;
for (int b : G[n.a]) {
if( b == n.parent ) continue;
q[v++] = new Node(n.a, b);
}
}
return ret;
}
static int[][] adjB(int n, int[] from, int[] to) {
int[][] adj = new int[n][];
int[] cnt = new int[n];
for (int f : from) {
cnt[f]++;
}
for (int t : to) {
cnt[t]++;
}
for (int i = 0; i < n; i++) {
adj[i] = new int[cnt[i]];
}
for (int i = 0; i < from.length; i++) {
adj[from[i]][--cnt[from[i]]] = to[i];
adj[to[i]][--cnt[to[i]]] = from[i];
}
return adj;
}
@SuppressWarnings("unused")
static class FastScanner {
private BufferedReader reader;
private StringTokenizer tokenizer;
FastScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = null;
}
String next() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
String nextLine() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
long nextLong() {
return Long.parseLong(next());
}
int nextInt() {
return Integer.parseInt(next());
}
int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
int[] nextIntArray(int n, int delta) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt() + delta;
return a;
}
long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextLong();
return a;
}
}
static void writeLines(int[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (int a : as) pw.println(a);
pw.flush();
}
static void writeLines(long[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (long a : as) pw.println(a);
pw.flush();
}
static void writeSingleLine(int[] as) {
PrintWriter pw = new PrintWriter(System.out);
for (int i = 0; i < as.length; i++) {
if (i != 0) pw.print(" ");
pw.print(as[i]);
}
pw.println();
pw.flush();
}
static int max(int... as) {
int max = Integer.MIN_VALUE;
for (int a : as) max = Math.max(a, max);
return max;
}
static int min(int... as) {
int min = Integer.MAX_VALUE;
for (int a : as) min = Math.min(a, min);
return min;
}
static void debug(Object... args) {
StringJoiner j = new StringJoiner(" ");
for (Object arg : args) {
if (arg == null) j.add("null");
else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
else j.add(arg.toString());
}
System.err.println(j.toString());
}
static void printSingleLine(int[] array) {
PrintWriter pw = new PrintWriter(System.out);
for (int i = 0; i < array.length; i++) {
if (i != 0) pw.print(" ");
pw.print(array[i]);
}
pw.println();
pw.flush();
}
static int lowerBound(int[] array, int value) {
int lo = 0, hi = array.length, mid;
while (lo < hi) {
mid = (hi + lo) / 2;
if (array[mid] < value) lo = mid + 1;
else hi = mid;
}
return lo;
}
static int upperBound(int[] array, int value) {
int lo = 0, hi = array.length, mid;
while (lo < hi) {
mid = (hi + lo) / 2;
if (array[mid] <= value) lo = mid + 1;
else hi = mid;
}
return lo;
}
}