問題文

(1,2,\ldots,N) を並び替えて得られる数列 P のうち以下の条件を満たすものの個数を求め、998244353 で割ったあまりを出力してください。

• すべての i\ (2 \leq i \leq N) について、以下のいずれかが成り立つ。
  • すべての j\ (1 \leq j \lt i) について、P_j \lt P_i
  • すべての j\ (1 \leq j \lt i) について、P_j \gt P_i

制約

• 2 \leq N \leq 10^{18}
• N は整数

入力例 1

2

出力例 1

2

(1,2) を並び替えて得られる数列は (1,2) と (2,1) の 2 つですが、そのどちらもが問題文中の条件を満たします。

入力例 2

659636104093210683

出力例 2

512716103

998244353 で割ったあまりを出力してください。

原案: penguinman

問題文

A, B のみからなる長さ N の文字列 S, T が与えられます。以下の操作を 0 回以上繰り返すことで S を T に一致させられるかを判定し、可能なら必要な操作回数の最小値を求めてください。

• S_i=S_{i+1} であるような整数 i\ (1 \leq i \lt N) を選び、S_i と S_{i+1} を A, B のうち現在とは異なる文字にそれぞれ置き換える。

制約

• 2 \leq N \leq 2 \times 10^5
• S, T は A, B のみからなる長さ N の文字列

入力例 1

3
AAB
BAA

出力例 1

2

例えば以下のような手順で操作を行うのが最善です。

• i=1 として操作を行う。S は BBB となる。
• i=2 として操作を行う。S は BAA となり、これは T に一致する。

入力例 2

3
ABA
AAA

出力例 2

-1

そもそも操作を一回も行うことができず、S を T に一致させることはできないため、-1 を出力します。

入力例 3

4
ABAB
ABAB

出力例 3

0

S と T が既に一致しているため、一度も操作を行う必要がありません。

原案: NatsubiSogan

問題文

tada72 君は不思議な紙を拾いました。その紙には、 「この紙には 1 が 2 個、 2 が 3 個、 3 が 2 個、 4 が 1 個書かれている」と書いてありました。そして彼は、同じような性質を持つ紙を他にも作ってみたくなりました。

整数 N が与えられるので、次の 2 つの条件を満たす長さ N の数列 A が存在するか判定し、存在する場合は構築してください。

• 数列の要素は全て 1 以上 N 以下の整数
• 1 \leq i \leq N を満たす全ての整数 i に対し、 i=A_j(1 \leq j \leq N) を満たす整数 j は A_i-1 個存在する

制約

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

入力例 1

4

出力例 1

2 3 2 1

A には 1 が 1 個、 2 が 2 個、 3 が 1 個、 4 が 0 個含まれているので条件を満たしています。

入力例 2

2

出力例 2

-1

原案: tada72

問題文

この問題はインタラクティブな問題です。

kaage 君と penguinman 君は NG ワードゲームで遊んでいます。 このゲームは次のように進行します。

• penguinman 君が NG ワードとして、 0 または 1 で構成される長さ N の文字列を 1 つ決める。
• kaage 君が次のような質問を繰り返す。
  • 0 または 1 で構成される長さ 1 以上 3000 以下の文字列 S を 1 つ決める
  • NG ワードが S の部分列であるかを質問する
• 2000 回以下の質問で NG ワードを特定できたら kaage 君の勝ち、特定できなかったら penguinman 君の勝ちとなる。

kaage 君は忙しいので、代わりに NG ワードを特定するプログラムを書いてください。

ただし、文字列 X が文字列 Y の部分列であるとは、 Y の文字を 0 文字以上取り除き、残った文字を元の順番で並べた物が X となることを言います。

制約

• 1 \leq N \leq 1000
• N は整数

入出力

最初に、 N が以下の形式で与えられる。

N

次に、質問を繰り返し送る。この回数は 2000 回以下でなければならない。
質問する文字列を S として、質問は以下の形式で出力せよ。ただし、 S は 0 または 1 で構成される長さ 1 以上 3000 以下の文字列である必要がある。

? S

これに対する返答は、 Yes または No である。これは、 NG ワードが S の部分列であるかを表している。

NG ワードを答えるときは、その文字列を NG として、以下の形式で出力せよ。

! NG

NG ワードの出力は質問の回数に含まれないことに注意せよ。

なお、 2000 回以下の質問で NG ワードを特定できることは証明できる。

注意

