A - Finding (((...)))

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

整数 N,K が与えられます．

(,) からなる正しい括弧列 s に対し，そのスコアを次のように定義します．

  • (( \times c )+ ( ) \times c) という形の文字列 ((), (()), ((())), etc...) をよい文字列と呼ぶことにする． s に(連続するとは限らない)部分列として含まれるよい文字列の長さの最大値を，s のスコアとする．

長さ 2N の正しい括弧列であって，スコアがちょうど 2K になるものの個数を 998244353 で割ったあまりを求めてください．

1 つの入力につき，T 個のテストケースを解いてください．

正しい括弧列とは 正しい括弧列とは、() である部分文字列を削除することを 0 回以上繰り返して空文字列にできる文字列を指します。

制約

  • 1 \leq T \leq 10^5
  • 1 \leq K \leq N \leq 10^6
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる．

N K

出力

答えを出力せよ．

入力例 1

4
2 1
2 2
3 1
100 70

出力例 1

1
1
0
366458221

長さ 4 の正しい括弧列と，そのスコアは以下のとおりです．

  • ()(): スコア 2
  • (()): スコア 4
B - Interpolation

実行時間制限: 8 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

すぬけくんは誕生日に N 次整数係数多項式 f(x),g(x) をもらいました． これに喜んだすぬけくんは，h(x)=2^x\times f(x) + g(x) と定義し，h(0),h(1),\cdots,h(2N+1) の値を \text{mod }{998244353} で計算しました． そして，h(i) \bmod 998244353=A_i であったとメモしました．

ある日，すぬけくんはうっかり f(x),g(x) をなくしてしまいました． 残っているのは A_0,A_1,\cdots,A_{2N+1} の値のみです． しかしすぬけくんは賢いので，この問題の制約下で（すぬけくんは自分が問題文の登場人物であることすら知っています！），これらの値から f(x),g(x) の係数を \text{mod }{998244353} で一意に復元できることに気が付きました．

A_0,A_1,\cdots,A_{2N+1} 及び X が与えられるので，h(X) \bmod 998244353 の値を求めてください．

制約

  • 0 \leq N \leq 125000
  • 0 \leq X \leq 9 \times 10^8
  • 0 \leq A_i < 998244353
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N X
A_0 A_1 \ldots A_{2N+1}

出力

答えを出力せよ．

入力例 1

0 2
5 7

出力例 1

11

f(x)=2,g(x)=3 です．

入力例 2

1 5
3 9 24 61

出力例 2

359

f(x)=2x+1,g(x)=x+2 です．

入力例 3

3 0
785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563

出力例 3

785439575

入力例 4

10 12345678
519729086 344065186 273714212 560047125 139793596 542901248 520999410 855572558 498896932 418633758 742973826 248730678 238856535 319502970 908902333 164543594 245101681 197971506 714635866 966125570 768080799 80565655

出力例 4

57546937
C - Even Subgrid

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1200 点

問題文

L \times L の盤面があります． 上から i 行目，左から j 列目のマスをマス (i,j) と呼ぶことにします．

最初すべてのマスは白色でしたが，すぬけくんが以下の操作を N 回行い，いくつかのマスを黒く塗りました．

  • 操作 i (1 \leq i \leq N): 長方形領域 [A_i,B_i] \times [C_i,D_i] を黒く塗る． より正確に言えば，すべてのマス (r,c) (A_i \leq r \leq B_i, C_i \leq c \leq D_i) に対して，その色を黒にする．

今から，各白マスに 0 or 1 を書き込みます． ただし，書き込み方は以下の条件を満たす必要があります．

  • 任意の 2 \times 2 領域について，その 4 マスがすべて白色なら，そこに書かれた値の合計は偶数である．

ところで，すぬけくんには M 個のこだわりがあります． i 番目のこだわりは，マス (X_i,Y_i) に書き込む数は V_i であってほしいというものです． こだわり i が満たされると，すぬけくんは 2^{M-i} の嬉しさを得ます．

すぬけくんが得られる嬉しさの合計の最大値を求めてください． なお，答えは M 桁の 2 進数として出力してください．

制約

  • 1 \leq L \leq 10^9
  • 0 \leq N \leq 250
  • 1 \leq M \leq 10^5
  • 1 \leq A_i \leq B_i \leq L
  • 1 \leq C_i \leq D_i \leq L
  • 1 \leq X_i,Y_i \leq L
  • マス (X_i,Y_i) は白色である
  • V_i = 0 or 1
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

L N M
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N
X_1 Y_1 V_1
X_2 Y_2 V_2
\vdots
X_M Y_M V_M

出力

答えを M 桁の 2 進数として出力せよ．

入力例 1

3 0 4
1 1 0
1 3 0
3 1 0
3 3 1

出力例 1

1110

こだわり 1,2,3 を満たすことはできますが，その場合こだわり 4 は満たせません．

入力例 2

3 1 4
2 2 2 2
1 1 0
1 3 0
3 1 0
3 3 1

