結果
問題 | No.2792 Security Cameras on Young Diagram |
ユーザー |
|
提出日時 | 2024-06-21 22:49:02 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 910 bytes |
コンパイル時間 | 1,994 ms |
コンパイル使用メモリ | 204,976 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 18:46:03 |
合計ジャッジ時間 | 3,157 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 WA * 1 |
ソースコード
#include <atcoder/modint>#include <bits/stdc++.h>using namespace std;using ll = long long;using mint = atcoder::modint998244353;#define rep(i, n) for (int i = 0; i < (int)(n); i++)const int MX = 100'010;mint fact[MX + 10], finv[MX + 10];mint c(ll a, ll b) {if (a < b || a < 0 || b < 0)return 0;return fact[a] * finv[a - b] * finv[b];}void solve() {fact[0] = finv[0] = 1;rep(i, MX) {fact[i + 1] = fact[i] * (i + 1);finv[i + 1] = fact[i + 1].inv();}ll n;cin >> n;vector<ll> a(n);rep(i, n) cin >> a[i];a.push_back(0);mint ans = 1;rep(i, n + 1) {if (i > 0 && a[i - 1] > a[i])for (ll j = a[i - 1]; j > a[i]; j--)ans += c(j + i - 1, i - 1);}cout << ans.val() << '\n';}int main() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);int T = 1;for (int t = 0; t < T; t++) {solve();}return 0;}