• 出力した後に、出力を flush する必要がある。そうしない場合、 TLE する可能性がある。
• NG ワードを答えた後プログラムを終了させなかった場合、ジャッジ結果は不定である。
• 正しくない形式で出力をしたり、 2000 回より多くの質問をした場合は、ジャッジ結果は不定である。

入出力例

この入出力例では、 N=3 であり、 NG ワードは 110 であるときのジャッジとのやり取りの一例を示しています。
なお、これはあくまで入出力例であり、意味のあるやりとりをしているとは限らないことに注意してください。

原案: kaage

問題文

非負整数 K が与えられます。以下の条件を満たす正整数列 A=(A_1, A_2, \ldots, A_N) を 1 つ構築してください。

• 3 辺の長さがそれぞれ A_i, A_j, A_k である面積が正の三角形が存在するような整数組 (i, j, k) (1 \leq i < j < k \leq N) がちょうど K 個ある。

制約

• 0 \leq K \leq 10^9
• 入力は全て整数

入力例 1

3

出力例 1

5
1 2 3 4 5

A_i, A_j, A_k を 3 辺に持つ面積が正の三角形が存在するのは (i, j, k) = (2,3,4), (2,4,5), (3,4,5) の 3 つなので、条件を満たします。

入力例 2

0

出力例 2

3
1 10 100

入力例 3

10

出力例 3

5
10 10 10 10 10

原案: NatsubiSogan

問題文

しおむすび君は次のような問題を解いています。

Paken 王国は N 個の街 1, 2, \ldots, N と M 本の道路 1, 2, \ldots, M からなります。 道路の情報を表す長さ M の数列 A,B,C が与えられていて、道路 i は街 A_i と街 B_i を双方向に結び、通るのに C_i のコストがかかります。

Paken 王国では、技術室奥プログラミングコンテスト#6の開催に合わせて N 日間に渡りイベントを開催します。 i 日目には街 i でイベントが開催されるので、街 i に行く必要があります。 i = 1, 2, \ldots, N について、 i 日目に街 1 から街 i を通り街 N まで移動するのにかかるコストの合計の最小値を求めて下さい。 ただし、頂点 1,N も含め同じ頂点や同じ道路を複数回通ってもいいものとします。

しおむすび君にかかればこの問題は簡単です。 しおむすび君は i = 1, 2, \ldots, N それぞれについて、 i 日目の答えが D_i であると分かりました。

しかししおむすび君は抜けているところがあるので、 A, B, C が何であったか忘れてしまいました。 しおむすび君のために A, B, C として考えられるものを 1 つ見つけてあげてください。

ただし、そのようなものが存在しないときは、それを報告してください。

制約

• 1 \leq N,M \leq 10^5
• 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
• 入力は全て整数

入力例 1

5 7
5 5 6 6 5

出力例 1

Yes
1 2 1
1 3 2
1 4 6
2 4 5
2 5 4
3 4 3
4 5 1

この出力例では、例えば 3 日目に移動にかかるコストが最小になる経路は、道路 2, 6, 7 を順に通るものになります。 道路を移動するのにかかるコストはそれぞれ 2, 3, 1 なので、合計で 6 のコストがかかります。

入力例 2

5 4
10 10 10 10 10

出力例 2

Yes
1 2 1
2 3 2
3 4 3
4 5 4

入力例 3

3 100
1 3 2

出力例 3

No

条件を満たす A, B, C は存在しません。

原案: shiomusubi496

問題文

ある長さ M の整数列 B は、以下の条件を満たすときいい数列 と呼ばれます。

• 1 \leq i \lt j \lt M かつ |B_i-B_{i+1}|=|B_j-B_{j+1}| を満たす整数対 (i,j) が存在しない。

ペンギンくんの目標は、与えられる長さ N の整数列 A に対して以下の操作を 0 回以上任意の回数繰り返すことで、A をいい数列 にすることです。

• 1 \leq l \leq r \leq N を満たす整数対 (l,r) を選び、A_l,A_{l+1},\ldots,A_r をそれぞれ -1 倍する。

ペンギンくんの目標が達成可能かを判定し、可能なら必要な操作回数の最小値を求めてください。

制約

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

入力例 1

4
1 3 0 2

出力例 1

1

例えば (l,r)=(2,3) として一度だけ操作を行うとよいです。

入力例 2

4
-2 1 -4 8

出力例 2

0

ペンギンくんの目標は既に達成されています。

入力例 3

4
1 1 1 1

出力例 3

-1

ペンギンくんは目標を達成することができません。

入力例 4

10
-7 4 -8 6 10 3 4 -9 4 7

出力例 4

1

原案: penguinman

問題文

机の上にリバーシの駒が N 個あります。現在、左から i 番目の駒は、 i が奇数のときは黒の面を、偶数のときは白の面を上に向けています。また、左から i 番目の駒には、黒の面に数 B_i が、白の面に数 W_i が書かれています。

質問が Q 個与えられるので、全てに答えてください。 i 番目の質問は次のようなものです。

• 左から L_i 番目から R_i 番目までの駒以外を全て机から取り除く。その後、次の操作を 0 回以上の任意の回数繰り返す。このとき、机の上に置かれている駒が向けている面に書かれた数の総和は最大でいくつになるか。
  • 現在机の上に置かれている駒の数を r とする。 1 \leq i \leq j \leq r かつ、左から i 番目の駒と左から j 番目の駒が向けている面の色が同じであるような整数 i と j を選ぶ。左から i 番目から j 番目までの駒全てについて、その駒の向けている面の色が左から i 番目と違うなら、その駒をひっくり返す。

なお、全ての質問は独立であり、 i 番目の質問で駒を取り除いたり駒をひっくり返したりしても、 i+1 番目以降の質問には影響を与えません。

制約

• 1 \leq N \leq 10^5
• 1 \leq B_i \leq 10^9
• 1 \leq W_i \leq 10^9
• 1 \leq Q \leq 10^5
• 1 \leq L_i \leq R_i \leq N
• 入力は全て整数

入力例 1

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

出力例 1

18
10
5

1 番目の質問では、 i = 1, j = 3 として 1 度だけ操作をするのが最適です。机の上に残っている駒が向けている面に書かれた数は、順に 4, 6, 8 となります。

2 番目の質問では、一度も操作をしないのが最適です。

3 番目の質問では、そもそも操作をすることができません。

入力例 2

4
17 59
59 91
78 71
24 19
3
1 3
2 4
2 3

出力例 2

186
188
169

原案: Forested

問題文

パ研王国は、1 から N までの番号が振られた N 個の都市と、それらの間を結ぶ N-1 本の道路からなります。i 本目の道路は都市 u_i と v_i を双方向に結び、また 0 以上 1 以下の整数からなる重み w_i が割り当てられています。

さて、これからペンギンくんがパ研王国を旅します。ペンギンくんの旅は M+1 個の整数 x_0,x_1,\ldots,x_M によって表され、これはペンギンくんが都市 x_0 から始めて都市 x_1,x_2,\ldots,x_M をこの順で訪れることを表します（途中で他の都市を経由してもよい）。

ペンギンくんは旅の最中、以下の行動を好きなだけ繰り返すことができます。

• 今いる都市と直接道路で結ばれている都市を 1 つ選び、道路を通ってその都市に移動する。コストに通った道路の重みが加算され、その後通った道路の重み（x とする）が 1-x に置き換わる。

ペンギンくんは旅全体を通じての合計コストを最小化したいです。

ところで、ペンギンくんはとても気まぐれです。そのため、以下のクエリを Q 個、与えられる順に処理してください。

• タイプ1: 整数 a,b が与えられる。x_a を b に変更する。
• タイプ2: 整数 r が与えられる。ペンギンくんが都市 x_0 から始めて x_1,x_2,\ldots,x_r をこの順に訪れるときの、合計コストの最小値を求める。なお、タイプ2のクエリは独立しているため、移動の最中における辺の重みの変更は次以降のクエリでは考慮しないものとする。

制約

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq u_i,v_i \leq N\ (1 \leq i \leq N-1)
• 0 \leq w_i \leq 1\ (1 \leq i \leq N-1)
• 1 \leq x_i \leq N\ (0 \leq i \leq M)
• タイプ1のクエリにおいて、0 \leq a \leq M,1 \leq b \leq N が成り立つ
• タイプ2のクエリにおいて、1 \leq r \leq M が成り立つ
• 各クエリの前後において、x_i \neq x_{i+1}\ (0 \leq i \leq M-1) が成り立つ
• Q 個目のクエリはタイプ2のクエリである
• 与えられるグラフは木
• 入力は全て整数

入力例 1

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

出力例 1

1
2

