Submission #3416433
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++) #define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++) #define int long long using namespace std; using II = pair<int, int>; using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>; const int MOD = 1e9 + 7; // MODにおける階乗とその逆元、事前計算O(N * log(MOD))、参照O(1) class FactMod { int MOD; int N; // x^a int pow(int x, int a) { if (a == 0) { return 1; } int half = pow(x, a / 2); return half * half % MOD * (a % 2 ? x : 1) % MOD; } public: VI fact; VI fact_inv; FactMod(int n = 0, int mod = 1e9 + 7) : N(n), MOD(mod) { fact = VI(N + 1); fact[0] = 1; REP (i, N) { fact[i + 1] = fact[i] * (i + 1) % MOD; } fact_inv = VI(N + 1); fact_inv[N] = inv(fact[N]); for (int i = N - 1; i >= 0; i--) { fact_inv[i] = fact_inv[i + 1] * (i + 1) % MOD; assert(fact_inv[i] * fact[i] % MOD == 1); } } // xの逆元 x^(MOD - 2) int inv(int x) { return pow(x, MOD - 2); } }; VVI G; FactMod fm; II dfs(int v, int prev) { int num = 1, sz = 0; for (int u: G[v]) if (u != prev) { II p = dfs(u, v); (num *= p.first) %= MOD; (num *= fm.fact_inv[p.second]) %= MOD; sz += p.second; } (num *= fm.fact[sz]) %= MOD; return {num, sz + 1}; } signed main() { int N; cin >> N; fm = FactMod(N); G = VVI(N); REP (i, N - 1) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } int ans = 0; REP (i, N) { (ans += dfs(i, -1).first) % MOD; } cout << ans * fm.fact_inv[2] % MOD << endl; }
Submission Info
Submission Time | |
---|---|
Task | N - 木 |
User | knshnb |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1726 Byte |
Status | WA |
Exec Time | 23 ms |
Memory | 384 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 5 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 06, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | WA | 23 ms | 384 KB |
01 | WA | 13 ms | 384 KB |
02 | WA | 16 ms | 256 KB |
03 | WA | 16 ms | 256 KB |
04 | WA | 16 ms | 384 KB |
05 | WA | 16 ms | 384 KB |
06 | WA | 16 ms | 256 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |