結果
問題 |
No.3213 depth max K
|
ユーザー |
|
提出日時 | 2025-07-25 22:36:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 297 ms / 2,000 ms |
コード長 | 12,765 bytes |
コンパイル時間 | 5,095 ms |
コンパイル使用メモリ | 339,732 KB |
実行使用メモリ | 199,884 KB |
最終ジャッジ日時 | 2025-07-25 22:36:50 |
合計ジャッジ時間 | 15,886 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; /* winter's kyopro template */ //*/ #include <atcoder/all> using namespace atcoder; //*/ // ......Jgg+. // ..jQHHMHHHHMMHHMNHHmaJ+&&ga&&J-.... ..(-. // .JdMHMM@@@@@MMHyyyWHHWMHHMMM@MMMHHHMMMNmmm&-..&HMMMMMm. // .(WHM@@@@@@@@MMWyyWWWH@@@@@g@@@@@MH@@@@@@@@MMHMMMHVyyVHMNHHHm. // .dMM@@@@@@@@@MHVWWWMMM@@@@@@@@@@@@@@@@@@@@@@@@@@@MkWWWHHHWyyHMn. // .dH@@@@MMMMHHHWWHWH@@@@@@@@@@@g@@@@g@@@@@@@@@@@@@@@MMHyyyyyyyWHMNma.. // (WH@@@@NWyyyWWHUuuuXWH@@@@@@@@@@@g@@@@@@M@@@@@@g@@@@@HHkyyyyyVH@@@MMHNm, // (WH@@@@@@HyyWHUuuuuuuuuXWHHHH@@@@@@@g@@@@@MM@@@@@@@@@@HUWkyyyyWM@@@@@@MMNm- // .dH@@@@@@@MkWHkkkkkkXuuuuuuuuXWUWHHHHHHHg@@g@MHHg@@HHHUuuuWkyyyyWM@@@@@@@MMH+ // .dMM@@@g@@MHHM@@@@@@@HHkkkXuuuWSuuuuuuuuuuuuXXXUHkXuuuuuuuuXHkyyyyWHM@@@@@@MHNe. // (MM@@@@@@@NW@@@@@@MM@@@@@@@HHWHkkXuuuuuuuuuuuuuuuUHkuuuuuuuuXHWyyyyyVHM@@@g@@MNl // .WH@@@@@@@@@M@@@@@MM@@@@@@@M9=d@@@@gHHHHkkkkkkQQQQQkHkQkkHHHkkWkyyyyyyyWH@@@@@MHH- // .dH@@@@@g@@@H@@@@@MM@@@@@@H9! (W@@@@@@@@MM@@@@@@@@@@@@MM@@@@@@@@HVyyyyyWWW@@@@@@MNr // (HM@@@@@@@@MM@@@@@M@g@@@@B:``.(@@@@@@@@@MH@@@@@@@@@@@@@MM@@@@@@@MHWWkWqH@@@@@@@@MHH_ // .dHM@@@@g@@@H@@@@@H@@@@@M3_`.` J@@@@@@@@@H?H@@@@@@@@@@@@@HM@@@g@@@@HHWyyVH@@@@@@@@HH~ // dMM@@@@@@@@HM@@@@@H@@g@#>..... dM@@@g@@@@D.?H@@@@@g@@g@@@@M@@@@@@@@HVWWWH@@@@@g@@@HN- // .dMM@@@@g@@gMH@@@@@M@@@@#><?zw&. j@@@@@@g@M>` ?M@@@@@@@@@@@@H@@@@@@@@MH@M@@@@@@@@@@@HM{ // .dMM@@@@@@@@@M@@@@g@H@@@#!```` _?IjH@@@@@@M$_``.?H@@@@@@g@@@@M@@@g@@@@M@@@@@@@@@@@@@@HM> // ..jHH@@@@@g@@g@MM@@@@@@HM@MC......`.`_W@@@@@@D_..-J+dMMM@MM@@@g@H@@@@@@@MH@@@@@@@@@g@@@MHD` // .gHHQHMMM@@@@@@@@@@MHM@@@@g@@HM@D~.(ggNQma,.jH@MM@#~.-~~_.. ?WMMHM@@@@H@@@@g@@HHM@@@@@g@@@g@@MMD // ZMHM@@@@@@@@@@@@@MHM@@@@@@@MHMMI+MB=?HNHHMn-U@MMM{.````.``.. ?TMMM@@@M@g@@@@@H@H@@@g@@@@@@@@HM$ // ?WMHMHM@@@@@@g@MM@@@Nc?H@MHMMNd#:+-.dMMNZ>.(WN?U:`.`.``.```.`._!_TMM@@@@g@@MM@MM@@@@@g@@@@@H#: // .+MHM@@@@@@@@@MM@@@@@No(HHHVUWN{(MMMMMMMb_`.-?!`.`...-((-..`.`.`. (M@@@@@@@H@@M#M@@@@@g@@@MHR // (dMM@@@@@@@@@MHMHWHM@@M81zHD_dMN<(MMMMMMMD_``.``.`. (JgggJ.<!.``. (H@@@g@@@M@@@MMH@@g@@@@@@MHR // +MM@@@@@@@@MMHHM@Nm._79!<-(>`(wI?3-?MHWWM@!.`.`.`.`.(TYYYHMMNe..`.(H@@@@@@MHM@@MM@@@@@@@@g@@MHR // jMHMMM@@@@MMM@@HM@@@@H+ <i(w> jK>:~~__<?7!_``.`.`.`.``.``.` _7MMs(d@@@@@@@MWM@@MHM@@@@@@@g@@@MHD // dHH#M@@@MMM9>?WH@@@MM@N;. ~!.jMH<:::::_`.``.`..`.``.`.`.`... .(WHMM@@@@HY! dHHHHM@@@@@g@@@@@MMr // dHHM@@@MM9! dHM@MHM@#Nx `` ?MN<_____.`.`......`.``.`.`._~:::((ud@@HH9=``` jH@HH@@@@@@@@@@@@MMR. // vMHM@MH#> dMM@HHHMMHM2 `.`?MN, ````.`..jUwz?>++. ``.`_~~:?TY9Y=<~_``...dM9TMH@@M@@@@g@@g@@HH_ // OMM@H#: .WMHHH@@MMHN;.`.`_TMm. `.```.jZ=====zw:.``.`..`````..-JJJggHHY! .HH@MHM@@@@@@@@@HN{ // .dHMHR _WMHHMC!?TMN+.`.`._vHW&...``.?====zz>_`.`.``````..JdMBYTY^` .WH@HHMM@@@g@MM@MMR. // (MMHR_ _7T=` (MN+``.` (wXWUUO+-.. _~<<`.`.`..` .-JgHMHHH, dMM@HHHM@@@@@MHMHNe. // (TH9! (HNx..`.wdyykX<(HWH4Z1++(((JJ&zwXWWWHHWWXMNo TMH@MHH@@@@@HHHH#MH+ // (WMm&(wwXyyyXXdkW0`.`.`. dWyR+uwyyyyyyyWwHN{ ?THMMH@@@@@HMY7TMHC // jMSXSwyyyyyyWXUWH......(dHWUXXyyyyyyyyykXMHe. dMM@@@MH#~ // dMHXXyyyyyyyWWyXkwXZuuuwXwuUyyyyyyyyyyykwvdMm. J@M@@@MMD` // (TMM@HHQQkkkWHyyyyyyyyyy0<:;zyyyyyyyyyXXf~_WN- .dH@@@HM@! // `??TYYYWHMMWyyyyyyyyyWA&uwyyWHkyyyUwVC((dMMMH_ .HH@@MM8! // vMNWyyyyyyyyyyyyyyyyyWHkQHmdWWyyWHMD` .dMMMM#=` // 7MMkyyyyyyyyyyyyyyyyyWWHMMkWWWWMMHH+ JMMM9=` // (TMMHkWyyyyyyyyyyyyyWHWkWH9Y<zUV<WN; ?!` // .(d@HMHWkkWyyyyyyyVWHHM8w+ ` _.(HNo. // .(gkHHMMMMNWyyWWWWVyyypHpW0z;<zO++zV9?WN; // (WMM9UOOTUv?WWkWVVVWWWWU0CzXz;;;;;;+Z:-dM{ // (MR~1+-<.(w++<?TH9TC1<;;;;;?1;;>;;+v:(dMD` // ?MH+?1-.._<zz;vC;;;;>++;;>;>;;;;+wC<&dN: // `(M#!_?u-..(z&++>;;<jV<;>;;;>>>+jZ~(dM= // .TMm+JZ1--_._~?zz&u9Twzz&&zZ77<!(WMB^ // (WHB1-_(z_..(-____..~_~~_.._-JW#> // .gHMB! <<.(1(JXQe+((+<<<1+(+1WMMY` // .dM9!_~```-?1-.(dMD<<<<<(-....dMC // (W#! ````````` (dH@~````` _?<.dM= // (H8````````` .(HHM}` `````` (WB! // .d#:`` ```` .JHMHM#~``` `` .(M9! // `(MD ` ````.JkM9=`(H$`````` jM$ // (@{``` ` (HB>` (@l ` `` `.WK~ // .dMx ``.jM3` JM{``` ```.MK` // .WHHA<+(dMC dM>````` `(M$ // dHH$_(WM3 dN: ``` ` dN{ // ?MHmJdH#! .d#~` ````-WD` // ?TTB9! (Mb- ` ` .dM> // .dH9!(A-. .dM% // (MNI-.dWyVQd#> // .TMm+?UVWWM#> // ?WMHmdMM9! // _?7T=! #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC target("avx,avx2,fma") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #define rep(i,n) for(int i=0;i<n;i++) #define Rep(i,a,b) for(int i=a;i<b;i++) #define ALL(x) (x).begin(),(x).end() #define dbgv(x); for(auto now : x) cout << now << " "; cout << endl; //using P = pair<int,int>; using ll = long long; using ull = unsigned long long; //*/ template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<int> vint; random_device rnd; mt19937 rng(rnd()); const int dx[4] = {1,0,-1,0}; const int dy[4] = {0,1,0,-1}; const int dx2[8] = {1,1,1,0,-1,-1,-1,0}; const int dy2[8] = {0,1,-1,1,0,1,-1,-1}; using mint = modint998244353; long long pow(long long x, long long n, long long m) { long long ret = 1; x %= m; while (n > 0) { if (n & 1) ret *= x; // n の最下位bitが 1 ならば x^(2^i) をかける x *= x; n >>= 1; // n を1bit 左にずらす ret %= m; x %= m; } return ret; } // 閉区間の範囲を管理 template<typename T> struct RangeSet{ set<pair<T,T>> st; T TINF; RangeSet(){ TINF=numeric_limits<T>::max()/2; st.emplace(TINF,TINF); st.emplace(-TINF,-TINF); } // [l,r] covered? bool covered(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); return ite->first<=l and r<=ite->second; } bool covered(T x){ return covered(x,x); } // [l, r]がカバーされているなら,その区間を返す. されていないなら[-TINF,-TINF]を返す pair<T,T> covered_by(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return *ite; return make_pair(-TINF,-TINF); } pair<T,T> covered_by(T x){ return covered_by(x,x); } // insert[l,r], 増加量を返す T insert(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return T(0); T sum_erased=T(0); if(ite->first<=l and l<=ite->second+1){ l=ite->first; sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); }else ite=next(ite); while(r>ite->second){ sum_erased+=ite->second-ite->first+1; ite=st.erase(ite); } if(ite->first-1<=r and r<=ite->second){ sum_erased+=ite->second-ite->first+1; r=ite->second; st.erase(ite); } st.emplace(l,r); return r-l+1-sum_erased; } T insert(T x){ return insert(x,x); } T insert_sum(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second) return T(1LL); T sum_erased=T(0); T cnt = 0; if(ite->first<=l and l<=ite->second+1){ l=ite->first; sum_erased+=ite->second-ite->first+1; cnt += 1; ite=st.erase(ite); }else ite=next(ite); while(r>ite->second){ sum_erased+=ite->second-ite->first+1; cnt += 1; ite=st.erase(ite); } if(ite->first-1<=r and r<=ite->second){ sum_erased+=ite->second-ite->first+1; r=ite->second; cnt += 1; st.erase(ite); } st.emplace(l,r); //cerr << r-l+1-sum_erased << " " << cnt << endl; return r-l+1-sum_erased+cnt; } // erase [l,r], 減少量を返す T erase(T l,T r){ assert(l<=r); auto ite=prev(st.lower_bound({l+1,l+1})); if(ite->first<=l and r<=ite->second){ // 完全に1つの区間に包含されている if(ite->first<l) st.emplace(ite->first,l-1); if(r<ite->second) st.emplace(r+1,ite->second); st.erase(ite); return r-l+1; } T ret=T(0); if(ite->first<=l and l<=ite->second){ ret+=ite->second-l+1;// 消えた if(ite->first<l) st.emplace(ite->first,l-1); ite=st.erase(ite);// 次へ }else ite=next(ite); while(ite->second<=r){ ret+=ite->second-ite->first+1; ite=st.erase(ite); } // 右端が区間の間にあるか if(ite->first<=r and r<=ite->second){ ret+=r-ite->first+1; if(r<ite->second) st.emplace(r+1,ite->second); st.erase(ite); } return ret; } T erase(T x){ return erase(x,x); } // number of range int size(){ return (int)st.size()-2; } // mex [x,~) T mex(T x=0){ auto ite=prev(st.lower_bound({x+1,x+1})); if(ite->first<=x and x<=ite->second) return ite->second+1; else return x; } void output(){ cout<<"RangeSet : "; for(auto &p:st){ if(p.first==-TINF or p.second==TINF) continue; cout<<"["<<p.first<<", "<<p.second<<"] "; } cout<<"\n"; } }; using mint = modint998244353; mint dp[5010][5010]; mint dp2[5010][5010]; void solve(){ rep(i,5001)rep(j,5001) dp[i][j] = 0; rep(i,5001)rep(j,5001) dp2[i][j] = 0; dp[0][0] = 1; int n,k; cin >> n >> k; rep(i,n+1)for(int j = 0;j <= i;j++){ { int ni = i+1; int nj = j; if(ni > n || ni - nj > k); else{ dp[ni][nj] += dp[i][j]; } } { int ni = i; int nj = j+1; if(nj > n || ni < nj); else{ dp[ni][nj] += dp[i][j]; } } } dp2[0][0] = 1; rep(i,n+1)for(int j = 0;j <= i;j++){ { int ni = i+1; int nj = j; if(ni > n || ni - nj > k-1); else{ dp2[ni][nj] += dp2[i][j]; } } { int ni = i; int nj = j+1; if(nj > n || ni < nj); else{ dp2[ni][nj] += dp2[i][j]; } } } // rep(i,n){ // rep(j,n){ // cout << dp[i][j].val() << " "; // } // cout << endl; // } mint ans = dp[n][n] - dp2[n][n]; cout << ans.val() << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(25); int t = 1; //cin >> t; rep(testcase,t) solve(); }