問題文

マーブリングの操作を高々 500 回行うことで，以下の画像に近い画像を作り上げよ．後述の達成条件を満たしていれば，カラフルな画像にしてもよい．

キャンバスとマーブリング操作

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

キャンバスに対して，以下の 2 種類のマーブリング操作を行うことができる．

• drop: 画素 C(x, y) に色 (r, g, b) の絵の具を垂らして半径 d の円を作る．
  • この操作によって点 P の色は C + \sqrt{1+\frac{d^2}{|P-C|^2}} (P-C) に移動する．
  • ただし，C からの距離が d 以下の画素は色が (r, g, b) になる．
• tine_line: 2 点 A(x_1, y_1), B(x_2, y_2) を通る直線に沿って，A から B の方向へ，水面に細い棒を通す．
  • この操作によって点 P の色は P + zu^d M に移動する．ここで，z,u,d,M はそれぞれ以下のように決まる．
    • N を \overrightarrow{AB} に直交する単位ベクトルとして d=|(P-B)\cdot N|．
    • M は \overrightarrow{AB} と同じ方向の単位ベクトル．
    • 1 \le z \le 100 は絵の具の移動量を表す指定可能なパラメタ．大きい方が色が線に沿ってより大きく動く．
    • u = 2^{-1/c} (1 \le c \le 10) は絵の具の移動の範囲を表す指定可能なパラメタ．大きい方がより周囲の色も巻き込んで動く．

実際には，点 P が操作によって F(P) に移るとき，操作後の画素 Q の色は操作前の画素 F^{-1}(Q) の色として決める (座標は最も近い整数に丸める)．また，キャンバスの範囲外の色はすべて黒 ((R, G, B) = (0, 0, 0)) とする．

2 種類のマーブリング操作による点の移動について，以下が成り立つことを使ってもよい．

• Q = C + \sqrt{1+\frac{d^2}{|P-C|^2}} (P-C) のとき， P = C + \sqrt{1-\frac{d^2}{|Q-C|^2}}(Q-C)
• Q = P+zu^d M のとき， P = Q - zu^{d'}M (ここで d'=|(Q-B)\cdot N|)

達成条件

色 (R, G, B) は R + G + B \ge 255 を満たすとき明るい色と言い，R + G + B < 255 のとき暗い色と言う．ある画像が「目的画像に近い」とみなされるためには，目的画像において白い部分が明るい色になっており，黒の部分が暗い色になっている必要がある．

厳密には，目的画像と出力画像で明暗が不一致であるような画素の数が 16\,000 以下であれば AC となる．

ここで，画素 (x, y) の明暗が不一致であるとは，画素 (x, y) の色が目的画像において白かつ出力画像において暗い色，もしくは目的画像において黒かつ出力画像において明るい色であることを言う．

データ・ビジュアライザ

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

• marbling/input.png: 目的画像．画像サイズは横 500 px，縦 500 px である．
• marbling/input.txt: 目的画像に対応する入力データ．実際の採点に用いられるものと同一．

また，ビジュアライザが利用可能である．操作列の可視化や，達成条件の判定などの機能を備えている．ページ下部の「マーブリング操作を描画する」機能は，正しいマーブリング操作を表す行だけを読み込む (よって，後述の出力形式に従ったものを入れたときは，最初の行は単に読み飛ばされる)．

問題文

整数 N, K, P および，文字 A, B からなる長さ N の文字列 S が与えられる．各 k = 1, 2, \ldots, K に対して以下の問に答えよ (各 k に関する問は別々に考えよ)．

くろうさとしろうさが問題の速解き競争を行う．問題は 1 問ずつ出題され，i 問目 (i = 1, 2, \ldots) は以下のようになる：

• i \le N かつ S の i 文字目が A である場合，確率 \frac{P}{100} でくろうさが先に解き，確率 1 - \frac{P}{100} でしろうさが先に解く．
• i \le N かつ S の i 文字目が B である場合，確率 1 - \frac{P}{100} でくろうさが先に解き，確率 \frac{P}{100} でしろうさが先に解く．
• i > N の場合，確率 \frac{1}{2} でくろうさが先に解き，確率 \frac{1}{2} でしろうさが先に解く．

「i 問目をくろうさが先に解く」という事象たちは互いに独立である．

「先に解いた問題」が k 問に到達したうさぎが現れた時点で競争を終了し，そのうさぎの優勝とする．くろうさが優勝する確率と \frac{1}{2} の大小を比較せよ．

