問題文

長さがそれぞれ X, Y, Z である正整数列 A = (A_1, A_2, \ldots, A_X), B = (B_1, B_2, \ldots, B_Y), C = (C_1, C_2, \ldots, C_Z) が与えられます。ここで、X \leq Y \leq Z が成立します。

あなたは C の各要素を自由に並び替えることで、連続部分列として A, B を共に含むようにしたいです。

目標を達成できるか判定し、可能な場合は目標を達成するように並び替えた後の C としてありうる辞書順最小のものを求めてください。

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

制約

• 入力は全て整数
• 1 \leq T \leq 10^5
• 1 \leq X \leq Y \leq Z \leq 2 \times 10^5
• 1 \leq A_i \leq Z
• 1 \leq B_i \leq Z
• 1 \leq C_i \leq Z
• 1 つの入力に含まれるテストケースについて、 X + Y + Z の総和は 4 \times 10^5 以下

入力例 1

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

出力例 1

2 1 4 3
4 3 2 1
-1

• 1 番目のテストケースについて、並び替えた後の C としてありうるものは (2, 1, 4, 3) と (4, 3, 2, 1) の 2 つです。辞書順最小である (2, 1, 4, 3) を出力してください。
• 2 番目のテストケースについて、並び替えた後の C としてありうるものは (4, 3, 2, 1) の 1 つです。辞書順最小である (4, 3, 2, 1) を出力してください。
• 3 番目のテストケースについて、目標を達成することはできません。-1 を出力してください。

問題文

頂点 1, 2, \dots, N の N 頂点からなる二分木であって、以下の条件を全て満たすものの個数を 998244353 で割った余りを求めてください。

• 各 i = 1, 2, \dots, N に対し、頂点 i の行きがけ順は i である。特に、頂点 1 が根である。
• 各 i = 1, 2, \dots, M に対し、頂点 A_i の通りがけ順は B_i である。

ただし、2 つの二分木が異なるとは、ある頂点 v が存在して、以下のいずれかが成り立つことを指します。

• v の左の子の有無または頂点番号が異なる。
• v の右の子の有無または頂点番号が異なる。

pre_cnt = 1; in_cnt = 1
def dfs(v):
    preorder[v] = pre_cnt; pre_cnt += 1
    if v の左の子が存在する:
        dfs(v の左の子)
    inorder[v] = in_cnt; in_cnt += 1
    if v の右の子が存在する:
        dfs(v の右の子)

制約

• 入力は全て整数
• 1 \leq M \leq N \leq 500
• 1 \leq A_i, B_i \leq N
• A_i \neq A_j \ (i \neq j)
• B_i \neq B_j \ (i \neq j)

入力例 1

3 1
2 1

出力例 1

2

次の 2 つの二分木が条件を満たします。

• 頂点 1 が根で、頂点 2 が頂点 1 の左の子で、頂点 3 が頂点 2 の右の子である二分木。この二分木において、
  • 頂点 1 の行きがけ順は 1、通りがけ順は 3 です。
  • 頂点 2 の行きがけ順は 2、通りがけ順は 1 です。
  • 頂点 3 の行きがけ順は 3、通りがけ順は 2 です。
• 頂点 1 が根で、頂点 2 が頂点 1 の左の子で、頂点 3 が頂点 1 の右の子である二分木。 この二分木において、
  • 頂点 1 の行きがけ順は 1、通りがけ順は 2 です。
  • 頂点 2 の行きがけ順は 2、通りがけ順は 1 です。
  • 頂点 3 の行きがけ順は 3、通りがけ順は 3 です。

入力例 2

5 3
1 3
2 5
4 2

出力例 2

0

条件を満たす二分木は存在しません。

入力例 3

30 6
12 26
9 5
15 14
19 15
4 2
10 4

出力例 3

550222816

問題文

2 次元平面上の N 点が与えられます。i 番目の点の座標は (x_i,y_i) です。この N 点から、以下の条件を満たすようにいくつかの点に印を付けます。

• 印を付けた点のうちの相異なる 4 点を頂点とするような凸四角形が存在しない。

印を付ける点の個数として考えられる最大値を出力してください。

制約

• 入力は全て整数
• 4 \leq N \leq 500
• |x_i|,|y_i|\leq 10^8
• (x_i,y_i)\neq(x_j,y_j)\ (i\neq j)

入力例 1

5
0 0
-1 0
0 -1
1 0
0 1

出力例 1

4

