結果

問題 No.2792 Security Cameras on Young Diagram
ユーザー ortogawa
提出日時 2025-08-11 14:29:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 1,072 bytes
コンパイル時間 1,977 ms
コンパイル使用メモリ 198,020 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-11 14:29:42
合計ジャッジ時間 2,940 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int ll
#define fast_io cin.tie(0)->sync_with_stdio(0);
#define endl '\n'
typedef long long ll;

const int MAX = 2e5 + 10;
const int MOD = 998244353;
int fat[MAX], ifat[MAX];
int fexp(int a, int e) {
	int ans = 1;
	while (e) {
		if (e & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		e /= 2;
	}
	return ans;
}

int choose(int a, int b) {
	if (b < 0 || a < b) return 0;
	return fat[a] * ifat[b] % MOD * ifat[a - b] % MOD;
}

int32_t main() {
	fast_io;

	fat[0] = 1;
	for (int i = 1; i < MAX; i++) fat[i] = i * fat[i - 1] % MOD;
	ifat[MAX - 1] = fexp(fat[MAX - 1], MOD - 2);
	for (int i = MAX - 2; i >= 0; --i) {
		ifat[i] = ifat[i + 1] * (i + 1) % MOD;
	}

	int n; cin >> n;
	vector<int> a(n);
	for (auto &i : a) cin >> i;

	int at = a[0];
	int ans = 1;
	for (int i = 1; i < n; i++) {
		while (at > a[i]) {
			ans = (ans + choose(at + i - 2, i - 1)) % MOD;
			--at;
		}
		ans = (ans + choose(at - 1 + i, i)) % MOD;
	}
	while (at > 0) {
		ans = (ans + choose(at + n - 2, n - 1)) % MOD;
		--at;
	}

	cout << ans << endl;
}
0