結果
問題 |
No.2898 Update Max
|
ユーザー |
![]() |
提出日時 | 2025-07-16 07:36:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 1,930 bytes |
コンパイル時間 | 1,109 ms |
コンパイル使用メモリ | 74,116 KB |
実行使用メモリ | 17,064 KB |
最終ジャッジ日時 | 2025-07-16 07:36:32 |
合計ジャッジ時間 | 5,459 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream> #include <atcoder/modint> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; const int MX = 1000010; mint f[MX],inv[MX],fi[MX]; constexpr ll mod = 998244353; void solve(){ inv[1] = 1; for(int i=2;i<MX;i++){ inv[i] = mod - (mod/i)*inv[mod%i]; } f[0] = fi[0] = 1; for(int i=1;i<MX;i++){ f[i] = f[i-1]*i; fi[i] = fi[i-1]*inv[i]; } } mint nck(ll n, ll k){ if(n<0 || k<0 || n<k) return 0; return f[n]*fi[k]*fi[n-k]; } mint pw(mint a,ll x){ mint ret = 1; while(x){ if(x&1) (ret *= a); (a *= a); x /= 2; } return ret; } int a[200010],noUse[200010]; bool b[200010]; int main(){ solve(); int i,n; cin >> n; for(i=0;i<n;i++) cin >> a[i]; int al = 0; for(i=1;i<=n;i++) noUse[i] = 1; for(i=0;i<n;i++){ if(a[i]==-1) al++; else noUse[a[i]] = 0; } for(i=1;i<=n;i++) noUse[i] += noUse[i - 1]; for(i=n + 1;i>=1;i--) noUse[i] = noUse[i - 1]; for(i=0;i<n;i++){ if(a[i]!=-1) b[a[i]] = true; } int no_exist_mx = -1; for(i=1;i<=n;i++){ if(!b[i]) no_exist_mx = max(no_exist_mx,i); } mint ans = 0; int mx = -1,c = 0; for(i=0;i<n;i++){ if(a[i]==-1){ if(mx<n){ int l = noUse[mx + 1],r = noUse[no_exist_mx]; // sum_{l<=x<=r} nck(x,c) = nck(r + 1,c + 1) - nck(l,c + 1) // lに関しては、mx + 1からでよい (mxより大きくて存在しない最小値をyとして、noUse[y]から始めたいが、noUse[y] = noUse[mx + 1]) ans += (nck(r + 1,c + 1) - nck(l,c + 1))*f[c]*f[al - c - 1]; } }else{ if(mx<a[i]){ ans += nck(noUse[a[i]],c)*f[c]*f[al - c]; } } if(a[i]==-1) c++; mx = max(mx,a[i]); } cout << ans.val() << "\n"; }