(-1,0) を除く 4 点に印を付けることができます。全ての点に印を付けると、(0,0) を除く 4 点を頂点とする凸四角形が存在してしまうので、条件を満たしません。

入力例 2

5
0 0
1 1
2 2
2 3
3 2

出力例 2

5

入力例 3

7
-1 8
11 8
-4 -2
19 12
-8 -6
7 6
-1 2

出力例 3

6

入力例 4

4
0 0
2 0
1 -1
0 1

出力例 4

3

問題文

十進法で表された整数 N が与えられます。

N の各桁を先頭の桁が 0 にならないように並べ替えてできる整数のうち、11 の倍数であるものの個数を素数 2147483647\ (= 2^{31}-1) で割った余りを求めてください。

なお、N の各桁を並べ替えてできる整数には N 自身も含みます。

制約

• 入力は全て整数
• 1\leq N < 10^{2 \times 10^6}
• N は先頭の桁が 0 でない十進表現で与えられる

入力例 1

1001

出力例 1

2

1100 と 1001 が条件を満たします。

入力例 2

31415926535

出力例 2

144000

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられます。この A に対して、i=1,2, \dots, N-1 の順に、以下の操作を行います。

• A_i と A_{i+1} を入れ替えるか、または何もしない。

操作後の数列として考えられるものの個数を 998244353 で割った余りを出力してください。

制約

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

入力例 1

5
1 2 1 2 3

出力例 1

10

操作後の数列として考えられるのは以下の 10 通りです。

• (1,2,1,2,3)
• (1,2,1,3,2)
• (1,2,2,1,3)
• (1,2,2,3,1)
• (1,1,2,2,3)
• (1,1,2,3,2)
• (2,1,1,2,3)
• (2,1,1,3,2)
• (2,1,2,1,3)
• (2,1,2,3,1)

入力例 2

9
3 1 6 2 2 7 7 6 6

出力例 2

104

問題文

本問の設定は G 問題と共通です。

( および ) のみからなる長さ N の文字列 S が与えられます。

Q 個のクエリに答えてください。i 番目のクエリでは整数 L_i, R_i が与えられるので、以下の問題を解いてください。

S の L_i 文字目から R_i 文字目までからなる部分文字列 X を考えます。

正整数 k を選び、さらに X を k 回連結した文字列の部分文字列 Y を選ぶことを考えます。ここで、Y は正しい括弧列である必要があります。Y は空文字列であってもかまいません。

Y の長さとしてありうる最大値が存在するかどうか判定してください。

制約

• N, Q, L_i, R_i は整数
• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• S は ( および ) のみからなる長さ N の文字列
• 1 \leq L_i \leq R_i \leq N

入力例 1

