問題文

与えられたスタンプだけを高々 20\,000 回使うことで，以下の領域マップに沿った画像を作り上げよ．後述の達成条件を満たしていれば，カラフルな画像にしてもよい．

キャンバスとスタンプ

画像を作るためのキャンバスは横 800 px，縦 400 px であり，画素の位置は整数の組 (x, y) (0 \le x < 800，0 \le y < 400) で表される．x 座標が増える方向が左から右へ，y 座標が増える方向が上から下へであることに注意せよ．各画素は色を表す R, G, B の 3 要素を持つ．はじめ，キャンバスのどの要素も R, G, B の値はすべて 0 である．

スタンプは大きさ s と，色情報 r, g, b の 4 つの整数によって表される．1 回のスタンプ操作では，キャンバスの指定した位置にスタンプを押すか，指定した位置からスタンプを引くことができる．

より詳細には，あるスタンプ (s, r, g, b) を位置 (x_i, y_i) に 押した／引いた 場合，x_i \le x < x_i + s かつ y_i \le y < y_i + s を満たすすべての画素 (x, y) に対し，その画素の R, G, B の値にそれぞれ r, g, b が 加算／減算 される．操作の結果，ある画素の値が 255 を上回った場合は 255 に，0 を下回った場合は 0 になる．

達成条件

領域マップにおいて，同じ色からなる画素の 4 方向に連結な成分を領域と呼ぶ．ある画像が「領域マップに沿った」とみなされるためには次のようになっている必要がある．

• それぞれの領域内はある程度同じ色で塗られている．
• 隣り合う領域はある程度異なる色で塗られている．

厳密には，画像が以下の 2 条件をどちらも満たしていればよい：

• 領域内条件：それぞれの領域に対し，領域内の画素すべての R の値の分散が 700 以下であること．また，G の分散と B の分散も同様に 700 以下であること．
• 隣接領域条件：ある領域の平均色を，領域内の画素すべての R, G, B の (要素ごとの) 平均値とする．領域マップにおいて隣接する 2 つの領域の平均色をそれぞれ (R_1, G_1, B_1) および (R_2, G_2, B_2) とすると，(R_1 - R_2)^2 + (G_1 - G_2)^2 + (B_1 - B_2)^2 \ge 80^2 が成り立つこと．

データ

この問題を解くために必要なデータをまとめた zip ファイルがこちらからダウンロードできる．zip 内には以下のファイルが入っている．

• stamps/map.png: 領域マップを表す画像．画像サイズは横 800 px，縦 400 px である．
• stamps/map.txt: 領域マップに対応する，各画素にその領域 ID を振ったテキストファイル．
  • 400 行からなり，各行に 800 個の整数が書かれている．
• stamps/stampset.txt: 使えるスタンプの一覧を表すテキストファイル．
  • 1 行目にはスタンプの種類数 K が書かれている．
  • 続く K 行には，各行に 5 個の整数 k, s, r, g, b が書かれている．これはスタンプ ID が k であるスタンプが (s, r, g, b) で表されることを意味する．スタンプはスタンプ ID の昇順に書かれている．
• stamps/play.html: ビジュアライザ兼手作業用ツール．操作列の可視化や，達成条件の判定などの機能も備えているので，少なくとも提出前には使うことが推奨される．
  • 左下に「スタンプ操作をロードする」機能がある．これは正しいスタンプ操作を表す行だけをすべて読み込む (よって，後述の出力形式に従ったものを入れたときは，最初の行は単に読み飛ばされる)．
• stamps/play.js: ビジュアライザ兼手作業用ツールのソースコード．

制約

上記のデータが満たす条件のうち，一部の重要な情報を以下に示す．

• 画像サイズは横 800 px，縦 400 px である．
• 領域の個数は 30 であり，領域 ID は 0, \ldots, 29 である．
• 同じ領域 ID が振られた画素の集合は 4 方向に連結である．
• スタンプの種類数は 18 であり，スタンプ ID は 0, \ldots, 17 である．
• 各スタンプにおいて，以下が成り立つ：
  • 7 \le s \le 50．
  • 0 \le r \le 40．
  • 0 \le g \le 40．
  • 0 \le b \le 40．

