結果
問題 | No.1667 Forest |
ユーザー |
👑 ![]() |
提出日時 | 2021-09-03 22:56:04 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 3,000 ms |
コード長 | 1,082 bytes |
コンパイル時間 | 2,761 ms |
コンパイル使用メモリ | 115,260 KB |
最終ジャッジ日時 | 2025-01-24 06:44:22 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <atcoder/modint>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(n); i++)using m32 = atcoder::modint;int main(){int N; cin >> N;u32 MOD; cin >> MOD;m32::set_mod(MOD);vector<m32> F(N+1,1);for(int i=1; i<=N; i++) F[i] = F[i-1] * i;vector<m32> I(N+1,1);for(int i=1; i<=N; i++) I[i] = m32(i).inv();vector<m32> iF(N+1,1);for(int i=1; i<=N; i++) iF[i] = F[i].inv();vector<m32> X(N+1, 1);for(int i=2; i<=N; i++) X[i] = m32(i).pow(i-2) * iF[i-1];vector<m32> dp(N+1,0);vector<m32> ans(N+1,0);dp[N] = F[N];for(int n=1; n<=N; n++){for(int k=0; k<=N; k++){for(int d=1; d<=k; d++){dp[k-d] += dp[k] * X[d] * I[k];}dp[k] = 0;}ans[N-n] = dp[0];}rep(i,N) cout << ans[i].val() << "\n";return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;