結果
問題 | No.758 VVVVV |
ユーザー |
|
提出日時 | 2018-12-06 00:31:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,409 bytes |
コンパイル時間 | 670 ms |
コンパイル使用メモリ | 80,464 KB |
最終ジャッジ日時 | 2025-03-14 22:41:48 |
合計ジャッジ時間 | 1,694 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘T pow_(T, T, T)’: main.cpp:19:5: error: ‘uint64_t’ was not declared in this scope 19 | uint64_t u = 1, xx = x; | ^~~~~~~~ main.cpp:8:1: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’? 7 | #include <queue> +++ |+#include <cstdint> 8 | main.cpp:21:18: error: ‘u’ was not declared in this scope 21 | if (n&1) u = u * xx % M; | ^ main.cpp:21:26: error: ‘xx’ was not declared in this scope; did you mean ‘x’? 21 | if (n&1) u = u * xx % M; | ^~ | x main.cpp:22:9: error: ‘xx’ was not declared in this scope; did you mean ‘x’? 22 | xx = xx * xx % M; | ^~ | x main.cpp:25:27: error: ‘u’ was not declared in this scope 25 | return static_cast<T>(u); | ^ main.cpp: At global scope: main.cpp:30:12: error: ‘uint64_t’ was not declared in this scope 30 | vector<uint64_t> facts, factinv; | ^~~~~~~~ main.cpp:30:12: note: ‘uint64_t’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’? main.cpp:30:20: error: template argument 1 is invalid 30 | vector<uint64_t> facts, factinv; | ^ main.cpp:30:20: error: template argument 2 is invalid main.cpp: In constructor ‘Factorial<T>::Factorial(int, T)’: main.cpp:34:14: error: invalid types ‘int[int]’ for array subscript 34 | facts[0] = 1; | ^ main.cpp:35:44: error: invalid types ‘int[int]’ for array subscript 35 | for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1]*i % mod; | ^ main.cpp:35:55: error: invalid types ‘int[int]’ for array subscript 35 | for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1]*i % mod; |
ソースコード
#include <limits> #include <iostream> #include <algorithm> #include <vector> #include <iomanip> #include <map> #include <queue> static const int MOD = 1000000007; using ll = long long; using u32 = unsigned; using namespace std; template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208; template <class T> T pow_ (T x, T n, T M){ uint64_t u = 1, xx = x; while (n > 0){ if (n&1) u = u * xx % M; xx = xx * xx % M; n >>= 1; } return static_cast<T>(u); }; template <class T> class Factorial { T mod; vector<uint64_t> facts, factinv; public: Factorial(int n, T mod) : facts(static_cast<u32>(n+1)), factinv(static_cast<u32>(n+1)), mod(mod) { facts[0] = 1; for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1]*i % mod; factinv[n] = pow_(facts[n], static_cast<uint64_t>(mod - 2), static_cast<uint64_t>(mod)); for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * (i+1) % mod; } T fact(int k) const { return static_cast<T>(facts[k]); } T operator[](const int &k) const { return static_cast<T>(facts[k]); } T C(int p, int q) const { if(q < 0 || p < q) return 0; return static_cast<T>(facts[p]* factinv[q] % mod * factinv[p-q] % mod); } T P(int p, int q) const { if(q < 0 || p < q) return 0; return static_cast<T>((facts[p] * factinv[p-q]) % mod); } T H(int p, int q) const { if(p < 0 || q < 0) return 0; return static_cast<T>(q == 0 ? 1 : C(p+q-1, q)); } }; template<typename T> T extgcd(T a, T b, T &x ,T &y){ for (T u = y = 1, v = x = 0; a; ) { ll q = b/a; swap(x -= q*u, u); swap(y -= q*v, v); swap(b -= q*a, a); } return b; } template<typename T> T mod_inv(T x, T m){ T s, t; extgcd(x, m, s, t); return (m+s)% m; } int main() { int n; cin >> n; if(n == 1) { cout << 1 << "\n"; return 0; } vector<vector<int>> child(n); for (int i = 0; i < n-1; ++i) { int a, b; cin >> a >> b; if(a > b) swap(a, b); child[a-1].emplace_back(b-1); } int k = 0; for (int i = 0; i < n; ++i) { if(child[i].empty()) k++; } Factorial<ll> f(n, MOD); cout << ((f.C(n-2, k-1) * f.C(n-1, k-1)) % MOD)*mod_inv(k, MOD) % MOD << "\n"; return 0; }