入力例 1

出力例 1

4
0 100 200 1
1 -10 5 1
2 799 300 -1
0 100 200 1

これは上記の書式の条件を満たす出力の例である (ただし，この出力は達成条件を満たしていないので WA になる)．

問題文

1 回の賭けで「所持金が 1 円減る．確率 P % で所持金が W 円増え (あたり)，(100 - P) % で何ももらえない (はずれ)」となるものがある．なお，所持金は任意の整数値をとりうる．

正の整数 n であって以下の条件を満たすもののうち，最大のものを求めよ．ただし，条件を満たす n が存在しない場合は -1 と答えよ．また，条件を満たす n が無限個存在する場合は -2 と答えよ．

条件．最初，くじらの所持金は 0 円である．くじらが n 回この賭けを行う (各賭けでの確率は独立である)．このとき，「最終的なくじらの所持金が 0 円より真に多い確率」が \frac{1}{2} より真に大きい．

制約

• 0 \le P \le 100．
• 0 \le W \le 100．
• P, W は整数である．

入力例 1

30 3

出力例 1

2

n = 2 は条件を満たす．以下のように，最終的なくじらの所持金が 0 円より真に多い確率が \frac{51}{100} となるからである：

• 1 回目であたり 2 回目であたる確率は \frac{9}{100}，このとき最終的な所持金は 4 円となる．
• 1 回目であたり 2 回目ではずれる確率は \frac{21}{100}，このとき最終的な所持金は 1 円となる．
• 1 回目ではずれて 2 回目であたる確率は \frac{21}{100}，このとき最終的な所持金は 1 円となる．
• 1 回目ではずれて 2 回目ではずれる確率は \frac{49}{100}，このとき最終的な所持金は -2 円となる．

一方，n > 2 のときは条件を満たさないことが証明できる．よって求める最大の n は 2 である．

入力例 2

20 3

出力例 2

-1

入力例 3

40 3

出力例 3

-2

問題文

T 個のテストケースが与えられる．各テストケースで整数 N と整数 A_1, \ldots, A_N が与えられるので，以下の問に答えよ．

N 個の皿が並んでいて，i 番目の皿には最初キャンディが A_i 個置かれている．くろうさとしろうさがゲームをする．くろうさが先手で，交互に以下の行動をする．

行動．キャンディが 1 個以上置かれている皿を 1 個選び，その皿のキャンディの個数を x とする．その皿のキャンディの残り個数が x - 1 または \left\lfloor \frac{\sqrt{5} - 1}{2} x \right\rfloor になるようにキャンディを減らす (\lfloor y \rfloor は y を超えない最大の整数を表す)．取ったキャンディは他の皿に足したりせずすべて食べる．

行動ができなくなった方が負けで，負けなかった方が勝ちである．くろうさとしろうさのどちらに必勝法があるか？

制約

• 1 \le T \le 100．
• 1 \le N \le 20．
• 1 \le A_i \le 10^{18} (1 \le i \le N)．

入力例 1

2
2
5 9
4
20 15 10 5

出力例 1

Black
White

1 番目のテストケースでは，くろうさの最初の行動としては以下のいずれかが可能である：

• 1 番目の皿のキャンディの残り個数を 5 - 1 = 4 にする (1 個食べる)．
• 1 番目の皿のキャンディの残り個数を \left\lfloor \frac{\sqrt{5} - 1}{2} \cdot 5 \right\rfloor = 3 にする (2 個食べる)．
• 2 番目の皿のキャンディの残り個数を 9 - 1 = 8 にする (1 個食べる)．
• 2 番目の皿のキャンディの残り個数を \left\lfloor \frac{\sqrt{5} - 1}{2} \cdot 9 \right\rfloor = 5 にする (4 個食べる)．

くろうさは，このうち例えば 2 番目の皿のキャンディの残り個数を 5 にする行動を選ぶと，その後しろうさの行動によらず必ず勝つ方法が存在する．

問題文