出力例 2

1111

入力例 3

8 3 20
2 2 1 6
2 2 3 5
1 2 6 6
4 3 1
5 8 0
3 5 0
1 5 1
1 8 0
2 8 1
3 3 0
3 3 1
6 7 1
6 1 0
1 7 0
5 1 0
5 2 0
4 8 0
7 3 1
3 8 1
4 1 0
6 5 0
1 8 0
8 6 0

出力例 3

11111110111011110111

入力例 4

15 5 20
5 12 5 7
2 15 6 6
7 14 12 12
8 11 11 14
6 14 7 7
15 15 1
4 10 0
6 9 0
5 2 1
5 10 1
2 10 0
6 3 1
12 3 0
11 10 1
9 3 1
5 9 0
2 2 1
9 10 0
12 2 0
5 15 1
9 8 0
9 2 0
5 3 1
6 10 0
2 9 0

出力例 4

11111111111111110100
D - The Most Boring Game

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1200 点

問題文

整数の組の列 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) が与えられます． ここで，L_1 \leq R_1 < L_2 \leq R_2 < \cdots < L_N \leq R_N が保証されます． 整数の集合 S を S=[L_1,R_1] \cup [L_2,R_2] \cup \cdots \cup [L_N,R_N] と定義します．

あなたは暇つぶしのために，次のような遊びを思いつきました．

  • 空の黒板を用意する．そして，S に含まれるそれぞれの整数 v に対し，確率 1/(v+1) で v を黒板に書く． これらの選択はすべて独立である．
  • Alice と Bob を召喚し，以下のゲームを行わせる．
    • Alice からはじめて交互に手番をプレイする．プレイヤーは各手番で黒板に書かれた数を一つ消す． 黒板に書かれた数がなくなったらゲーム終了である． ゲームのスコアは ("Aliceが消した数の総和"-"Bobが消した数の総和") である． Alice はスコアを最大化するために，Bob は最小化するために最適に行動する．

遊びの結果，ゲームのスコアがちょうど K になる確率を \text{mod }{998244353} で求めてください．

確率 \text{mod }{998244353} の定義

求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

  • 1 \leq N \leq 8
  • 1 \leq L_1 \leq R_1 < L_2 \leq R_2 < \cdots < L_N \leq R_N \leq 9 \times 10^8
  • 0 \leq K \leq R_N
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N K
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

答えを出力せよ．

入力例 1

1 1
2 3

出力例 1

582309206

ゲームのスコアがちょうど 1 になるのは黒板に 2,3 が両方書かれるときのみで，この状況になる確率は 1/12 です．

入力例 2

2 3
1 2
4 6

出力例 2

443664157

入力例 3

3 0
1 1
10 10
100 100

出力例 3

230917011

入力例 4

5 78
2 3
5 8
13 21
34 55
89 144

出力例 4

495194560

入力例 5

8 608571543
17343953 20441194
126035510 225432305
226186035 246776041
310203273 364411927
468578834 469724135
489470456 504928885
639604101 708138853
771369549 852001013

出力例 5

550996549
E - Large Board

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1500 点

問題文

2N \times N の盤面があります． 上から i 行目，左から j 列目のマスをマス (i,j) と呼ぶことにします．

今から各マスに非負整数を書き込みます． ただし，以下の条件をすべて満たす必要があります．

  • i 行目 (1 \leq i \leq 2N) のマスに書かれた値の合計は A_i 以下である．
  • j 列目 (1 \leq j \leq N) のマスに書かれた値の合計は B_j 以下である．
  • マス (i,j) (1 \leq i \leq N,\ 1 \leq j \leq N) に書かれた値は X_i 以下である．
  • マス (i,j) (N+1 \leq i \leq 2N,\ 1 \leq j \leq N) に書かれた値は Y_j 以下である．

マスに書かれた値の総和としてありうる最大値を求めてください．

制約

  • 1 \leq N \leq 250000
  • 1 \leq A_i,B_i,X_i,Y_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \ldots A_{2N}
B_1 B_2 \ldots B_{N}
X_1 X_2 \ldots X_{N}
Y_1 Y_2 \ldots Y_{N}

出力

答えを出力せよ．

入力例 1

2
1 8 2 3
6 7
2 3
2 1

出力例 1

12

以下のように値を書き込めばよいです．

0 1
3 3
1 1
2 1

入力例 2

3
8 3 8 10 1 5
6 1 11
2 2 3
1 3 3

出力例 2

18

入力例 3

5
43 25 21 38 13 12 17 46 9 13
20 72 97 77 9
5 3 8 6 10
5 4 6 3 1

出力例 3

165

入力例 4

12
253 349 46 454 16 77 491 311 150 181 241 149 143 463 315 378 357 362 35 244 45 380 212 299
87 273 624 223 226 435 988 211 854 285 837 367
40 37 21 1 16 31 22 18 2 39 5 42
29 21 31 25 23 20 35 37 21 41 38 6

出力例 4

4106