結果
問題 |
No.827 総神童数
|
ユーザー |
![]() |
提出日時 | 2019-05-03 23:07:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 1,233 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 84,484 KB |
最終ジャッジ日時 | 2025-01-07 03:31:11 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <queue> #include <iostream> #include <vector> using namespace std; const long long mod = 1e9+7; long long mod_inv(long long x){ long long k = mod - 2, ret = 1; while(k){ if(k&1) ret *= x, ret %= mod; x *= x, x %= mod; k >>= 1; } return ret; } int main(){ int N; cin >> N; vector<vector<int>> G(N); for(int i = 0; i < N-1; ++i){ int u, v; cin >> u >> v; --u,--v; G[u].push_back(v); G[v].push_back(u); } vector<long long> F(N+2), F_(N+2); F[0] = 1; for(int i = 0; i <= N; ++i) F[i+1] = (i+1)*F[i]%mod; F_[N+1] = mod_inv(F[N+1]); for(int i = N+1; i > 0; --i) F_[i-1] = i*F_[i]%mod; auto f = [=](int a, int b){ if(a < b) return 0LL; return F[a]*F_[b]%mod*F_[a-b]%mod; }; auto g = [=](int k){ return F[k]*F[N-k-1]%mod*((f(N+1,k+1)+mod-f(N,k))%mod)%mod; }; queue<int> Q; Q.push(0); vector<int> D(N,-1); D[0] = 0; while(not Q.empty()){ int v = Q.front(); Q.pop(); for(auto v_ : G[v]){ if(D[v_] >= 0) continue; D[v_] = D[v]+1; Q.push(v_); } } long long ans = 0; for(int i = 0; i < N; ++i){ ans += g(D[i]); ans %= mod; } cout << ans << endl; }