結果
問題 | No.758 VVVVV |
ユーザー |
![]() |
提出日時 | 2018-12-10 20:53:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 2,141 bytes |
コンパイル時間 | 1,177 ms |
コンパイル使用メモリ | 113,540 KB |
実行使用メモリ | 11,884 KB |
最終ジャッジ日時 | 2024-10-14 01:48:32 |
合計ジャッジ時間 | 3,039 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>using namespace std;typedef long long ll;typedef unsigned int ui;const ll mod = 1000000007;const ll INF = (ll)1000000007 * 1000000007;typedef pair<int, int> P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef long double ld;typedef complex<ld> Point;const ld eps = 1e-11;const ld pi = acos(-1.0);typedef pair<ll, ll> LP;typedef pair<ld, ld> LDP;typedef unsigned long long ul;//x,yがax+by=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;}//aのmod mでの逆元を求めるll mod_inverse(ll a, ll m) {ll x, y;extgcd(a, m, x, y);return (m + x % m) % m;}const int N_MAX = 1 << 18;ll p[N_MAX];void init() {p[0] = 1;rep1(i, N_MAX - 1) {p[i] = p[i - 1] * i%mod;}}//xCyを求めるll comb(ll x, ll y, ll m) {if (x < y)return 0;ll res = p[x];(res *= mod_inverse(p[y], m)) %= mod;(res *= mod_inverse(p[x - y], m)) %= mod;return res;}vector<int> G[1 << 17];bool used[1 << 17];int dfs(int id) {used[id] = true;if (G[id].size() == 1&&used[G[id][0]])return 1;int res = 0;rep(j, G[id].size()) {int to = G[id][j];if (used[to])continue;res += dfs(to);}return res;}int main() {int n; cin >> n; init();if (n == 1) {cout << 1 << endl; return 0;}rep(i, n-1) {int a, b; cin >> a >> b; a--; b--;G[a].push_back(b);G[b].push_back(a);}int t = dfs(0); //cout << t << endl;ll out = comb(n - 1, t - 1, mod)*comb(n - 2, t - 1, mod) % mod*mod_inverse(t, mod) % mod;cout << out << endl;return 0;}