結果

問題 No.1667 Forest
ユーザー sapphire__15sapphire__15
提出日時 2021-09-04 13:29:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 646 ms / 3,000 ms
コード長 2,578 bytes
コンパイル時間 1,282 ms
コンパイル使用メモリ 135,888 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-22 20:55:08
合計ジャッジ時間 6,586 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 646 ms
4,380 KB
testcase_01 AC 641 ms
4,376 KB
testcase_02 AC 629 ms
4,380 KB
testcase_03 AC 7 ms
4,380 KB
testcase_04 AC 621 ms
4,380 KB
testcase_05 AC 372 ms
4,380 KB
testcase_06 AC 228 ms
4,380 KB
testcase_07 AC 139 ms
4,380 KB
testcase_08 AC 68 ms
4,376 KB
testcase_09 AC 40 ms
4,380 KB
testcase_10 AC 21 ms
4,380 KB
testcase_11 AC 4 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <cmath>
#include <complex>
#include <functional>
#include <cassert>
#include <stack>
#include <numeric>
#include <iomanip>
#include <limits>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <cstring>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> Pdd;

#define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++)
#define all(_l) _l.begin(), _l.end()
#define rall(_l) _l.rbegin(), _l.rend()
#define MM << " " <<

template<typename _T>
using MaxHeap = std::priority_queue<_T>;
template<typename _T>
using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>;

template<typename _T>
inline bool chmax(_T &_l, const _T _b) {
    if (_b > _l) {
        _l = _b;
        return true;
    }
    return false;
}
template<typename _T>
inline bool chmin(_T &_l, const _T _b) {
    if (_l > _b) {
        _l = _b;
        return true;
    }
    return false;
}

template<typename _T>
void vdeb(const std::vector<_T> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        if (i == bb.size() - 1) std::cout << bb[i];
        else std::cout << bb[i] << ' ';
    }
    std::cout << '\n';
}
template<typename _T>
void vdeb(const std::vector<std::vector<_T>> &bb) {
    for (unsigned int i = 0;i < bb.size();i++) {
        std::cout << i << ": ";
        vdeb(bb[i]);
    }
    std::cout << '\n';
}

using namespace std;

ll modpow(ll n, ll k, ll m) {
    ll ret = 1, now = n;
    while(k) {
        if(k&1) ret = ret * now % m;
        now = now * now % m;
        k /= 2;
    }
    return ret;
}

int main() {
    ll n, m; cin >> n >> m;
    vector<ll> forest(n+1, 1);
    rip(i,n+1,2) {
        rip(j,i-2,0) forest[i] = forest[i] * i % m;
    }
    vector<ll> frc(n+1, 1), inv(n+1, 1);
    rip(i,n+1,1) frc[i] = frc[i-1] * i % m;
    rip(i,n+1,1) inv[i] = modpow(frc[i], m-2, m);
    auto comb = [&](int n, int k) {
        return frc[n] * inv[k] % m * inv[n-k] % m;
    };
    vector<vector<ll>> dp(n+1, vector<ll>(n));
    dp[0][0] = 1;
    rip(i,n+1,0) rip(j, n, 0) {
        rip(k, n+1, 1) {
            if(i + k > n || j + k - 1 >= n) break;
            if(k == 1) dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % m;
            else {
                dp[i+k][j+k-1] = (dp[i+k][j+k-1] + comb(n-i-1,k-1) * forest[k] % m * dp[i][j] % m) % m;
            }
        }
    }
    rip(i,n,0) cout << dp[n][i] << endl;
}
0