結果

問題 No.1696 Nonnil
コンテスト
ユーザー 👑 希丝缇娜菲贝尔
提出日時 2026-08-31 20:07:40
言語 cLay
(20250308-1 + boost 1.92.0)
コンパイル:
clayc _filename_
実行:
./a.out
結果
AC  
実行時間 169 ms / 3,500 ms
+ 262µs
コード長 983 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,660 ms
コンパイル使用メモリ 206,128 KB
実行使用メモリ 24,280 KB
最終ジャッジ日時 2026-08-31 20:07:59
合計ジャッジ時間 10,342 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define MD 998244353
using mm = Mint;

ll @N; int @K, @m;

VI bst(K + 1, -1); // bst[r] := \max_{R_i = r} L_i
VI g(K + 1, -1); // g[r] := \max_{R_i <= r} L_i

rep(m) {
	int @L, @R;
	bst[R] >?= L;
}

rep(i, 1, K + 1) g[i] = max(bst[i], g[i - 1]); // bst[i] 前缀最大刚好是 g[i]

vector<vector<mm>> f(K + 1, vector<mm>(K + 1, 0)), pre(K + 1, vector<mm>(K + 1, 0));
f[0][0] = 1;

pre[0][0] = 1;
rep(i, 1, K + 1) pre[0][i] = pre[0][i - 1] + f[0][i];

rep(s, 1, K + 1) {
	rep(x, 1, K + 1) {
		f[s][x] = pre[s - 1][x - 1];
		if(g[x - 1] > 0) f[s][x] -= pre[s - 1][g[x - 1] - 1];
	}
	rep(x, 1, K + 1) pre[s][x] = pre[s][x - 1] + f[s][x];
}

vector<mm> H(K + 1, 0);
rep(s, 1, K + 1) rep(x, g[K], K + 1) H[s] += f[s][x];

vector<mm> F(K + 1, 0); // F(N, s) = s! * {N, s}

Comb<mm> comb;

rep(s, 1, K + 1) {

	rep(j, s + 1) {
		mm tt = 1;
		tt *= (-1) ** (s - j);
		tt *= comb.C(s, j);
		tt *= powmod(j, N, MD);
		F[s] += tt;
	}

}

mm ans = 0;
rep(s, K + 1) ans += H[s] * F[s];
wt(ans);
0