Submission #6423123
Source Code Expand
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<ll, ll> P; const ll MOD = 1e9 + 7; vector<int> G[1000]; const int MAX_N = 1000; ll fact[MAX_N + 1]; ll inv_fact[MAX_N + 1]; ll mod_pow(ll a,ll n) { if (n == 0) return 1; if (n % 2 == 0) { ll tmp = mod_pow(a, n / 2); return (tmp*tmp) % MOD; } return a*mod_pow(a, n - 1) % MOD; } void comb_init(int n) { fact[0] = inv_fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i - 1] * i%MOD; inv_fact[i] = inv_fact[i - 1] * mod_pow(i, MOD - 2) % MOD; } } ll comb(int n, int k) { if (n < k) return 0; ll ret = fact[n]; (ret *= inv_fact[k]) %= MOD; (ret *= inv_fact[n - k]) %= MOD; return ret; } P dfs(int v, int p) { vector<P> child; ll ret = 1; int sum = 0; for (int to : G[v]) { if (to == p) continue; child.push_back(dfs(to, v)); (ret *= child.back().first) %= MOD; sum += child.back().second + 1; } int rest = sum; for (int i = 0; i < child.size(); i++) { (ret *= comb(rest, child[i].second + 1)) %= MOD; rest -= child[i].second + 1; } return P(ret, sum); } int main() { int N; cin >> N; vector<P> edge; for (int i = 0; i + 1 < N; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); edge.emplace_back(a, b); } comb_init(N); ll ans = 0; for (P e : edge) { P p1 = dfs(e.first, e.second); P p2 = dfs(e.second, e.first); int sum = p1.second + p2.second; ll tmp = p1.first*p2.first%MOD; (tmp *= comb(sum, p1.second)) %= MOD; (ans += tmp) %= MOD; } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | N - 木 |
User | Div9851 |
Language | C++14 (GCC 5.4.1) |
Score | 5 |
Code Size | 1647 Byte |
Status | AC |
Exec Time | 82 ms |
Memory | 384 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 5 / 5 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 06, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 65 ms | 384 KB |
01 | AC | 20 ms | 384 KB |
02 | AC | 72 ms | 384 KB |
03 | AC | 73 ms | 384 KB |
04 | AC | 69 ms | 384 KB |
05 | AC | 74 ms | 384 KB |
06 | AC | 82 ms | 384 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |