問題文

長さ 2^N の数列 (A_0, A_1, \dots, A_{2^N-1}) があります。最初、A_0=A_1=\dots=A_{2^N-1}=1 です。

K 回の操作を行います。i 回目の操作では、\text{popcount}(j \oplus C_i) = D_i であるような各 j \ (0 \leq j < 2^N) について、A_j を (A_j \times X_i)\bmod M で置き換えます。

操作をすべて行った後の A_0, A_1, \dots, A_{2^N-1} をそれぞれ求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 18
• 2 \leq M \leq 10^9
• 1 \leq K \leq 5 \times 10^5
• 0 \leq C_i < 2^N
• 0 \leq D_i \leq N
• 2 \leq X_i \leq 10^9

入力例 1

3 100 2
0 2 4
3 0 25

出力例 1

1 1 1 0 1 4 4 1

1 回目の操作では、A_3,A_5,A_6 が 1\times 4\bmod 100=4 になります。

2 回目の操作では、A_3 が 4\times 25 \bmod 100=0 になります。

入力例 2

4 998244353 7
0 2 4
3 0 25
9 4 37
4 1 16
6 3 8
1 4 68
13 3 97

出力例 2

1552 8 1 9700 1 64 229696 1 8 4 388 8 64 8 68 1

問題文

ある空でない文字列 D, R（両者は一致しても良い）を用いて S = D + R + D と表せるとき、文字列 S は DRD 文字列であるといいます。ここで、+ は文字列の連結を表します。

使える文字が M 種類あるとき、長さ N の DRD 文字列として考えられるものの数を 998244353 で割った余りを求めてください。

制約

• 入力は全て整数
• 3 \leq N \leq 10^6
• 1 \leq M \leq 10^6

入力例 1

6 2

出力例 1

40

使える 2 種類の文字を a, b とすると、例えば abbaab, aaaaaa は長さ 6 の DRD 文字列です。一方、abbabb, aaabbb は DRD 文字列ではありません。

入力例 2

3017 7801

出力例 2

515391664

問題文

整数 N,M が与えられます。あなたは縦 N マス、横 M マスのマス目の各マスに 1 以上 NM 以下の整数を 1 つずつ書き込む必要があります。

以下を満たす書き込み方を平等な書き込み方とします。

• 1 以上 NM 以下の整数は全てどれかのマスに一度ずつ書き込まれている。
• 各行のマスに書き込まれた M 個の整数の和は全て等しい。

平等な書き込み方が存在するかを判定し、存在する場合はその一例を示してください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力は全て整数
• 1 \leq T \leq 10^4
• 1 \leq N, M
• 1 \leq NM \leq 3 \times 10^5
• 1 つの入力に含まれるテストケースについて、NM の総和は 5 \times 10^5 以下

入力例 1

2
2 2
10 1

出力例 1

Yes
1 4
2 3
No

• 1 番目のテストケースについて、 1 行目も 2 行目も、その行のマスに書き込まれた 2 つの整数の総和は 5 = 1+4 = 2+3 です。
• 2 番目のテストケースについて、平等な書き込み方が存在しないことが示せます。

問題文

N 枚のカードが横一列に並んでいます。 最初、文字列 S の i 文字目が 1 のとき左から i 枚目のカードは表を向いていて、0 のとき裏を向いています。

あなたは以下の操作を 10^6 回まで行うことができます。

• 一番右にあるカードを一番左に移動する。その後、移動させたカードが表を向いているなら左から A_1,A_2,\dots,A_P 枚目のカードの表裏を全て反転させる。そして、左から B_1,B_2,\dots,B_Q 枚目のカードの表裏を全て反転させるか、何もしないかのどちらかを選択する。

操作の結果、文字列 T の i 文字目が 1 のとき左から i 枚目のカードは表を向いていて、0 のとき裏を向いているようにしたいです。

10^6 回以下の操作により条件を満たすことができるかを判定し、条件を満たすことが可能な場合は操作回数が最小となるような操作列を 1 つ出力してください。

制約

• 入力される数値は全て整数
• 1 \leq N \leq 5000
• S, T は 0, 1 のみからなる長さ N の文字列
• S \neq T
• 1 \leq P, Q \leq N
• 1 \leq A_1 < A_2 < \dots < A_P \leq N
• 1 \leq B_1 < B_2 < \dots < B_Q \leq N

入力例 1

5
00001
00111
3
1 2 3
2
3 5

出力例 1

4
1001

1 度目の操作において、まず一番右のカードを一番左に移すとカードの状態は 10000 になり、移動させたカードが表を向いているため、左から A_1,A_2,A_3 枚目（1,2,3 枚目）のカードの表裏を全て反転させて 01100 になります。その後、左から B_1,B_2 枚目（3,5 枚目）のカードの表裏を全て反転させることを選択すれば 01001 になります。 以後も出力例に従って操作すると、2 回目の操作で 01000 に、3 回目の操作で 00100 に、4 回目の操作で 00111 になります。 これよりも操作回数が少ない方法は存在しないため、出力例は正しい出力です。

入力例 2

4
0110
1000
2
1 2
4
1 2 3 4

出力例 2

-1

どのように操作しても 10^6 回以下で条件を満たすことができないため、-1 を出力します。

問題文

頂点に 1,2,\ldots,N の番号が付いた N 頂点 M 辺の連結無向グラフがあります。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。グラフは多重辺をもつ場合がありますが、自己ループはもちません。

W = 0,1,\ldots,K それぞれに対して、以下の問題を解いてください。

各 i (1\leq i\leq M) について i 番目の辺に重み w_i\in \lbrace 0,1,\ldots,L \rbrace を割り当てる方法で、グラフの任意の全域木の重みがちょうど W になるようなものが存在するか判定してください。ただし、全域木の重みとは全域木に含まれる全ての辺の重みの総和のことです。また、存在するならばそのような割り当て全体における (w_1)^2+(w_2)^2+\cdots +(w_M)^2 の最小値を求めてください。

制約

• 入力は全て整数
• 2 \leq N \leq 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq L \leq K \leq 10^5
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• 与えられる無向グラフは連結である

入力例 1

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

出力例 1

0 1 3 4

例えば W = 2 のときは (w_1,w_2,w_3,w_4) = (0,1,1,1) とすれば、グラフの任意の全域木の重みは 2 になります。

入力例 2

2 3 2 1
1 2
2 1
1 2

出力例 2

0 3 -1

グラフの任意の全域木の重みを 2 にすることはできません。

与えられるグラフは多重辺をもつ場合があることに注意してください。

入力例 3

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

出力例 3

0 1 2 5 6 7 10 13 22 25

問題文

整数 i,j (0 \leq i \leq K, 0 \leq j < 2^{K-i}) を用いて [2^i j, 2^i (j+1)) と表せる区間をセグメント木的な区間と呼ぶことにします。

整数 l,r (0 \leq l < r \leq 2^K) に対し、区間 [l,r) をセグメント木的な区間の和集合として表す方法は必ず 1 つ以上あることが証明できます。このときの用いる区間の最小個数を f(l,r) と表します。

k = 1,2,\dots,2K-2 それぞれに対して、以下の問題を解いてください。

整数 l,r (0 \leq l < r \leq 2^K) の組であって、f(l,r)=k となるような組の総数を 998244353 で割った余りを求めてください。

制約

• 入力は全て整数
• 2 \leq K \leq 5 \times 10^5

入力例 1

3

出力例 1

15 14 6 1

たとえば k = 4 のときは、f(l, r) = k となるのは l = 1, r = 7 のときのみなので、1 を出力します。

入力例 2

5

出力例 2

63 110 132 114 70 30 8 1

入力例 3

10

出力例 3

2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1

問題文

ある池でマラソン大会が開催されます。池は円形で、池の外周に沿って時計回りに等間隔に 1, 2,\ldots, 2N の印がつけられています。マラソン大会の参加者は 2N 人いて、そのうち N 人が赤色の帽子を、残りの N 人が白色の帽子を被っています。

マラソン大会は以下のように実行されます。

• 2N 個ある印それぞれについて、ちょうど 1 人がその位置につく。
• 印 1 が付けられた位置にいる人がバトンを持って時計回りに走り始める。
• i 番目 (1 \le i \le 2N - 1) に走る人は、最初に自分と異なる色の帽子を被っている人のいる位置に到達するまで走り続ける。到達したら、その相手にバトンを渡して池から離れる。バトンを渡された人は、時計回りに走り始める。
• 2N 番目に走る人は、印 1 が付けられた位置まで走りマラソン大会を終了する。

池 1 周の長さを 1 とすると、2N 人が走る距離の合計は整数になり、これを L とします。

ありうる 2N 人の配置は (2N)! 通りありますが、その全てについての L の総和を 998244353 で割った余りを求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 10^6

入力例 1

1

出力例 1

2

ありうる配置は 2 通りありますが、いずれの場合も L=1 となります。

入力例 2

2

出力例 2

40

参加者の被っている帽子の色が印 1 が付けられた位置から順に

• 赤赤白白のときは L=2
• 赤白赤白のときは L=1
• 赤白白赤のときは L=2
• 白赤赤白のときは L=2
• 白赤白赤のときは L=1
• 白白赤赤のときは L=2

となります。それぞれに 4 通りの配置があるので、ありうる 24 通りの配置全てについての L の総和は (2 + 1 + 2 + 2 + 1 + 2) \times 4 = 40 です。

入力例 3

3

出力例 3

1656

入力例 4

4

出力例 4

112896

入力例 5

5

出力例 5

11750400

問題文

N 種類の紙幣があり、i 種類目の紙幣は A_i 円札です。それぞれの紙幣は 10^{100} 枚ずつあります。ここで A_1 < A_2 < \cdots < A_N であり、各 i \: (1 \leq i \leq N - 1) に対して A_{i+1} は A_i の倍数です。

これらの紙幣から何枚か選んで、袋に入れることを考えます。

紙幣を袋に入れる方法のうちで次の条件を満たすものを、x 円の良い入れ方と呼びます。

• 袋に入っている紙幣の合計金額は x 円である。
• 袋に入っている紙幣から何枚か選んで、その合計金額を \dfrac{x}{2} 円にする方法は存在しない。

また、x 円が良い金額であるとは、x 円の良い入れ方が存在することをいいます。

L 円以上 R 円以下の金額のうち、良い金額は何個あるか求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 60
• 1 \leq L \leq R \leq 10^{18}
• 1 = A_1 < A_2 < \cdots < A_N \leq 10^{18}
• A_{i+1} は A_i の倍数 (1 \leq i \leq N - 1)

入力例 1

3 20 30
1 5 10

出力例 1

8

例えば 10 円札を 3 枚入れると 30 円の良い入れ方となるので、30 円は良い金額です。

一方、20 円の良い入れ方は存在しないので、20 円は良い金額ではありません。

21, 23, 25, 26, 27, 28, 29, 30 円の 8 個が答えです。

入力例 2

8 500007484602844543 985892611352151235
1 1971 151767 10927224 87417792 118975614912 263174060185344 43686893990767104

出力例 2

483957600323779237

問題文

長さ N の整数列 (A_1, A_2, \dots, A_N), (B_1, B_2, \dots, B_N), (C_1, C_2, \dots, C_N) が与えられます。

1 \leq i \leq N, 1 \leq j \leq N, 1 \leq k \leq N を満たす整数 i,j,k の選び方 N^3 通りそれぞれについて、A_i + B_j + C_k の値を求めたとき、そのうち K 番目に小さい値を求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 50000
• 1 \leq K \leq \min\lbrace N^3, 10^9\rbrace
• 0 \leq A_i \leq 10^9
• 0 \leq B_j \leq 10^9
• 0 \leq C_k \leq 10^9

入力例 1

2 4
1 2
3 4
5 6

出力例 1

10

整数 i,j,k の選び方 8 通りに対応する A_i+B_j+C_k の値は、小さい順に 9, 10, 10, 10, 11, 11, 11, 12 となるので、そのうち 4 番目に小さい値は 10 です。

入力例 2

10 40
11 9 13 12 15 11 11 2 11 17
3 1 10 2 12 18 9 11 11 15
14 9 4 14 16 9 20 2 1 18

出力例 2

14

入力例 3

1 1
1000000000
1000000000
1000000000

出力例 3

3000000000

問題文

N 本のまっすぐな棒があります。i 番目の棒の長さは L_i です。

これらの棒から 3 本を選び、それらを 3 辺とする（非退化な）三角形を作ります。このような棒の選び方が存在するかを判定し、存在する場合は作れる三角形の面積の最大値を 2 乗した値を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力は全て整数
• 1 \leq T \leq 2 \times 10^5
• 3 \leq N \leq 2 \times 10^5
• 2 \leq L_i \leq 20000
• L_i は偶数
• 1 つの入力に含まれるテストケースについて、N の総和は 2 \times 10^5 以下

