結果
問題 |
No.2898 Update Max
|
ユーザー |
![]() |
提出日時 | 2025-07-16 07:13:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,570 bytes |
コンパイル時間 | 895 ms |
コンパイル使用メモリ | 74,320 KB |
実行使用メモリ | 17,184 KB |
最終ジャッジ日時 | 2025-07-16 07:13:31 |
合計ジャッジ時間 | 5,697 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 14 WA * 14 |
ソースコード
#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; } mint ans = 0; mint ans2 = 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[n]; // sum_{l<=x<r} nck(x,c) = nck(r,c + 1) - nck(l,c + 1) ans += (nck(r,c + 1) - nck(l,c + 1))*f[c]*f[al - c - 1]; // int cnt = 0; // for(int j=1;j<=mx;j++) cnt += !b[j]; // for(int j=max(0,mx) + 1;j<=n;j++){ // if(!b[j]){ // cout << cnt << endl; // // cout << j << " xx " << (nck(cnt,c)*f[c]*f[al - c - 1]).val() << "\n"; // ans2 += nck(cnt,c)*f[c]*f[al - c - 1]; // cnt++; // } // } // if(ans.val()!=ans2.val()){ // cout << mx << " " << l << " " << r << " " << c << " " << i << endl; // cout << cnt << endl; // cout << ans.val() << " " << ans2.val() << endl; // assert(false); // } } }else{ if(mx<a[i]){ ans += nck(noUse[a[i]],c)*f[c]*f[al - c]; ans2 += nck(noUse[a[i]],c)*f[c]*f[al - c]; } } if(a[i]==-1) c++; mx = max(mx,a[i]); // cout << "ans == " << ans.val() << "\n"; } cout << ans.val() << "\n"; // cout << ans2.val() << "\n"; }