正の整数 N と整数 C が与えられる．N \times N 行列 A を次のように定める： (i, j) 成分 (1 \le i \le N，1 \le j \le N) は

• i = j のとき 1，
• j が i で割り切れないとき C，
• 上のいずれでもない場合 0．

このとき，\det A を 998244353 で割った余り (0 以上 998244353 未満) を求めよ．

制約

• 1 \le N \le 10^9．
• 0 \le C < 998244353．

部分点

• N \le 10^5 を満たすデータセットに正解した場合は，20 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 80 点が与えられる．

入力例 1

6 3

出力例 1

998244345

A = \begin{bmatrix}1&0&0&0&0&0\\3&1&3&0&3&0\\3&3&1&3&3&0\\3&3&3&1&3&3\\3&3&3&3&1&3\\3&3&3&3&3&1\end{bmatrix} であり，\det A = -8 となる．

入力例 2

2020 11

出力例 2

515894850

入力例 3

1000000000 2020

出力例 3

4909496

問題文

正の整数 N, A が与えられる．

m を正の整数とする．サイは 1 から m までの番号のついた m 個の特殊なサイコロを持っている．これからサイは，それぞれのサイコロを A 回ずつ振る．サイコロ i (1 \le i \le m) を 1 回振るたびに，\frac{1}{i^2} の確率であたりが出る．これらの試行の結果はすべて独立な事象である．

合計でちょうど N 回あたりが出る確率はいくつだろうか？　この値は m に依存するが，m が限りなく大きくなるときのこの確率の極限を求めよ．

この極限の値を p とおくと，有理数 c_0, \ldots, c_{N-1} であって p = \sum_{j=0}^{N-1} c_j \pi^j となるものが一意に存在することが証明できる (\pi は円周率)．この c_0, \ldots, c_{N-1} を \operatorname{mod} 998244353 で出力せよ．

有理数を \operatorname{mod} 998244353 で出力する際は，それを既約分数 \frac{x}{y} で表したとき，x - y z が 998244353 で割り切れるような 0 以上 998244353 未満の整数 z を出力せよ．この問題の制約によって，出力すべき値は一意に定まることが証明できる．

制約

• 1 \le A \le N \le 250\,000．

部分点

• N \le 100 かつ A = 1 を満たすデータセットに正解した場合は，10 点が与えられる．
• A = 1 を満たすデータセットに正解した場合は，上記とは別に 10 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 80 点が与えられる．

入力例 1

1 1

出力例 1

499122177

p = \frac{1}{2} である．

入力例 2

2 1

出力例 2

623902721 0

p = \frac{3}{8} である．

入力例 3

3 1

出力例 3

686292993 0 353544875

p = \frac{5}{16} - \frac{1}{48} \pi^2 である．

入力例 4

3 2

出力例 4

623902721 0 0

p = \frac{3}{8} である．

入力例 5

10 5

出力例 5

748591874 0 809083222 0 440705764 0 0 0 0 0

問題文

カナリアは以下のような問題を作った．

Fox the Optimizing Chef

長さ N の整数列 A = (A_1, \ldots, A_N) と B = (B_1, \ldots, B_N) が与えられます．

きつねは，あるレストランを経営しています．今このレストランには，1 から N までの番号のついた N 人の客がいます．客 i は，調理に A_i 単位時間かかる料理を注文し，料理を食べるのに B_i 単位時間かかります．

各整数 k (1 \le k \le N) について，以下の問題を解いてください．

きつねが k 人の客を選び，選ばなかった N - k 人を帰宅させます．そして，k 人のための料理を好きな順で作っていきます．2 個以上の料理を同時に作ることはできません．客は，自分の料理が完成した瞬間に食事を開始します．きつねの労働時間は，「最初の料理を作り始めてから，k 人の客すべてが食事を終えるまでの時間」です．きつねの労働時間の最小値を求めてください．

しかし，この問題はロシアの国内コンテストでほぼ既出であることが発覚した．そこで，カナリアは問題を以下のように変形した．

Fox the Counting Chef

