H - TUATPC2024Summer (Heuristic) (Admin ver.) (Hard)
ผักชี
2
s
1024
MB
100
点
問題文
長さ $N$ の整数列 $A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N)$ が与えられます。
$1$ 以上 $N$ 以下の全ての整数からなる集合の空でない部分集合 $S$ のうち、以下の $3$ つの条件のうち少なくとも $1$ つを満たすものの個数を $998244353$ で割ったあまりを求めてください。
- $|S| \leq 2$
- $\underset{i \in S}{\max}\left( \max(A_i, B_i) \right) < 1600$
- $\displaystyle\sum_{i \in S} \max(A_i, B_i) < 4200$
制約
- $1 \leq N \leq 500{,}000$
- $1 \leq A_i, B_i \leq 10^9$
- 入力はすべて整数
部分点
以下の制約を追加したデータセットに正解した場合は $1$ 点が与えられます。
- $N \leq 10^3$
入力
入力は以下の形式で標準入力から与えられます。
$N$
$A_1\ \ A_2\ \ \cdots\ \ A_N$
$B_1\ \ B_2\ \ \cdots\ \ B_N$
出力
答えを標準出力に出力してください。
入力例 1
4
100 1100 4300 1200
500 200 2350 1700
出力例 1
11
$|S| \leq 2$ であるような部分集合はすべて $1$ つ目の条件を満たします。また、そのような部分集合は $10$ 個存在します。
$|S| \geq 3$ であるような部分集合について考えます。$S = \lbrace 1, 2, 4\rbrace$ のとき、$3$ つ目の条件を満たします。そうでないとき、$S$ はいずれの条件も満たしません。
よって $11$ を $998244353$ で割ったあまりである $11$ を出力します。
入力例 2
5
314 159 265 358 979
323 846 264 338 327
出力例 2
31
すべての $S$ が少なくとも $1$ つの条件を満たします。
入力例 3
9
1264 1862 1748 1286 972 891 860 1337 958
1297 1278 1230 1357 891 7 1309 1407 240
出力例 3
172