入力例 1

3
5
2 2 2 2 2
7
2 6 4 10 8 10 20
5
4 16 36 64 100

出力例 1

3
1344
-1

2 番目のテストケースでは、3 辺の長さが 8,10,10 の三角形が最大で、面積は 8\sqrt{21} となります。この 2 乗は 1344 です。

3 番目のテストケースでは、どの 3 本の棒を組み合わせても三角形を作ることはできません。

問題文

1 以上 2N-1 以下の奇数からなる長さ M の整数列 (A_1,A_2,\dots,A_M) が与えられます。

(1,2,\dots,2N) の順列 P=(P_1,P_2,\dots,P_{2N}) のうち、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• 0, 1 のみからなる長さ 2N の文字列 S であって、以下の条件を全て満たすものが存在する。
  • S は N 文字の 0 と N 文字の 1 からなる文字列である。
  • i=1,2,\dots,M に対し、S の 1,2,\dots,A_i 文字目に登場する文字のうち、最も多いのは 0 である。
  • i=1,2,\dots,M に対し、S の P_1,P_2,\dots,P_{A_i} 文字目に登場する文字のうち、最も多いのは 0 である。

制約

• 入力は全て整数
• 1 \leq M \leq N \leq 10^{5}
• 1 \leq A_1 < A_2 < \dots < A_M \leq 2N-1
• A_i は奇数

入力例 1

2 2
1 3

出力例 1

14

例えば P=(2,1,3,4) の場合、S= 0011 とすると 3 つの条件を全て満たす文字列となっています。

一方、P=(4,3,2,1) の場合、3 つの条件を全て満たす長さ 4 の文字列は存在しません。

入力例 2

3 1
3

出力例 2

684

問題文

英小文字からなる長さ N の文字列 S=S_1 S_2 \dots S_N があります。以下の操作をちょうど 1 回行うとき、最終的な S としてありうる文字列の種類数を求めてください。

• 1 \le l \le r \le N を満たす整数 l, r を選び、S の l 文字目から r 文字目までを取り除く。つまり、操作後の S は S_1S_2\dots S_{l-1}S_{r+1}\dots S_N となる。

制約

• N は整数
• 1 \leq N \leq 5 \times 10^5
• S は英小文字からなる長さ N の文字列

入力例 1

5
abbab

出力例 1

11

得られる S としてありうるものは以下の 11 通りです。

• 空文字列
• a
• aab
• ab
• abab
• abb
• abba
• abbb
• b
• bab
• bbab

入力例 2

5
aaaaa

出力例 2

5

入力例 3

4
utpc

出力例 3

10

問題文

UT 鉄道 PC 本線は、1 本の路線に沿って N+1 個の駅が設置されていて、始発駅から終着駅まで順に 0,1,\ldots,N の番号が付いています。各 i (0\leq i\leq N-1) について、駅 i と駅 i+1 は隣り合っていて、この駅間の混雑度は C_i です。現在、駅 0, N には車両基地が併設されています。

次のダイヤ改正では、まず以下の操作を何回か繰り返すことで車両基地を建設します。

• ある i (1\leq i\leq N-1) を選び、駅 i に車両基地を併設する。これにはコスト A_i がかかる。

次に、以下の操作を何回か繰り返すことで車両基地間に列車を運行させます。

• 車両基地が併設されている駅 l,r (l < r) を選び、この間に列車を 1 本運行させる。このとき、駅 i と駅 i+1 の間 (l\leq i\lt r) の混雑度が 1 減少する。これにはコスト r-l がかかる。

ダイヤ改正の目標は、全ての i (0\leq i\leq N-1) について、駅 i と駅 i+1 の間の混雑度が 0 以下になるようにすることです。車両基地の建設および列車の運行に必要な総コストの最小値を求めてください。

制約

• 入力は全て整数
• 2 \leq N \leq 5\times 10^5
• 1 \leq C_i \leq 10^9 (0\leq i\leq N-1)
• 1 \leq A_i \leq 10^9 (1\leq i\leq N-1)

入力例 1

4
3 1 4 1
5 9 2

出力例 1

15