整数 V と，長さ N の整数列 B = (B_1, \ldots, B_N) が与えられます．

長さが N で各要素が 1 以上 V 以下の整数列 A = (A_1, \ldots, A_N) は V^N 通り存在しますが，それぞれの A に対し (与えられた B とともに) 問題 "Fox the Optimizing Chef" を解き，各整数 k (1 \le k \le N) についてその答えの総和を 998244353 で割った余りを求めてください．

問題 "Fox the Counting Chef" を解け．

制約

• 1 \le N \le 30．
• 1 \le V \le 20．
• 1 \le B_i \le 600 (1 \le i \le N)．

入力例 1

2 2
1 2

出力例 1

10 16

k = 2 の場合を考える．各 A に対する元の問題の答えは以下のようになる：

• A = (1, 1)：労働時間の最小値は 3．
• A = (1, 2)：労働時間の最小値は 4．
• A = (2, 1)：労働時間の最小値は 4．
• A = (2, 2)：労働時間の最小値は 5．

よって，3 + 4 + 4 + 5 = 16 を出力する．

入力例 2

3 5
1 2 4

出力例 2

448 787 1255

入力例 3

10 10
14 38 45 9 19 18 7 18 33 21

出力例 3

663655052 615617049 323725023 554911324 803518888 499232802 916051842 54293837 639852351 260050903

問題文