制約

• 1 \le N \le 10^5．
• 1 \le K \le 10^5．
• 0 \le P \le 100．
• S は A, B からなる長さ N の文字列である．

入力例 1

2 2 25
AB

出力例 1

-0

k = 1 のとき，1 問目をくろうさが先に解く確率は \frac{1}{4} なので，くろうさが優勝する確率は \frac{1}{4} である．

k = 2 のとき，

• 1 問目をくろうさが先に解き，2 問目をくろうさが先に解く確率は \frac{3}{16}
• 1 問目をくろうさが先に解き，2 問目をしろうさが先に解き，3 問目をくろうさが先に解く確率は \frac{1}{32}
• 1 問目をしろうさが先に解き，2 問目をくろうさが先に解き，3 問目をくろうさが先に解く確率は \frac{9}{32}

なので，くろうさが優勝する確率は \frac{1}{2} である．

入力例 2

10 4 99
AABBBAABBB

出力例 2

++-+

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) と Q=(Q_1,Q_2,\ldots,Q_N) が与えられる．以下の操作を高々 N^2 回行って P を Q に一致させられるか判定し，可能な場合はそのような操作列を 1 通り求めよ．

• 次の条件のうち少なくとも一方を満たす整数 i を選び，P_i と P_{i+1} の値を入れ替える．
  • 1 \leq i \leq N-2 かつ \min(P_i,P_{i+1}) < P_{i+2} < \max(P_i,P_{i+1})
  • 2 \leq i \leq N-1 かつ \min(P_i,P_{i+1}) < P_{i-1} < \max(P_i,P_{i+1})

制約

• 2 \leq N \leq 1000．
• (P_1,P_2,\ldots,P_N) は (1,2,\ldots,N) の順列である．
• (Q_1,Q_2,\ldots,Q_N) は (1,2,\ldots,N) の順列である．

入力例 1

3
2 1 3
2 3 1

出力例 1

1
2

入力例 2

3
1 2 3
1 3 2

出力例 2

-1

問題文

非負整数 N, A, B, C が与えられる．

正整数列 (x_0, x_1, \ldots, x_N) であって，以下の条件をすべて満たすものの個数を 998244353 で割った余りを求めよ：

• x_0 = 2^A \times 2^B．
• x_N = ((2^A + 1) \times 2^C) - 1．
• 各 i = 0, 1, \ldots, N - 1 に対し，x_{i+1} \in \{ \lfloor x_i/2 \rfloor, 2 x_i, 2 x_i + 1 \}．

制約

• 0 \le N, A, B, C \le 10^7．

入力例 1

4 1 1 1

出力例 1

7

条件を満たす組 (x_0, x_1, x_2, x_3, x_4) は以下の 7 個である：

• (4, 2, 1, 2, 5)
• (4, 2, 4, 2, 5)
• (4, 2, 5, 2, 5)
• (4, 2, 5, 10, 5)
• (4, 2, 5, 11, 5)
• (4, 8, 4, 2, 5)
• (4, 9, 4, 2, 5)

入力例 2

9 2 0 1

出力例 2

1164

入力例 3

1 0 2 4

出力例 3

0

入力例 4

2022 12 24 14

出力例 4

426021617

問題文

整数 P_1, P_2, \ldots, P_N が与えられる．

N 枚のコインがあり，それぞれ 1, 2, \ldots, N の番号が付いている．どの 2 枚のコインも区別できる．うさぎがこれからある特殊な方法でこれらのコインを一斉に投げ，各コインが表または裏のいずれか一方になる．

コイン i は確率 \frac{P_i}{100} で表になり，確率 1 - \frac{P_i}{100} で裏になることがわかっている (1 \le i \le N)．また，どの異なる 2 枚のコイン i, j についても，コイン i が表になる事象とコイン j が表になる事象は独立であることがわかっている (1 \le i, j \le N，i \ne j)．

このとき，すべてのコインが表になる確率として考えられる最小値を求めよ．この問題の制約下で最小値が存在することが証明できる．

制約

• 1 \le N \le 100．
• 0 \le P_i \le 100   (1 \le i \le N)．

部分点

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

入力例 1

2
13 77

出力例 1

0.1001

\frac{13}{100} \times \frac{77}{100} = \frac{1001}{10000} である．

問題文

無向グラフ G は 1, 2, \ldots, N を頂点とし，頂点 u と頂点 v を結ぶ辺はちょうど A_{u,v} 本ある (1 \le u, v \le N)．すべての辺は区別される．

