結果
問題 | No.2528 pop_(backfront or not) |
ユーザー | otoshigo |
提出日時 | 2023-11-03 21:59:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,569 ms / 2,000 ms |
コード長 | 1,439 bytes |
コンパイル時間 | 1,719 ms |
コンパイル使用メモリ | 88,244 KB |
実行使用メモリ | 91,740 KB |
最終ジャッジ日時 | 2023-11-03 22:00:17 |
合計ジャッジ時間 | 12,837 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
27,048 KB |
testcase_01 | AC | 70 ms
27,048 KB |
testcase_02 | AC | 71 ms
27,048 KB |
testcase_03 | AC | 70 ms
27,048 KB |
testcase_04 | AC | 92 ms
27,052 KB |
testcase_05 | AC | 73 ms
27,240 KB |
testcase_06 | AC | 77 ms
27,192 KB |
testcase_07 | AC | 90 ms
27,852 KB |
testcase_08 | AC | 100 ms
28,380 KB |
testcase_09 | AC | 172 ms
31,812 KB |
testcase_10 | AC | 406 ms
42,900 KB |
testcase_11 | AC | 450 ms
43,896 KB |
testcase_12 | AC | 595 ms
51,876 KB |
testcase_13 | AC | 664 ms
54,192 KB |
testcase_14 | AC | 789 ms
60,852 KB |
testcase_15 | AC | 1,229 ms
79,536 KB |
testcase_16 | AC | 1,569 ms
91,740 KB |
testcase_17 | AC | 1,528 ms
91,740 KB |
testcase_18 | AC | 1,528 ms
91,740 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<atcoder/modint> using namespace std; using namespace atcoder; using ll=long long; using mint=modint998244353; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} const int MAX=2000010; const ll MOD=998244353; mint fac[MAX+1],finv[MAX+1],inv[MAX+1]; void set_fac(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for (int i=2;i<=MAX;i++){ fac[i]=fac[i-1]*i; inv[i]=-inv[MOD%i]*(MOD/i); finv[i]=finv[i-1]*inv[i]; } } mint cmb(int n,int r){ if (r<0||n<r)return 0; return fac[n]*finv[r]*finv[n-r]; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); set_fac(); int N; cin>>N; N=2*N+1; vector dp(N+1,vector<mint>(N+1)); vector flag(N+1,vector<bool>(N+1)); auto f=[&](auto f,int x,int i)-> mint { if(flag[x][i])return dp[x][i]; if(x==1)return 1; if(i==1||i==x)return 0; flag[x][i]=true; if(i-2>=2)dp[x][i]+=f(f,x-2,i-2)*(i-2)*(i-3)/2; dp[x][i]+=f(f,x-2,i-1)*(1+(ll)(i-2)*(x-i-1)); if(x-i-1>=2)dp[x][i]+=f(f,x-2,i)*(x-i-1)*(x-i-2)/2; return dp[x][i]; }; for(int i=1;i<=N;i++)cout<<f(f,N,i).val()<<"\n"; }