4 3
()((
2 3
1 4
3 4

出力例 1

Infinite
Finite
Finite

1 番目のクエリでは、X = )( です。任意の正整数 k に対し、X を k 回連結した文字列から最初の文字と最後の文字を削除して得られる長さ 2k-2 の文字列は正しい括弧列であるため、Y の長さとしてありうる最大値は存在しません。したがって、Infinite を出力します。

2 番目のクエリでは、X = ()(( です。Y の長さとしてありうる最大値は 2 であることが証明できます。したがって、Finite を出力します。

3 番目のクエリでは、X = (( です。Y の長さとしてありうる最大値は 0 であるため、Finite を出力します。Y は空文字列でもよいことに注意してください。

問題文

本問の設定は F 問題と共通です。

( および ) のみからなる長さ N の文字列 S が与えられます。

Q 個のクエリに答えてください。i 番目のクエリでは整数 L_i, R_i が与えられるので、以下の問題を解いてください。

S の L_i 文字目から R_i 文字目までからなる部分文字列 X を考えます。

正整数 k を選び、さらに X を k 回連結した文字列の部分文字列 Y を選ぶことを考えます。ここで、Y は正しい括弧列である必要があります。Y は空文字列であってもかまいません。

Y の長さとしてありうる最大値が存在するかどうか判定し、存在する場合はその最大値を求めてください。

制約

• N, Q, L_i, R_i は整数
• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• S は ( および ) のみからなる長さ N の文字列
• 1 \leq L_i \leq R_i \leq N

入力例 1

4 3
()((
2 3
1 4
3 4

出力例 1

-1
2
0

1 番目のクエリでは、X = )( です。任意の正整数 k に対し、X を k 回連結した文字列から最初の文字と最後の文字を削除して得られる長さ 2k-2 の文字列は正しい括弧列であるため、Y の長さとしてありうる最大値は存在しません。

2 番目のクエリでは、X = ()(( です。Y の長さとしてありうる最大値は 2 であることが証明できます。

3 番目のクエリでは、X = (( です。Y の長さとしてありうる最大値は 0 です。Y は空文字列でもよいことに注意してください。

問題文

(3N+1) 行 (3N+1) 列のマス目があります。以下の条件を全て満たすように各マスを「黒」または「白」で塗ることが可能か判定し、可能であれば塗り方を 1 つ示してください。

• 異なる黒マスは辺を共有して接していない。
• 任意の黒マスを始点として、角を共有して接する黒マスに移動することを 0 回以上繰り返すことで、マス目の外周と接している黒マスのいずれかに到達することができる。
• 白マスは全体で連結である。すなわち、任意の 2 つの白マスについて、辺を共有して接する白マスに移動することを 0 回以上繰り返すことで、一方からもう一方へ到達することができる。
• ある 2 つの行には黒マスがちょうど N+1 個ずつ存在する。それ以外の行には黒マスがちょうど N 個ずつ存在する。
• ある 2 つの列には黒マスがちょうど N+1 個ずつ存在する。それ以外の列には黒マスがちょうど N 個ずつ存在する。

制約

• 入力は全て整数
• 1 \leq N \leq 500

入力例 1

1

出力例 1

No

以下の 3 つの出力例は N=1 での出力形式に合致していますが、条件を満たしていないため不正解と判定されます。

Yes
##..
#...
...#
..##

Yes
#.#.
...#
#.#.
.#..

Yes
...#
.#..
..#.
#...

1 つ目の例では、黒マスが辺を共有して接しています。

2 つ目の例では、白マスが全体で連結ではありません。

3 つ目の例では、黒マスの個数に関する条件を満たしていないほか、例えば上から 2 行目、左から 2 列目にある黒マスを始点として、角を共有して接する黒マスに移動することを繰り返しても、マス目の外周と接する黒マスに到達することはできません。

N=1 のとき、条件を満たす塗り方は存在しないことが証明できます。

問題文

整数 N,K と、長さ Q の整数列 D = (D_1, D_2, \dots, D_Q) が与えられます。

(1, 2, \dots, N) の順列 P = (P_1, P_2, \dots, P_N) に対して、頂点 1 から頂点 N までの N 個の頂点を持つ無向グラフ G(P) を以下のように定義します。

1 \leq i < j \leq N を満たす整数の組 (i, j) について、P_i > P_j であるとき、またそのときに限り、G(P) において頂点 i と頂点 j の間に辺が存在する。

また、各 d = 1, 2, \dots, N-1 について、以下の条件を全て満たす (1, 2, \dots, N) の順列 P 全体の集合を \mathcal{S}_d とします。

• G(P) が木である。
• G(P) の直径が d である。

q = 1, 2, \dots, Q に対し、\displaystyle \sum_{P \in \mathcal{S}_{D_q}} (\mathrm{LIS}(P))^K を 998244353 で割った余りを求めてください。ただし、\mathrm{LIS}(P) は順列 P の最長増加部分列の長さを表します。

制約

• 入力は全て整数
• 2 \leq N \leq 10^6
• 0 \leq K \leq 10^{18}
• 1\le Q\le 2\times 10^5
• 1\le D_1 < D_2 < \ldots < D_Q < N

部分点

• 追加の制約 N \le 500 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

4 0
3
1
2
3

出力例 1

0
2
2

G(P) が木であるような (1, 2, 3, 4) の順列 P は以下の 4 通りです。

• P = (2, 3, 4, 1)：G(P) の直径は 2 で、\mathrm{LIS}(P) = 3 です。
• P = (4, 1, 2, 3)：G(P) の直径は 2 で、\mathrm{LIS}(P) = 3 です。
• P = (2, 4, 1, 3)：G(P) の直径は 3 で、\mathrm{LIS}(P) = 2 です。
• P = (3, 1, 4, 2)：G(P) の直径は 3 で、\mathrm{LIS}(P) = 2 です。

以上より

• q = 1 に対する答えは 0
• q = 2 に対する答えは 3^0 + 3^0 = 2
• q = 3 に対する答えは 2^0 + 2^0 = 2

となります。

入力例 2

2 100
1
1

出力例 2

1

入力例 3

314159 26535
5
271
828
1828
45904
52353

出力例 3

765557189
351184939
258247317
305813889
68486796

問題文

1, 2, \dots, N の番号がつけられた N 種類の食べ物と水ゼリーの、合計 N+1 種類の食べ物があります。i = 1, 2, \dots, N について、食べ物 i の甘さは A_i で、辛さは B_i です。また、水ゼリーの甘さは 0 で、辛さは 0 です。

UTPC 君は、はじめに水ゼリーを食べ、続いて食べ物 1, 2, \dots, N を任意の順番で 1 回ずつ食べ、最後に水ゼリーを食べます。

UTPC 君がはじめに水ゼリーを食べ終わった時点での幸福度は 0 です。これ以降、食べ物を食べる度に、UTPC 君の幸福度は次のように変化します。

• 食べる食べ物の甘さを a、辛さを b とし、その直前に食べた食べ物の甘さを a'、辛さを b' とする。このとき、UTPC 君の幸福度は \max(a - a', b - b') だけ増加する。幸福度の増加量は負であることもある。

食べ物 1, 2, \dots, N を食べる順番を工夫したときの、UTPC 君の最終的な幸福度の最大値を求めてください。

制約

• 入力は全て整数
• 1 \leq N \leq 5 \times 10^5
• 0 \leq A_i,B_i \leq 10^9

入力例 1

4
1 4
3 1
2 3
3 4

出力例 1

6

食べ物 1,2,3,4 の順番で食べればよいです。このとき、はじめに水ゼリーを食べ終わった以降の UTPC 君の幸福度の変化は以下の通りです。

• 食べ物 1 を食べる。UTPC 君の幸福度は \max(1-0,4-0) = 4 だけ増加し、4 となる。
• 食べ物 2 を食べる。UTPC 君の幸福度は \max(3-1,1-4) = 2 だけ増加し、6 となる。
• 食べ物 3 を食べる。UTPC 君の幸福度は \max(2-3,3-1) = 2 だけ増加し、8 となる。
• 食べ物 4 を食べる。UTPC 君の幸福度は \max(3-2,4-3) = 1 だけ増加し、9 となる。
• 水ゼリーを食べる。UTPC 君の幸福度は \max(0-3,0-4) = -3 だけ増加し、6 となる。

入力例 2

3
1 2
2 1
1 2

出力例 2

3

入力例 3

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

出力例 3

18

問題文

U + T + P + C 枚のカードがあり、このうち U 枚は表面にユニコーンの絵が、T 枚は表面にトラの絵が、P 枚は表面にパンダの絵が、C 枚は表面にネコの絵が描かれています。すべてのカードははじめ裏面を向けて置かれており、どのカードも表面に何の絵が描かれているかわからないようになっています。

あなたはこれらのカードを用いてゲームをします。ゲームはいくつかのターンからなり、あなたは各ターン、次の操作 A、操作 B のいずれかを選んで行います。

• 操作 A: 裏面を向けているカードから等確率に 1 枚選び、表面を向ける。このとき、
  • 選んだカードの表面に描かれている絵がユニコーン、トラ、パンダのいずれかであれば、次のターンに移りゲームを続行する。選んだカードは表面を向けたままにする。
  • 選んだカードの表面に描かれている絵がネコであれば、ゲームを終了する。このとき、あなたの得点は 0 点となる。
• 操作 B: ゲームを終了させる。このとき、表面を向けたカードのうちユニコーンが描かれているものの枚数を u、トラが描かれているものの枚数を t として、あなたの得点は 2u+t 点となる。

得点の期待値を最大化する戦略をとったときの得点の期待値を、\text{mod } 998244353 で求めてください。

制約

• 入力は全て整数
• 1 \leq U, T, P, C \leq 10^6

入力例 1

1 1 1 1

出力例 1

166374060

ゲーム進行の一例を示します。必ずしも最適な戦略とは限りません。

1 ターン目に操作 B を行えば得点は 0 点となりゲームが終了します。ここでは操作 A を行い、選んだカードの表面にユニコーンが描かれていたとします。

この状態で 2 ターン目に操作 B を行えば得点は 2 点となりゲームが終了します。ここでは操作 A を行い、選んだカードの表面にパンダが描かれていたとします。

この状態で 3 ターン目に操作 B を行えば得点は 2 点となりゲームが終了します。ここでは操作 A を行い、選んだカードの表面にネコが描かれていたとします。ネコが描かれているカードを表向きにしたので、得点は 0 点となりゲームが終了します。

最適な戦略をとった場合、得点の期待値は \frac{7}{6} になることが示せます。

入力例 2

2 7 1 8

出力例 2

300941313

入力例 3

20 26 2 14

出力例 3

631490021

問題文

整数 N,K と長さ N の整数列 X=(X_0,X_1,\ldots,X_{N-1}) が与えられます。

以下の条件を全て満たす整数の組 (M,A,B) を良い組と呼びます。

• 1 \le M < 2^{30}
• k=0,1,\ldots,N-1 に対し \displaystyle X_k = \left\lfloor\frac{Ak+B}M \right\rfloor が成り立つ。

制約下で良い組の個数は有限となることが証明できます。この個数を C とします。

K \le C が成り立つか判定し、成り立つ場合は辞書順で K 番目に小さい良い組を求めてください。

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

制約

• 入力は全て整数
• 1\le T \le 1000
• 2\le N \le 2\times 10^5
• 1\le K\le 10^9
• 0\le X_i < 2^{30}
• 全てのテストケースにおける N の総和は 2\times 10^5 以下

部分点

• 追加の制約 K=1 を満たすデータセットに正解した場合は 2 点が与えられる。
• 追加の制約 K\le 10 を満たすデータセットに正解した場合はさらに 18 点が与えられる。

入力例 1

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

出力例 1

2 1 1
-1
11 -19 107

1 番目のテストケースについて、良い組は辞書順に (M,A,B)=(2,1,1),(3,2,1),(4,2,2),(4,2,3),(4,3,1),\ldots です。

2 番目のテストケースについて、良い組は存在しません。

3 番目のテストケースについて、良い組は辞書順に (M,A,B)=(4,-7,39),(7,-12,68),(8,-14,78),(8,-14,79),(9,-16,89),(10,-17,97),(11,-19,107),\ldots です。

問題文

Conference を解いた人は、自然にこの問題を思いついているかもしれません。

長さ N の文字列 S が与えられます。ここで、S の各文字は A, B, C, ? のいずれかであり、特に S の 1 文字目と N 文字目は A です。

ここで、各文字が A, B, C のいずれかである長さ N の文字列のスコアを、文字列の i 文字目と i+1 文字目が異なるような整数 i \ (1 \leq i \leq N-1) の個数とします。

Q 個のクエリに答えてください。i 番目のクエリの内容は以下の通りです。

非負整数 X_i, Y_i, Z_i が与えられます。ここで、X_i + Y_i + Z_i は S の ? の個数に等しいです。S の ? のうち X_i 個を A に、Y_i 個を B に、Z_i 個を C に置き換えて得られる文字列のスコアとしてありうる最大の値を出力してください。

制約

• N, Q, X_i, Y_i, Z_i は整数
• 2 \leq N \leq 3 \times 10^5
• S は A, B, C, ? からなる長さ N の文字列
• S の 1 文字目と N 文字目は A
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq X_i
• 0 \leq Y_i
• 0 \leq Z_i
• X_i + Y_i + Z_i は S に含まれる ? の個数と等しい

入力例 1

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

出力例 1

8
6
4

• 1 番目のクエリでは、ABCBABCBA と置き換えればスコアを 8 とできます。
• 2 番目のクエリでは、ABABAACAA と置き換えればスコアを 6 とできます。
• 3 番目のクエリでは、ACCBCCCCA と置き換えればスコアを 4 とできます。

入力例 2

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

出力例 2

4
8
4
10

入力例 3

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

出力例 3

24
21
23
21
19
20
19
21
19
17
19
22
19
17
22
19
23
22
20
13
15
19
20
17
21
17

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

\lbrace 1,2,\ldots,N \rbrace の部分集合 X,Y であって以下の条件を全て満たすものが存在するか判定し、存在する場合は 1 つ示してください。

• 0 < |X|=|Y|
• X,Y は異なる
• \displaystyle s_X = \sum_{x \in X} \frac1{A_x},\ s_Y = \sum_{y \in Y} \frac1{A_y} としたとき、\left|s_X-s_Y \right| \le 10^{-5} が成り立つ

制約

• 入力は全て整数
• 2\le N\le 1000
• 1\le A_i \le 10^5

入力例 1

10
31 41 59 26 53 58 97 93 23 84

出力例 1

Yes
2
1 3
4 8

\displaystyle s_X=\frac1{31}+\frac1{59}=0.04920721705\ldots,

\displaystyle s_Y=\frac1{26}+\frac1{93}=0.04921422663\ldots

より |s_X-s_Y| \le 10^{-5} が成り立ちます。

入力例 2

7
2 3 5 7 11 13 17

出力例 2

No

入力例 3

8
123 456 789 314 159 265 271 828

出力例 3

Yes
3
4 5 7
1 3 6