駅 3 に車両基地を併設し、駅 0,3 間に列車を 3 本、駅 0,4 間に列車を 1 本運行させます。すると、各駅間の混雑度は 0 以下になり、総コストは 15 となります。

入力例 2

9
28 35 19 27 84 98 78 79 60
40 35 54 63 72 71 27 94

出力例 2

682

問題文

N 個の + と M 個の - からなる長さ N+M の文字列 S、および M 個の整数からなる集合 A=\lbrace A_1,A_2,\dots,A_M\rbrace が与えられます。

集合 X=\lbrace \rbrace,Y=\lbrace \rbrace を用意し、i=1,2,\dots,N+M の順に以下を行うことを考えます。

• S の i 文字目が + のとき、1 から N までの整数のうち、X,Y のいずれにも含まれない整数を 1 つ選び、X に追加する。
• S の i 文字目が - のとき、X に含まれる整数の最小値 m を X から削除し、m を Y に追加する。制約から、操作の直前に X は空でないことが保証される。

一連の操作で X に追加する整数の順番は N! 通り考えられますが、そのうち一連の操作を終えた後に Y=A となっているような順番の数を 998244353 で割った余りを求めてください。

制約

• 入力される数値は全て整数
• 1 \leq M \leq N \leq 300
• S は N 個の + と M 個の - からなる長さ N+M の文字列
• i=1,2,\dots,N+M に対し、S の i 文字目までに登場する - の数は i 文字目までに登場する + の数を超えない
• 1 \leq A_1 < A_2 < \dots < A_M \leq N

入力例 1

4 2
++-++-
1 3

出力例 1

4

条件を満たす一連の操作の例として以下のようなものが考えられます。

• i=1 のとき、X に 3 を追加する。X=\lbrace 3\rbrace,Y=\lbrace \rbrace となる。
• i=2 のとき、X に 4 を追加する。X=\lbrace 3,4\rbrace,Y=\lbrace \rbrace となる。
• i=3 のとき、X に含まれる整数の最小値 3 を X から削除して Y に追加する。X=\lbrace 4\rbrace,Y=\lbrace 3\rbrace となる。
• i=4 のとき、X に 2 を追加する。X=\lbrace 2,4\rbrace,Y=\lbrace 3\rbrace となる。
• i=5 のとき、X に 1 を追加する。X=\lbrace 1,2,4\rbrace,Y=\lbrace 3\rbrace となる。
• i=6 のとき、X に含まれる整数の最小値 1 を X から削除して Y に追加する。X=\lbrace 2,4\rbrace,Y=\lbrace 1,3\rbrace となる。

入力例 2

6 4
++-++---++
2 3 4 6

出力例 2

48

S の末尾は - とは限りません。

入力例 3

20 10
++++-++++++--+--+-+++++--+-++-
1 2 3 4 5 6 7 9 12 13

出力例 3

179396825

問題文

N 個の相異なる正整数からなる数列 A=(A_1,A_2,\ldots,A_N) が与えられます。A の要素を並び替えて数列 B=(B_1,B_2,\ldots,B_N) を得るとき、以下の値の最小値を求めてください。

\displaystyle\left\lfloor\frac{B_2}{B_1}\right\rfloor + \left\lfloor\frac{B_3}{B_2}\right\rfloor + \cdots + \left\lfloor\frac{B_{N}}{B_{N-1}}\right\rfloor + \left\lfloor\frac{B_1}{B_N}\right\rfloor

ただし、実数 x に対して \left\lfloor x\right\rfloor で x 以下の最大の整数を表します。

制約

• 入力は全て整数
• 2 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^{18}
• A_i\neq A_j (i\neq j)

入力例 1

3
2 3 6

出力例 1

3

(B_1,B_2,B_3) = (6, 2, 3) とすると、\displaystyle\left\lfloor\frac{B_2}{B_1}\right\rfloor + \left\lfloor\frac{B_3}{B_2}\right\rfloor + \left\lfloor\frac{B_1}{B_3}\right\rfloor = \left\lfloor\frac{2}{6}\right\rfloor + \left\lfloor\frac{3}{2}\right\rfloor + \left\lfloor\frac{6}{3}\right\rfloor = 0 + 1 + 2 = 3 となります。

入力例 2

2
15 4

出力例 2

3

入力例 3

9
284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422

出力例 3

4580