結果
問題 | No.1667 Forest |
ユーザー |
|
提出日時 | 2021-09-03 23:19:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 796 ms / 3,000 ms |
コード長 | 1,687 bytes |
コンパイル時間 | 2,105 ms |
コンパイル使用メモリ | 199,188 KB |
最終ジャッジ日時 | 2025-01-24 07:11:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include <atcoder/all> // using namespace atcoder; #define rep(i, l, r) for (auto i = (l); i < (r); i++) #define all(a) a.begin(), a.end() #define chmin(dest, src) if ((dest) > (src)) dest = (src) #define chmax(dest, src) if ((dest) < (src)) dest = (src) using ll = long long; using i64 = long long; using i32 = long; using u64 = unsigned long long; using u32 = unsigned long; ll pow_mod(ll a, ll e, ll m) { ll r = 1; while (e != 0) { if (e & 1) r = r * a % m; a = a * a % m; e >>= 1; } return r; } int main() { ll N, MOD; cin >> N >> MOD; vector<ll> fac(N + 1); vector<ll> finv(N + 1); vector<ll> inv(N + 1); fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i <= N; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } auto comb = [&](ll n, ll k) -> ll { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; }; // http://oeis.org/A105599 // T[n][m] = n頂点でm本の木を作る場合の数 vector<vector<ll>> T(N + 1, vector<ll>(N + 1, 0)); T[0][0] = 1; rep (n, 1, N + 1) { rep (m, 1, n + 1) { rep (k, 1, n - m + 2) { if (k >= 2) { T[n][m] += comb(n - 1, k - 1) * pow_mod(k, k - 2, MOD) % MOD * T[n - k][m - 1] % MOD; T[n][m] %= MOD; } else { T[n][m] += T[n - k][m - 1]; T[n][m] %= MOD; } } } } rep (m, 0, N) { if (T[N][N - m] < 0) T[N][N - m] += MOD; cout << T[N][N - m] % MOD << "\n"; } return 0; }