結果
問題 | No.2898 Update Max |
ユーザー |
![]() |
提出日時 | 2024-09-18 23:44:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,747 bytes |
コンパイル時間 | 827 ms |
コンパイル使用メモリ | 76,416 KB |
実行使用メモリ | 8,388 KB |
最終ジャッジ日時 | 2024-09-19 21:50:06 |
合計ジャッジ時間 | 2,870 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 8 WA * 20 |
ソースコード
#include <iostream>#include <vector>using namespace std;#include <atcoder/modint>using namespace atcoder;using mint = modint998244353;const int MAX = 201000;constexpr long long MOD = 998244353;vector<mint> fac(MAX), finv(MAX), inv(MAX);// i!, 1/i, 1/i!void COMinit(){fac[0] = 1;fac[1] = 1;finv[0] = 1;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 COM(int n, int k){if(n < k || n < 0 || k < 0){return 0;}return fac[n] * finv[k] * finv[n - k];}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);COMinit();int n;cin >> n;int m = 0;vector<int> a(n), b, exist(n, 0);for(int i = 0; i < n; i++){cin >> a[i];if(a[i] == -1){m++;}else{a[i]--;exist[a[i]] = 1;}}for(int i = 0; i < n; i++){if(exist[i] == 0){b.emplace_back(i);}}mint ans = 0;int x = 0, mx = -1;for(int i = 0; i < n; i++){if(a[i] != -1){mx = max(mx, a[i]);if(mx != a[i]){continue;}int y = lower_bound(b.begin(), b.end(), mx) - b.begin();ans += COM(y, x) / COM(m, x);}else{int j = lower_bound(b.begin(), b.end(), mx) - b.begin();j = max(j, x + 1);ans += (COM(m, x + 1) - COM(j - 1, x + 1)) / (m * COM(m - 1, x));x++;}}for(int i = 1; i <= m; i++){ans *= i;}cout << ans.val() << endl;}