1 個目のクエリでは、ペンギンくんは頂点 1 \rightarrow 頂点 3 \rightarrow 頂点 1 \rightarrow 頂点 2 の順に移動するべきです。移動にかかるコストはそれぞれ 1, 0, 0 となるため、答えは 1 です。

3 個目のクエリでは、ペンギンくんは頂点 1 \rightarrow 頂点 3 \rightarrow 頂点 1 \rightarrow 頂点 3 の順に移動するべきです。移動にかかるコストはそれぞれ 1, 0, 1, 0 となるため、答えは 2 です。

入力例 2

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

出力例 2

4
9
8
1

原案: penguinman

問題文

N 頂点の無向グラフがあります。このグラフの辺の情報は長さ N の数列 A を用いて、以下のように表されます。

• 任意の整数対 (i,j)\ (1 \leq i \lt j \leq N) について、
  • A_i と A_j が互いに素なら、頂点 i と頂点 j の間に辺は存在しない。
  • A_i と A_j が 1 より大きい公約数を持つなら、その中の最小値を x として頂点 i と頂点 j の間に長さ x の辺が存在する。

以下のクエリが Q 個与えられるので、順に処理してください。

• 頂点の組 (S,T) が与えられる。S と T が連結かを判定し、連結なら S から T へ向かう最短経路の長さを出力せよ。

制約

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 2 \times 10^3
• 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
• 各クエリにおいて、1 \leq S,T \leq N かつ S \neq T が満たされる
• 入力は全て整数

部分点

• Q=1 を満たすデータセットに正解した場合、500 点が与えられる。

注意

部分点のみを狙ったコードを提出する際には、Q が 1 より大きいならすぐ終了するといった処理を書き加えることを推奨します。

入力例 1

3 3
10 6 21
1 2
2 3
1 3

出力例 1

2
3
5

与えられる N=3 頂点のグラフには、以下の 2 本の辺が張られています。

• 頂点 1 と頂点 2 を結ぶ、長さ 2 の辺
• 頂点 2 と頂点 3 を結ぶ、長さ 3 の辺

よって各クエリに対する答えは以下の通りとなります。

• 1 個目のクエリにおいて問われている、頂点 1 と頂点 2 の最短距離は頂点 1 と頂点 2 を直接結ぶ辺の長さに等しく、その値は 2 である。
• 2 個目のクエリにおいて問われている、頂点 2 と頂点 3 の最短距離は頂点 2 と頂点 3 を直接結ぶ辺の長さに等しく、その値は 3 である。
• 3 個目のクエリにおいて問われている、頂点 1 と頂点 3 の最短距離は頂点 1,2 を結ぶ辺の長さと頂点 2,3 を結ぶ辺の長さの和に等しく、その値は 5 である。

入力例 2

2 1
1 1
1 2

出力例 2

-1

与えられるグラフにおいて頂点 1 と頂点 2 は非連結であるため、-1 を出力します。

なお、この入力は部分点の制約を満たします。

入力例 3

8 5
10 465 800 966 393 217 556 279
7 6
6 4
4 1
6 2
1 6

出力例 3

9
7
2
10
9

原案: primenumber_zz

問題文

かめ君は N 種類の色のついたボールを持っています。

色には 1, 2, \ldots , N と番号が振られており、各整数 i \ (1 \le i \le N) について色 i のついたボールは A_i 個あります。

各整数 k = 1, 2, \ldots , M に対し、以下の値を 998244353 で割ったあまりをそれぞれ出力してください。

• 互いに区別できる k 個の箱に、持っているすべてのボールを入れるときのボールの入れ方の総数（ここで、ボールが一つも入っていない箱があってもよい）

ただし、ある箱とある正整数 i が存在して、その箱に入っている色 i のボールの個数が異なるとき、またそのときに限りボールの入れ方が異なるとみなします（つまり、同じ色のボールは区別しません）。

制約

• 1 \le N \le 250000
• 1 \le M \le 100000
• 1 \le A_i < 998244353 \ (1 \le i \le N)
• 入力は全て整数

入力例 1

3 2
1 2 3

出力例 1

1
24

色 1 のボールは 1 個、色 2 のボールは 2 個、色 3 のボールは 3 個あります。

k=2 の時、一方の箱に何個のボールを入れるかを決めればもう片方に入れるボールの数が決まるため、答えは 2 \times 3 \times 4 = 24 となります。

入力例 2

2 3
1 1

出力例 2

1
4
9

