結果
問題 | No.1667 Forest |
ユーザー | magurofly |
提出日時 | 2021-09-03 23:19:18 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,681 bytes |
コンパイル時間 | 1,926 ms |
コンパイル使用メモリ | 206,308 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-15 17:54:45 |
合計ジャッジ時間 | 4,348 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 2 ms
6,816 KB |
testcase_16 | AC | 1 ms
6,820 KB |
testcase_17 | WA | - |
ソースコード
#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 = int;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;}