この問題では，グラフは無向単純グラフのみを考える．グラフ H, H' に対し，グラフ H \mathbin{\square} H' と H \times H' を以下のように定義する．H, H' の頂点集合をそれぞれ V(H), V(H') と書く．W = V(H) \times V(H') (すなわち「H の頂点と H' の頂点の組」全体の集合) とおく．

H \mathbin{\square} H' の頂点集合は W であり，H \mathbin{\square} H' において頂点 (u, u') \in W と (v, v') \in W を結ぶ辺があるための必要十分条件は，以下のいずれかが成り立つことである：

• u = v，かつ，H' において頂点 u' と頂点 v' を結ぶ辺がある．
• u' = v'，かつ，H において頂点 u と頂点 v を結ぶ辺がある．

H \times H' の頂点集合は W であり，H \times H' において頂点 (u, u') \in W と (v, v') \in W を結ぶ辺があるための必要十分条件は，「H において頂点 u と頂点 v を結ぶ辺があり，かつ，H' において頂点 u' と頂点 v' を結ぶ辺があること」である．

例

K 個のグラフ G_1, \ldots, G_K が与えられる．各 k (1 \le k \le K) に対し，G_k の頂点集合は \{1, \ldots, N_k\} であり，G_k は M_k 本の辺を持ちその i 番目 (1 \le i \le M_k) は頂点 A_{k,i} と B_{k,i} を結ぶ．

各 k, k' (1 \le k \le K，1 \le k' \le K) に対し，グラフ G_k \mathbin{\square} G_{k'} と G_k \times G_{k'} が同型であるか判定せよ (すなわち，全単射 f\colon V(G_k) \times V(G_{k'}) \to V(G_k) \times V(G_{k'}) であって，任意の (u, u'), (v, v') \in V(G_k) \times V(G_{k'}) に対し「G_k \mathbin{\square} G_{k'} において頂点 (u, u') と頂点 (v, v') を結ぶ辺があること」と「G_k \times G_{k'} において頂点 f((u, u')) と頂点 f((v, v')) を結ぶ辺があること」が同値となるようなものが存在するか判定せよ)．

制約

• 1 \le K \le 10．
• 1 \le N_k \le 25\,000 (1 \le k \le K)．
• 0 \le M_k \le 25\,000 (1 \le k \le K)．
• 1 \le A_{k,i} < B_{k,i} \le N_k (1 \le k \le K，1 \le i \le M_k)．
• 各 1 \le k \le K に対し，M_k 個の組 (A_{k,i}, B_{k,i}) (1 \le i \le M_k) はすべて異なる．

入力例 1

5
3
2
1 2
2 3
4
3
1 2
2 3
3 4
5
5
1 2
1 3
2 4
3 5
2 3
8
6
1 2
5 8
1 6
4 8
2 7
6 7
6
9
1 3
3 5
1 5
1 2
2 3
3 4
4 5
5 6
1 6

出力例 1

00000
00000
00000
00000
00000

問題文

正の整数 N が与えられる．\{0, \ldots, N - 1\} の空でない部分集合それぞれについて，「葉にふさわしいか否か」「根にふさわしいか否か」がそれぞれ決まっている．

根付き木の各頂点に \{0, \ldots, N - 1\} の空でない部分集合 1 個がラベルとして書かれたものであって，以下の条件をすべて満たすものの個数を 998244353 で割った余りを求めよ：

• 各頂点の子は 0 個または 2 個である．
• 子が 0 個の頂点のラベルは葉にふさわしい．
• 子が 2 個の頂点に対し次が成り立つ：その頂点のラベルを A，子のラベルを B, C とするとき，B \cup C = A かつ B \cap C = \emptyset．
• 根のラベルは根にふさわしい．

ただし，子が 2 個ある頂点についてそれらの順番は区別しない．

制約

• 1 \le N \le 21．

入力例 1

3
01110111
00000101

出力例 1

4

この例では，葉にふさわしい集合は \{0\}, \{1\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\} の 6 個，根にふさわしい集合は \{0, 2\}, \{0, 1, 2\} の 2 個である．条件を満たすラベル付き根付き木は以下の 4 個である：

• 根のラベルが \{0, 2\} である 1 頂点の木
• 根のラベルが \{0, 1, 2\} である 1 頂点の木
• 根のラベルが \{0, 1, 2\} であり，その子のラベルが \{0\}, \{1, 2\} である 3 頂点の木
• 根のラベルが \{0, 1, 2\} であり，その子のラベルが \{1\}, \{0, 2\} である 3 頂点の木

入力例 2

5
00000001000101100001011001101000
00000000000000010000000100010111

出力例 2

0

入力例 3

6
0111001111111111111111101111111111111111111110111111111111111110
0111001111111111111111111111111111110111111111111001000000010001

出力例 3

2020

問題文

正の整数 M, L が与えられる．M 変数ブール関数 F\colon \{0, 1\}^M \to \{0, 1\} を次のように定める：F(x_0, \ldots, x_{M-1}) は x_0, \ldots, x_{M-1} のうち 1 が L 個以上であるとき 0 であり，1 が L 個未満であるとき 1 である．

また，正の整数 N および N 変数ブール関数 G\colon \{0, 1\}^N \to \{0, 1\} が与えられる．F だけを使って，G を実現する以下の仕様を満たすプログラムを 1 つ求めよ．そのようなプログラムが存在しない場合はそれを指摘せよ．

プログラムは 10^4 個のブール変数 a[0], \ldots, a[10^4-1] を扱うことができる．プログラムは 0 個以上 10^4 個以下の命令からなり，それらが順に実行される．各命令は添え字 j, i_0, \ldots, i_{M-1} によって表され，F(a[i_0], \ldots, a[i_{M-1}]) を計算し，その結果を a[j] に代入することを意味する．

任意の (y_0, \ldots, y_{N-1}) \in \{0, 1\}^N に対し，プログラムの実行開始時に a[0], \ldots, a[N-1] の値が入力 y_0, \ldots, y_{N-1} であり他の変数が初期化されていない場合，実行終了時に a[N] の値が G(y_0, \ldots, y_{N-1}) でなければならない．また，実行の途中で初期化も代入もされていない変数を F の引数に渡してはならない．

簡易的な出力チェッカーがここから利用可能である．

制約

• 1 \le M \le 8．
• 1 \le L \le M．
• 1 \le N \le 8．

部分点

• N \le 2 を満たすデータセットに正解した場合は，10 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 90 点が与えられる．

入力例 1

2
1
3
00000101

出力例 1

3
2020 0 0
1224 2 2
3 2020 1224

この例では，F(x_0, x_1) = (x_0 \operatorname{NOR} x_1)，G(y_0, y_1, y_2) = (y_0 \operatorname{AND} y_2) である．