各 k = 0, 1, \ldots, \lfloor N/2 \rfloor に対し，G の大きさ k のマッチングの個数を 2^{64} で割った余りを求めよ．

(G の大きさ k のマッチングとは，G の辺 k 本からなる集合であって，それらの端点 2 k 個が相異なるようなものを指す．)

制約

• 1 \le N \le 40．
• 0 \le A_{u,v} < 2^{64}   (1 \le u, v \le N)．
• A_{u,u} = 0   (1 \le u \le N)．
• A_{u,v} = A_{v,u}   (1 \le u, v \le N)．

入力例 1

4
0 10 300 0
10 0 5 400
300 5 0 20
0 400 20 0

出力例 1

1 735 120200

G の大きさ 2 のマッチングは，以下の通りである．

• 頂点 1, 2 を結ぶ辺のうち 1 本と，頂点 3, 4 を結ぶ辺のうち 1 本からなるものが 200 個
• 頂点 1, 3 を結ぶ辺のうち 1 本と，頂点 2, 4 を結ぶ辺のうち 1 本からなるものが 120\,000 個

入力例 2

7
0 1 1 1 1 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 0 1 1 1
1 1 1 1 0 1 1
1 1 1 1 1 0 1
1 1 1 1 1 1 0

出力例 2

1 21 105 105

入力例 3

10
0 8629318490492529455 16934461172002342162 16689922355946803515 6532726440738276996 1194408499640297875 15866676155001669889 6498797546467110859 16876940315014902410 12387509481131737340
8629318490492529455 0 11507224725899007093 8715646015311805917 10082055328422634515 11661112510609506937 5671467989936109679 9958089075065687029 1044511129638713462 9641449008999128869
16934461172002342162 11507224725899007093 0 9017212196119468141 8742031656924741889 16712732165713258491 12486619021854068086 8079880079267306335 7411259632269635598 847494329973810398
16689922355946803515 8715646015311805917 9017212196119468141 0 16283252096557152371 8615030617835929416 17667878928797645683 18446439882335127774 11475081586957078864 15537196317840490094
6532726440738276996 10082055328422634515 8742031656924741889 16283252096557152371 0 2328769271400341339 5743580703459253102 13482125554117518013 8310663885706538154 15657502149293391713
1194408499640297875 11661112510609506937 16712732165713258491 8615030617835929416 2328769271400341339 0 13134573721194912427 3260072811817230082 12647757802949221999 15331084503094140917
15866676155001669889 5671467989936109679 12486619021854068086 17667878928797645683 5743580703459253102 13134573721194912427 0 5011674754910118042 4293452480892783480 12853153721226986708
6498797546467110859 9958089075065687029 8079880079267306335 18446439882335127774 13482125554117518013 3260072811817230082 5011674754910118042 0 8466317684966562639 13151347917827920992
16876940315014902410 1044511129638713462 7411259632269635598 11475081586957078864 8310663885706538154 12647757802949221999 4293452480892783480 8466317684966562639 0 1834230013668150904
12387509481131737340 9641449008999128869 847494329973810398 15537196317840490094 15657502149293391713 15331084503094140917 12853153721226986708 13151347917827920992 1834230013668150904 0

出力例 3

1 13998873960259808869 16134958027077044128 15075909322183550749 13815169532537848652 14625654317779811048

問題文

1 個の入力ファイルにつき T 個のテストケースが与えられる．各テストケースで整数 N, S が与えられるので，以下の問に答えよ．

整数 A_0, A_1, \ldots, A_{4N-1} を以下のように定める．数式および C++ コード片で示す：

1. 変数 s を s \gets S とする．
2. i = 0, 1, \ldots, 4 N - 1 に対しこの順で，A_i \gets \lfloor i/4 \rfloor + 1 とする．
3. i = 0, 1, \ldots, 4 N - 1 に対しこの順で，s \gets (s \times 2022) \bmod 998244353 としてから，s \not\equiv 0 \pmod{2} ならば A_i \gets -A_i とする．
4. i = 0, 1, \ldots, 4 N - 1 に対しこの順で，s \gets (s \times 2022) \bmod 998244353 としてから，A_{s \bmod (i+1)} と A_i の値を入れ替える．