入力例 3

4 5
31415 92653 58979 32384

出力例 3

1
287242452
806145507
819893815
181831825

998244353 で割った余りを出力することに注意してください。

原案: turtle0123__

問題文

Paken 王国は N 個の街 1, 2, \ldots, N と M 本の道路 1, 2, \ldots, M からなり、道路 i は街 A_i と街 B_i を双方向に結んでいます。

時は 2021 年、 Paken 王国にも新型ウイルスが蔓延したため、道路に向きを付けて片方向にしか通れないようにし、人の移動を抑えることになりました。 しかし、経済への影響は小さくしたいので、次のように定義されるGoTo度をできるだけ大きくしたいです。

GoTo度 : 街 u から街 v に 0 本以上の道路を通って移動できるような街の組 (u, v) の個数

道路の向き付けとして考えられるものは 2^M 通りありますが、その全てについてGoTo度を求め、その中の最大値を出力してください。

制約

• 1 \leq N, M \leq 10^5
• 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
• 各道路が双方向に通行可能であるとしたとき、任意の街から任意の街に 0 本以上の道路を通ることで移動できる
• 入力は全て整数

入力例 1

3 2
1 2
2 3

出力例 1

6

例えば、 1 \rightarrow 2, 2 \rightarrow 3 という向きにするのが最適です。

この時、 u から v へと 0 本以上の辺を通り移動できるような (u,v) の組は、 (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) の 6 つです。

入力例 2

3 3
1 2
1 3
2 3

出力例 2

9

例えば、 1 \rightarrow 2, 1 \leftarrow 3, 2 \rightarrow 3 という向きにするのが最適です。

この時、任意の頂点から任意の頂点に 0 本以上の辺を通り移動できるため、答えは 3 \times 3 = 9 です。

入力例 3

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

出力例 3

27

原案: shiomusubi496

ストーリー

20XX 年、パ研は技術室奥を捨て、海賊となり大海原に漕ぎ出した...

問題文

1 から N までの番号が振られた N 人の海賊が、1 から 10^{12} までの番号が振られた 10^{12} 個のお宝を山分けします。それぞれの海賊には分配されるお宝へのこだわりがあり、海賊 i は番号が L_i 以上 R_i 以下であるようなお宝のみを欲しがってその他のお宝は受け取りません。ここで海賊たちの間には「番号が大きい海賊はそれよりも番号が小さい海賊のお零れをもらうべきだ」という暗黙のことわりがあるため、すべての i,j\ (1 \leq i \lt j \leq N) について L_j \leq L_i かつ R_i \leq R_j が満たされます。

海賊たちはこの数日、様々な山分けの仕方について考えを巡らせています。そこで、以下の Q 個のクエリを順に処理してください。

• 海賊 l,l+1,\ldots,r でお宝を山分けするとき、それぞれがもらうお宝の個数の最小値は最大でいくらになるか。

制約

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq 10^{12}\ (1 \leq i \leq N)
• すべての i,j\ (1 \leq i \lt j \leq N) について、L_j \leq L_i かつ R_i \leq R_j が満たされる
• 各クエリにおいて、1 \leq l \leq r \leq N が満たされる
• 入力は全て整数

Extra ケース

下記の制約を満たすデータセット（上記の制約を満たす 800 点分のテストケースを含む）に正解した場合、追加で 1 点が与えられる。ただし、このデータセットにおいては低速な言語による AC が可能であることは保証されない。

• 2 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 5 \times 10^5

入力例 1

2
2 4
1 5
2
1 2
2 2

出力例 1

2
5

1 つ目のクエリにおいては、例えば以下のような山分けの仕方が考えられます。

• 海賊 1 にお宝 2,3 を、海賊 2 にお宝 4,5 を割り当てる。

2 つ目のクエリにおいては、海賊 2 にお宝 1,2,3,4,5 の全てを割り当てればよいです。

入力例 2

10
545730128881 685343573126
495640031759 777974687460
441446188770 793309056685
376909511228 836745593749
371724504348 838698721858
232388555737 839645478663
171431376831 859733468976
64650919635 891249391583
54537347654 900209259449
7975806821 908972571709
10
9 9
2 3
1 6
3 9
2 10
1 2
3 4
5 6
2 9
7 8

出力例 2

845671911796
175931433958
93394843502
120810273113
100110751654
139613444246
229918041261
303628461463
105708988974
413299235974

原案: penguinman