結果
問題 |
No.827 総神童数
|
ユーザー |
![]() |
提出日時 | 2019-05-03 22:51:32 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 254 ms / 2,000 ms |
コード長 | 2,987 bytes |
コンパイル時間 | 1,263 ms |
コンパイル使用メモリ | 115,040 KB |
実行使用メモリ | 21,348 KB |
最終ジャッジ日時 | 2024-12-31 18:51:35 |
合計ジャッジ時間 | 7,019 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <iostream> #include <algorithm> #include <bitset> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <cstring> #include <utility> #include <vector> #include <complex> #include <valarray> #include <fstream> #include <cassert> #include <cmath> #include <functional> #include <iomanip> #include <numeric> #include <climits> #include <random> #define _overload(a, b, c, d, ...) d #define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X)) #define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X)) #define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__) #define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X)) #define all(X) (X).begin(),(X).end() #define len(X) ((int)(X).size()) #define mod(n, m) (((n)%(m)+(m))%m) #define fi first #define sc second using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> Pii; typedef pair<ll,ll> Pll; const int INFINT = 1 << 30; // 1.07x10^ 9 const ll INFLL = 1LL << 60; // 1.15x10^18 const double EPS = 1e-10; const int MOD = 1000000007; const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; const int MAX_N = 200000; int N; int u[MAX_N], v[MAX_N]; int depth[MAX_N]; struct edge { int to, cost; }; const int MAX_V = MAX_N, INF = 1e9; // Vの初期化を忘れない。 int V; vector<edge> G[MAX_V]; int d[MAX_V]; void add_edge(int v, int u, int cost) { G[v].push_back((edge){u, cost}); G[u].push_back((edge){v, cost}); } void dijkstra(int s) { fill(d, d+V, INF); priority_queue<Pii, vector<Pii>, greater<Pii> > pque; d[s] = 1; pque.push(Pii(1, s)); while (!pque.empty()) { Pii p = pque.top(); pque.pop(); int v = p.second; if (d[v] < p.first) continue; for (int i = 0; i < (int)G[v].size(); ++i) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; pque.push(Pii(d[v]+ e.cost, e.to)); } } } } ll fact[MAX_N+1]; ll inv_fact[MAX_N+1]; //整数a,bに対し、ax + by = gcd(a,b) を満たす整数x,y,gcd(a,b) を計算する ll extgcd(ll a, ll b, ll& x, ll& y) { ll d = a; if (b != 0) { d = extgcd(b, a%b, y, x); y -= (a/b) * x; } else { x = 1; y = 0; } return d; } //ax ≡ gcd(a,m) (mod m) を満たすxを計算する。 ll mod_inverse(ll a, ll m) { ll x, y; extgcd(a, m, x, y); return (m + x%m) % m; } void init(ll n, ll mod) { fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = (fact[i-1]*i)%mod; for (int i = 0; i <= n; ++i) inv_fact[i] = mod_inverse(fact[i], mod); } int main() { std::ios::sync_with_stdio(false);std::cin.tie(0); cin >> N; init(N, MOD); V = N; rep(i, N-1) cin >> u[i] >> v[i]; rep(i, N-1) { add_edge(--u[i], --v[i], 1); } dijkstra(0); ll ans = 0; for (int i = 0; i < N; ++i) { ans = mod(ans + fact[N]*mod_inverse(d[i],MOD)%MOD, MOD); } cout << ans << endl; return 0; }