結果
問題 | No.1667 Forest |
ユーザー | packer_jp |
提出日時 | 2021-09-03 22:21:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 751 ms / 3,000 ms |
コード長 | 5,098 bytes |
コンパイル時間 | 2,509 ms |
コンパイル使用メモリ | 208,084 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-09 04:46:08 |
合計ジャッジ時間 | 7,796 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 751 ms
5,248 KB |
testcase_01 | AC | 744 ms
5,376 KB |
testcase_02 | AC | 728 ms
5,376 KB |
testcase_03 | AC | 8 ms
5,376 KB |
testcase_04 | AC | 721 ms
5,376 KB |
testcase_05 | AC | 430 ms
5,376 KB |
testcase_06 | AC | 263 ms
5,376 KB |
testcase_07 | AC | 162 ms
5,376 KB |
testcase_08 | AC | 79 ms
5,376 KB |
testcase_09 | AC | 47 ms
5,376 KB |
testcase_10 | AC | 25 ms
5,376 KB |
testcase_11 | AC | 4 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(a) (a).begin(), (a).end() using ll = long long; using ull = unsigned long long; using vll = vector<ll>; ull bit(int n) { return 1ull << n; } ll sign(ll a) { return (a > 0) - (a < 0); } ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } ll cdiv(ll a, ll b) { return -fdiv(-a, b); } template <typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; template <typename T> T sq(const T &a) { return a * a; } template <typename T, typename U> bool chmax(T &a, const U &b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T, typename U> bool chmin(T &a, const U &b) { return ((a > b) ? (a = b, true) : (false)); } template <typename T> ostream &operator<<(ostream &os, const vector<T> &a) { os << "("; for (auto itr = a.begin(); itr != a.end(); itr++) { os << *itr << (next(itr) != a.end() ? ", " : ""); } os << ")"; return os; } #ifdef ONLINE_JUDGE #define dump(...) (void(0)) #else void debug() { cerr << endl; } template <typename Head, typename... Tail> void debug(Head &&head, Tail &&... tail) { cerr << head; if (sizeof...(Tail)) cerr << ", "; debug(tail...); } #define dump(...) cerr << __LINE__ << ": " << #__VA_ARGS__ << " = ", debug(__VA_ARGS__) #endif struct rep { struct itr { int v; itr(int v) : v(v) {} void operator++() { ++v; } int operator*() const { return v; } bool operator!=(const itr &i) const { return v != i.v; } }; int l, r; rep(int r) : l(min(0, r)), r(r) {} rep(int l, int r) : l(min(l, r)), r(r) {} itr begin() const { return l; }; itr end() const { return r; }; }; struct per { struct itr { int v; itr(int v) : v(v) {} void operator++() { --v; } int operator*() const { return v; } bool operator!=(const itr &i) const { return v != i.v; } }; int l, r; per(int r) : l(min(0, r)), r(r) {} per(int l, int r) : l(min(l, r)), r(r) {} itr begin() const { return r - 1; }; itr end() const { return l - 1; }; }; ll MOD; struct modint { ll val; modint(ll val = 0) : val(val >= 0 ? val % MOD : (MOD - (-val) % MOD) % MOD) {} static ll mod() { return MOD; } modint inv() const { ll a = val, b = MOD, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return modint(u); } modint pow(ll k) const { modint ret = 1, mul = val; while (k) { if (k & 1) ret *= mul; mul *= mul; k >>= 1; } return ret; } modint &operator+=(const modint &a) { if ((val += a.val) >= MOD) val -= MOD; return *this; } modint &operator-=(const modint &a) { if ((val += MOD - a.val) >= MOD) val -= MOD; return *this; } modint &operator*=(const modint &a) { (val *= a.val) %= MOD; return *this; } modint &operator/=(const modint &a) { return *this *= a.inv(); } bool operator==(const modint &a) const { return val == a.val; } bool operator!=(const modint &a) const { return rel_ops::operator!=(*this, a); } modint operator+() const { return *this; } modint operator-() const { return modint(-val); } friend modint operator+(const modint &a, const modint &b) { return modint(a) += b; } friend modint operator-(const modint &a, const modint &b) { return modint(a) -= b; } friend modint operator*(const modint &a, const modint &b) { return modint(a) *= b; } friend modint operator/(const modint &a, const modint &b) { return modint(a) /= b; } friend istream &operator>>(istream &is, modint &a) { ll val; is >> val; a = modint(val); return is; } friend ostream &operator<<(ostream &os, const modint &a) { return os << a.val; } }; using mint = modint; template <typename mint> struct combination { vector<mint> fact, finv, inv; combination(int n) : fact(n + 1), finv(n + 1), inv(n + 1) { fact[0] = fact[1] = finv[0] = finv[1] = inv[1] = 1; for (int i : rep(2, n + 1)) { fact[i] = fact[i - 1] * i; inv[i] = -inv[mint::mod() % i] * (mint::mod() / i); finv[i] = finv[i - 1] * inv[i]; } } mint P(int n, int r) { return r < 0 || n < r ? 0 : (fact[n] * finv[n - r]); } mint C(int n, int r) { return P(n, r) * finv[r]; } mint H(int n, int r) { return C(n + r - 1, r); } mint catalan(int n) { return C(2 * n, n) / (n + 1); } }; int main() { ll m; cin >> m >> MOD; combination<mint> comb(m); vector<mint> cayley(m + 1, 1); for (ll i : rep(2, m + 1)) cayley[i] = mint(i).pow(i - 2); vector dp(m + 1, vector<mint>(m + 1)); dp[0][m] = 1; for (ll i : rep(m)) { for (ll j : rep(1, m + 1)) { for (ll k : rep(1, j + 1)) { dp[i + 1][j - k] += dp[i][j] * comb.C(j - 1, k - 1) * cayley[k]; } } } for (ll i : rep(m)) { cout << dp[m - i][0] << endl; } }