#include <vector>
std::vector<int> Generate(int N, long long S) {
  long long s = S;
  std::vector<int> A(4 * N);
  for (int i = 0; i < 4 * N; ++i) {
    A[i] = i / 4 + 1;
  }
  for (int i = 0; i < 4 * N; ++i) {
    s = (s * 2022) % 998244353;
    if (s % 2 != 0) {
      A[i] = -A[i];
    }
  }
  for (int i = 0; i < 4 * N; ++i) {
    s = (s * 2022) % 998244353;
    int j = s % (i + 1);
    int t = A[j];
    A[j] = A[i];
    A[i] = t;
  }
  return A;
}

各 j = 1, 2, \ldots, N に対して +j と -j のいずれかちょうど一方を「良い整数」と決める方法 2^N 通りのうち，以下の N 個の条件をすべて満たすものが存在するかどうか判定し，存在する場合はそのような方法を 1 通り求めよ：

• A_0, A_1, A_2, A_3 のうち少なくとも 1 個は良い整数である．
• A_4, A_5, A_6, A_7 のうち少なくとも 1 個は良い整数である．
• \cdots
• A_{4N-4}, A_{4N-3}, A_{4N-2}, A_{4N-1} のうち少なくとも 1 個は良い整数である．

制約

• 1 \le T \le 10．
• 1 \le N \le 10^5．
• 0 \le S < 998244353．

入力例 1

2
3 1
4 20221224

出力例 1

++-
+--+

1 個目のテストケースでは，

• (A_0, A_1, A_2, A_3) = (-3, -3, -2, +3)
• (A_4, A_5, A_6, A_7) = (+2, +1, -1, +3)
• (A_8, A_9, A_{10}, A_{11}) = (+2, +1, -2, +1)

となる．例えば，+1, +2, -3 を良い整数と決めれば条件を満たす．

2 個目のテストケースでは，

• (A_0, A_1, A_2, A_3) = (+3, -2, +2, -3)
• (A_4, A_5, A_6, A_7) = (+4, +1, +3, -1)
• (A_8, A_9, A_{10}, A_{11}) = (+4, +2, +1, +4)
• (A_{12}, A_{13}, A_{14}, A_{15}) = (-1, -2, -3, -4)

となる．例えば，+1, -2, -3, +4 を良い整数と決めれば条件を満たす．

問題文

1 個の入力ファイルにつき T 個のテストケースが与えられる．各テストケースで次のようなグラフ G が与えられるので，以下の問に答えよ．

G は N 頂点 M 辺からなる連結な単純無向グラフである．頂点には 1 から N までの番号がついており，i 番目の辺は頂点 A_i と B_i を結んでいる (1 \le i \le M)．

今，G の頂点はすべて白色で塗られている．これから，くろうさとしろうさが次のゲームを行う．

1. まず，くろうさが好きな頂点を 1 個選び，黒色で塗る．
2. その後，白色に塗られている頂点が存在する限り，しろうさが以下の操作を繰り返す：
   • 黒色で塗られている頂点に隣接しているような頂点を 1 個または 2 個選ぶ．選んだ頂点をすべて黒色で塗る．

しろうさの操作回数をスコアと呼ぶ．くろうさの目的はスコアの最大化であり，しろうさの目的は最小化である．両者が最適に行動した場合のゲームのスコアを求めよ．

制約

• 1 \le T \le 1.5 \times 10^5．
• 2 \le N \le 3 \times 10^5．
• N-1 \le M \le 3 \times 10^5．
• 1 \le A_i,B_i \le N   (1 \le i \le M)．
• グラフ G は単純かつ連結である．
• 1 個の入力ファイルにおける N の総和は 3 \times 10^5 を超えない．
• 1 個の入力ファイルにおける M の総和は 3 \times 10^5 を超えない．

入力例 1

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

出力例 1

2
2

1 個目のテストケースでは，くろうさが頂点 1 または 3 を選ぶことで，しろうさの操作回数が 2 回になる．

2 個目のテストケースでは，くろうさが選んだ頂点によらず，しろうさの操作回数が 2 回になる．

入力例 2

2
5 8
5 1
2 3
2 4
5 2
1 3
3 5
1 4
4 5
20 40
13 10
13 19
12 15
14 7
1 17
8 17
13 7
10 7
16 2
5 20
12 1
3 12
19 7
8 20
20 16
2 5
14 13
3 9
13 6
5 16
4 1
2 4
8 16
14 10
8 2
11 8
15 3
18 5
17 20
11 17
6 10
16 11
15 1
9 6
19 6
8 4
2 11
20 11
10 19
16 18

出力例 2

2
11