問題文

N 個の立て看板があります。

i 番目の立て看板は時刻 S_i に設置されます。

また、整数 T が与えられ、時刻が T の倍数になる度に、その時点で設置されている立て看板が全て撤去されてしまいます。

あなたは、好きな実数時刻に一瞬京都大学に訪れ、立て看板を見ることができます。 全ての立て看板を 1 度以上見たいとき、最小で何回訪れる必要があるか求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9
• 2 \leq T \leq 10^9
• 入力は全て整数
• S_i は T の倍数ではない

入力例 1

3
1 2 5
3

出力例 1

2

時刻 2.1 と時刻 5.1 に京都大学を訪れる場合、時系列は以下のようになります。

• 時刻 1 に 1 つ目の看板が設置される。
• 時刻 2 に 2 つ目の看板が設置される。
• 時刻 2.1 に京都大学を訪れ、1 つ目の看板と 2 つ目の看板を見る。
• 時刻 3 に 1 つ目の看板と 2 つ目の看板が撤去される。
• 時刻 5 に 3 つ目の看板が設置される。
• 時刻 5.1 に京都大学を訪れ、3 つ目の看板を見る。
• 時刻 6 に 3 つ目の看板が撤去される。

入力例 2

5
1 1 1 1 1
2021

出力例 2

1

同じ時刻に複数の看板が立つこともあります。

入力例 3

10
623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784 450968417
128512451

出力例 3

7

問題文

N 行 N 列のグリッドがあります。 あなたはグリッドの各マスを、白色か黒色のどちらかで塗ります。

以下の条件を満たすような塗り方を 1 つ構成してください。

• 白いマスは連結である。（どの 2 つの白いマスについても、辺で隣接した白いマスのみをたどることで行き来できる。）
• すべての黒いマスは少なくとも 1 つの白いマスに辺で隣接している。
• i 行目にある黒いマスの個数を p_i とすると、数列 P = (p_1, p_2, \ldots, p_N) は 0 から N-1 までの整数を並び替えた順列になっている。
• j 列目にある黒いマスの個数を q_j とすると、数列 Q = (q_1, q_2, \ldots, q_N) は 0 から N-1 までの整数を並び替えた順列になっている。

制約

• 2 \leq N \leq 500

入力例1

3

出力例1

..#
#.#
...

この出力は問題文のすべての条件を満たします。

条件を満たさない出力としては、次のようなものがあります。

.#.
##.
...

（白いマスが連結ではない。）

##.
#..
...

（白いマスに辺で隣接していない黒いマスがある。）

##.
...
..#

（Q = (1, 1, 1) であり、これは 0 から N-1 の順列ではない。）

問題文

数直線上に N 個のガチャと N 枚のコインがあります。i 個目のガチャの座標は A_i 、j 枚目のコインの座標は B_j です。ただしこれらの座標はすべて正の整数です。あなたは今座標 0 にいて数直線上を自由に移動することができます。

• コインのある座標に行くと、そのコインを拾うことができます。
• ガチャのある座標に行くと、拾ったコインを 1 枚消費することでそのガチャを回すことができます。

あなたは N 個すべてのガチャを 1 度ずつ回したいと考えています。目的を達成するのに必要な移動距離の最小値を求めてください。

制約

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• A_i \lt A_{i+1} (1 \leq i \leq N-1)
• 1 \leq B_j \leq 10^9
• B_j \lt B_{j+1} (1 \leq j \leq N-1)
• 入力はすべて整数である。

入力例 1

4
1 6 7 12
3 5 10 11

出力例 1

21

この入力例では次のように行動することで移動距離の最小値を達成することができます。

1. 座標 3 に移動しコインを拾う
2. 座標 1 に移動しガチャを回す
3. 座標 5 に移動しコインを拾う
4. 座標 6 に移動しガチャを回す
5. 座標 10 に移動しコインを拾う
6. 座標 11 に移動しコインを拾う
7. 座標 12 に移動しガチャを回す
8. 座標 7 に移動しガチャを回す

入力例 2

2
1 2
1 1000000000

出力例 2

1999999998

ガチャとコインが同じ座標にある場合もあります。

問題文

N 個の石の山があり、それぞれの山に 1 から N までの番号が割り振られています。山 i にある石の数は a_i です。また、N 個の数 b_i が与えられます。 Alice と Bob はゲームをします。Alice が先手として以下の操作を交互に行い、操作できなくなった方が負けです。

• ある石の山 i を選びます。ある非負整数 k を選び、山 i から石を b_i^k 個取ります。取った後の石の数が負になってはいけません。

両者が最適にゲームをしたとき、どちらが勝つでしょうか。

制約

• 1 \leq N \leq 10^5
• 1 \leq a_i, b_i \leq 10^9
• 入力は全て整数である

入力例1

2
10 3
7 4

出力例1

Bob

入力例2

16
903 5
246 38
884 12
752 10
200 17
483 6
828 27
473 21
983 35
953 36
363 35
101 3
34 23
199 8
134 2
932 28

出力例2

Alice

入力例3

16
35 37
852 17
789 37
848 40
351 27
59 32
271 11
395 20
610 3
631 33
543 14
256 28
48 8
277 24
748 38
109 40

出力例3

Bob

問題文

N 頂点 M 辺の無向単純連結グラフ G があります。 G の頂点には 1 から N までの番号がついていて、辺には 1 から M までの番号がついています。 G の辺 i は頂点 u_i と頂点 v_i を結んでいます。

0 および 1 からなる長さ M の数列 C = (c_1, c_2, \ldots, c_M) が与えられます。 c_i が 0 のとき辺 i は青色で塗られていて、c_i が 1 のとき辺 i は赤色で塗られています。 ここで、c_i = 1 となる i はちょうど N-1 個あり、赤色の辺は G の全域木をなしています。

次の条件を満たす、1 から M までの整数を並び替えた順列 P = (p_1, p_2, \ldots, p_M) のうち、辞書順最小のものを求めてください。

• G の辺 i の重みを p_i とすると、G の最小全域木に使われている辺はすべて赤色である。
• このとき、G の最小全域木は一意に定まることに注意せよ。

制約

• 2 \le N \le 2 \times 10^5
• N - 1 \le M \le 2 \times 10^5
• 1 \le u_i < v_i \le N
• 1 \leq i < j \leq M に対して (u_i, v_i) \neq (u_j, v_j)
• c_i \in \{0, 1\}
• \{辺 i \mid c_i = 1\} は G の全域木をなしている。

入力例1

4 5
1 2 0
2 3 1
3 4 1
2 4 0 
1 3 1

出力例1

3 1 4 5 2

P = (3, 1, 4, 5, 2) とすると、辺 i の重みを P_i としたときの最小全域木に使われている辺はすべて赤色になります。 P = (4, 1, 2, 5, 3) としてもこの条件は満たされますが、P のうち辞書順で最も小さいものは (3, 1, 4, 5, 2) です。

問題文

現在KUPC国で使われている硬貨は、日本と同じ 500 、 100 、 50 、 10 、 5 、 1 円玉の 6 種類です。

KUPC国にある唯一のお店には N 個の商品が売られていて、 i 個目の商品の値段は A_i 円です。 またあなたは硬貨の枚数が最小となるように X 円を持っています。

あなたはこれからお店で自由に買い物ができます。 買い物においてあなたは次に定義する会計を好きな回数繰り返すことができます。

• 会計とは、いくつかの商品を選び、その合計金額以上のお金を支払って購入することを表します。
• このとき、支払ったお金と選んだ商品の合計金額の差分がおつりとして、硬貨の枚数が最小となるように返されます。
• 各商品は 1 個しかないので、買い物を通して同じ商品を複数個購入することはできません。

あなたは 1 円玉が好きなので、できるだけたくさんの 1 円玉を集めたいです。 買い物を終えたときに持っている 1 円玉の枚数の最大値を求めてください。

制約

• 1 \leq N \leq 10^5
• 1 \leq X \leq 10^{14}
• 1 \leq A_i \leq 10^9
• 入力はすべて整数である。

入力例 1

5 57
27 18 31 9 14

出力例 1

8

入力例 2

4 50
11 11 11 11

出力例 2

12

問題文

N 個の箱と N 個のボールがあり、箱とボールにはそれぞれ 1 から N までの番号が付けられています。各箱はちょうど 1 個のボールが入る大きさであり、最初箱 i にはボール P_i が入っています。また箱は開閉することができ、最初すべての箱は閉じています。

これから 2 回の移動イベントが行われます。各イベントでは次の手順でボールを移動させます。

1. いくつかの箱を選んでその箱を開ける。箱を開けるには箱ごとに決まったコストがかかる。
2. 開いている箱の間でボールを自由に移動させる。ただし移動が終わったときすべての箱にちょうど 1 個のボールが入っていなければならない。
3. 開いている箱をすべて閉じる。

箱 i を開くのにかかるコストは、 1 度目のイベントにおいては A_i、2 度目のイベントにおいては B_i です。2 度の移動イベントを終えたときに箱 i にボール i が入っていなければなりません。かかるコストの合計の最小値を求めてください。

制約

• 1 \leq N \leq 10^5
• 1 \leq P_i \leq N
• i \neq j のとき P_i \neq P_j
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• 入力はすべて整数である。

入力例 1

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

出力例 1

28

1 度目の移動イベントにおいては箱 2 と 4 を開きボール 1 を箱 2 に、ボール 4 を箱 4 に移動します。これにはコストが 8 だけかかります。

2 度目の移動イベントにおいては箱 1 、 2 、 3 、5 を開き、ボール 1 、 2 、 3 、5 をそれぞれ目的の箱に移動させます。これにはコストが 20 だけかかります。

合計 28 のコストで条件を達成することができ、これが必要なコストの最小値になります。

入力例 2

1
1
1000000000
1000000000

出力例 2

0

すでに条件を満たしている場合もあります。

問題文

整数 s,t,u が与えられます。

ここで、 \alpha,\beta,\gamma は以下の条件を満たす複素数です。

• \alpha+\beta+\gamma=s
• \alpha\beta+\beta\gamma+\gamma\alpha=t
• \alpha\beta\gamma=u
• \alpha,\beta,\gamma は相異なる。

このとき、正の整数 n,m が与えられるので、

\dfrac{\alpha^n(\beta^m-\gamma^m)+\beta^n(\gamma^m-\alpha^m)+\gamma^n(\alpha^m-\beta^m)}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)}

を求めてください。ただし答えは有理数であることが保証されるので、 \mod 998244353 で出力してください。

注記

有理数を出力する際には、まずその有理数を分数 \dfrac{y}{x} として表してください。ここで、 x,y は整数であり、 x は 998244353 で割り切れてはなりません（この問題の制約下で、そのような表現は必ず可能です）。そして、 xz\equiv y\pmod{ 998244353}を満たすような 0 以上 998244352 以下の唯一の整数 z を出力してください。

制約

• 1 \leq n \leq 10^{18}
• 1 \leq m \leq 10^{18}
• 0 \leq s \lt 998244353
• 0 \leq t \lt 998244353
• 0 \leq u \lt 998244353
• \alpha,\beta,\gamma は相異なる。
• 入力はすべて整数で与えられる。

入力例1

2 3
314 159 265

出力例1

159

入力例2

1000000000000000000 800000000000000000
6 11 6

出力例2

76083766

入力例3

1000000000000000000 500000000000000000
505459328 165146837 982639180

出力例3

228155372

問題文

N 個の頂点からなる根付き木があります。各頂点には 1 から N までの番号がついており、頂点 1 が根になっています。 頂点 i (2 \leq i \leq N ) の親は P_i です。

各頂点にはおもちゃの箱があります。また、各頂点には人がいます。

はじめ、頂点 i のおもちゃの箱にはおもちゃが A_i 個入っています。

また、頂点 i にいる人はおもちゃを C_i 個集めることを目標にしています。ここで、

• 頂点 i にいる人は、頂点 i を根とする部分木のうちからいくつかの頂点を選び、選んだ各頂点からそれぞれ好きな数のおもちゃをとることができる

とします。

全員の目標を同時に達成することが可能かどうかを判定してください。(ただし、同一のおもちゃを複数の人がとることはできません。)

さらに、 Q 個のクエリが与えられます。 i 個目のクエリでは、整数 t_i,v_i,x_i が与えられ、次のように値を変更します。

• t_i = 1 のとき A_{v_i} の値を x_i に変更する
• t_i = 2 のとき C_{v_i} の値を x_i に変更する

各クエリ後に、その時点で全員の目標を同時に達成することが可能かどうかを判定してください。

ただし、全員の目標を同時に達成することが可能かどうかの判定において、実際におもちゃが移動することはないことに注意してください。(つまり、各判定は独立に考えられるものとします。)

制約

• 1 \leq N \leq 10^5
• 1 \leq P_i < i (2 \leq i \leq N )
• 1 \leq A_i \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq Q \leq 10^5
• t_i \in \{ 1 , 2 \}
• 1 \leq v_i \leq N
• 1 \leq x_i \leq 10^9
• 入力は全て整数

入力例 1

3
1 1
2 1 3
3 1 2
2
1 1 1
2 3 1

出力例 1

Yes
No
Yes

はじめ、

• 頂点 1 の人は頂点 1 のおもちゃの箱からおもちゃを 2 個、 頂点 3 のおもちゃの箱からおもちゃを 1 個とる
• 頂点 2 の人は頂点 2 のおもちゃの箱からおもちゃを 1 個とる
• 頂点 3 の人は頂点 3 のおもちゃの箱からおもちゃを 2 個とる

とすることで、全員の目標を同時に達成することができます。

1つ目のクエリの処理によって、頂点 1 のおもちゃの箱に入っているおもちゃの数は 2 個から 1 個に変化します。この場合はそれぞれの人がどのようにおもちゃをとっ ても、全員の目標を同時に達成することはできません。

2つ目のクエリの処理によって、頂点 3 にいる人が欲しているおもちゃの数は 2 個から 1 個に変化します。 この場合、

• 頂点 1 の人は頂点 1 のおもちゃの箱からおもちゃを 1 個、 頂点 3 のおもちゃの箱からおもちゃを 2 個とる
• 頂点 2 の人は頂点 2 のおもちゃの箱からおもちゃを 1 個とる
• 頂点 3 の人は頂点 3 のおもちゃの箱からおもちゃを 1 個とる

とすることで、全員の目標を同時に達成することができます。

入力例 2

5
1 2 1 3
1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1
1
1 1 1

出力例 2

Yes
Yes

おもちゃの総数が非常に大きくなることがあります。

入力例 3

5
1 2 2 2
109102235 645590056 708566822 497603443 131863700
50073184 441114664 164994352 304489019 158100373
8
1 5 692234112
1 3 610338520
2 4 818442884
2 4 164762830
2 4 923652447
2 4 197720766
1 1 779302743
1 1 222486377

出力例 3

No
Yes
Yes
No
Yes
No
Yes
Yes
Yes

問題文

R と B と W からなる長さ N の文字列 S が与えられます。

N 個のボールが左右一列に並んでいて、左から i 番目のボールの色は S の i 文字目が R なら赤、B なら青、W なら白です。

あなたははじめにすべての白色のボールをそれぞれ赤色か青色で塗りなおします。その後、あなたは以下の操作を可能な限り何度でも行うことができます。

• 赤色のボール r 個と青色のボール b 個からなる長さ r + b の連続したボールの列を選択し，列全体から取り除く。その後、残ったボールの順番を保ったまま取り除いた分だけ列を詰める。

上手く色を塗りなおし、適切な操作を行うと、最大何回操作ができるか求めてください。

制約

• 1 \leq N \leq 2 \times 10 ^ 5
• 1 \leq r, b
• r + b \leq N
• N, r, b は整数
• S は R, B, W からなる長さ N の文字列

入力例1

4 1 1
BBWR

出力例1

2

まず左から 3 番目の白いボールを赤く塗ります。 1 回目の操作では左から 2 番目の青いボールと 3 番目の赤いボールからなる連続部分列を選択し，列から取り除きます。 2 回目の操作では左から 1 番目の青いボールと 2 番目の赤いボールからなる連続部分列を選択し，列から取り除きます。

以上により 2 回の操作を行うことができました。

どのような手順でも 3 回以上操作を行うことはできないので、答えは 2 となります。

入力例2

6 2 1
RBBBWB

出力例2

0

取り除く部分列は連続である必要があります。

入力例3

13 3 3
WWWWWWWWWWWWW

出力例3

2

すべてのボールを同じ色で塗る必要は無いことに注意してください。

問題文

N 個の壁があります。各壁を赤、緑、青のいずれか 1 色で塗ることを考えます。

M 個の条件が与えられます。i 番目の条件は、整数 a_i,b_i と文字 x_i,y_i が与えられ、

• 壁 a_i を 色 x_i で塗ったとき、壁 b_i を 色 y_i で塗ってはならない

ことを表しています。ただし、 x_i,y_i はそれぞれ文字 R , G , B のいずれかであり、 R のとき赤を、G のとき緑を、 B のとき青を表しています。

M 個全ての条件を満たす色の塗り方が何通りあるかを答えてください。

制約

• 1 \leq N \leq 22
• 0 \leq M \leq 9 \times \frac{N(N-1)}{2}
• 1 \leq a_i < b_i \leq N
• x_i,y_i はそれぞれ文字 R , G , B のいずれかである。
• i \neq j のとき、(a_i,x_i,b_i,y_i) \neq (a_j,x_j,b_j,y_j)
• N,M,a_i,b_i はいずれも整数

入力例 1

2 3
1 R 2 R
1 G 2 R
1 B 2 G

出力例 1

6

壁 1 を赤色で塗る場合、壁 2 は緑色または青色で塗ることができます。

壁 1 を緑色で塗る場合、壁 2 は緑色または青色で塗ることができます。

壁 1 を青色で塗る場合、壁 2 は赤色または青色で塗ることができます。 よって、合計で 6 通りの塗り方があります。

入力例 2

1 0

出力例 2

3

壁 1 をどの色で塗っても条件を満たします。

入力例 3

22 0

出力例 3

31381059609

オーバーフローに注意してください。

入力例 4

4 12
2 R 3 R
1 B 2 B
2 R 3 B
3 R 4 R
1 B 4 G
1 R 3 B
3 G 4 B
2 G 3 G
1 B 2 R
1 G 2 R
1 R 3 G
1 G 3 B

出力例 4

13

問題文

N 頂点の木があります。この木の辺の長さはすべて 1 です。この木の上で Q 回鬼ごっこをします。あなたは逃げる側であり、鬼ごっこの開始時に鬼はあなたと異なる頂点にいます。鬼はあなたのいる場所を常に知っていて、毎秒 1 の速さであなたを追いかけます。あなたは鬼の位置はわかりませんが、鬼までの距離は鬼の匂いの濃度から常にわかります。その情報をもとに、毎秒以下の 2 つの動作のうち 1 つを行います。

• 1 秒かけて隣接する頂点に進む
• 1 秒間今いる頂点で静止する

辺上か頂点上で鬼と会ったら、その回の鬼ごっこは終了です。

i 回目の鬼ごっこの開始時では、あなたは頂点 x_i にいて、鬼までの距離が d_i であることがわかっています。鬼と出会うまでの時間の最小値を最大化するように行動したときの、鬼に会うまでの時間の最小値 s_i を求めてください。

(つまり、答えはあなたは得られた情報から賭けをすることなく鬼と出会わないように動くときの鬼と出会うまでの時間の最小値です。また、辺上での移動は等速運動とし、鬼はあなたとの距離を縮める方向に動きます。)

制約

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq a_i,b_i \leq N
• 1 \leq x_i,d_i \leq N
• 頂点 x_i から距離が d_i である頂点は必ず存在する。
• i \neq j のとき (x_i, d_i) \neq (x_j, d_j)
• 与えられるグラフは必ず木である。
• 入力は全て整数である。

入力例1

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

出力例1

4
1

1 回目の鬼ごっこの開始時には、あなたは頂点 1 にいて、鬼までの距離は 4、つまり鬼は頂点 5 にいます。このときは、頂点 1 にずっととどまる行動が最適となり、s_1 = 4 となります。

2 回目の鬼ごっこの開始時には、あなたは頂点 3 にいて、鬼までの距離は 1、つまり鬼は頂点 2 か頂点 4 のどちらかにいます。この後あなたが頂点 2 の方向に動いたとすると、鬼がはじめ頂点 2 にいたときは、0.5 秒後に辺上で出会い、頂点 4 にいたときは、3 秒後に頂点 1 で出会います。よって、この行動をしたときの鬼と出会うまでの最小値は 0.5 となります。 頂点 4 の方向に動いたときも同様に鬼と出会うまでの最小値は 0.5 となります。 もし、あなたが動かず頂点 3 にとどまっていたとすると、鬼が頂点 2 にいたとき 1 秒後に、頂点 4 にいたときも 1 秒後に出会います。よって、この行動をしたときの鬼と出会うまでの最小値は 1 となります。

したがって、あなたの最適な行動は頂点 3 にとどまることで、その時の鬼に会うまでの時間の最小値 s_2 は 1 となります。

入力例2

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

出力例2

2
5

問題文

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , + ,* の 11 種類の文字からなる、長さ N の文字列を考えます。

このような文字列は全部で 11^N 通りありますが、そのうち式として成り立っているものすべての計算結果の和を、998244353 で割ったあまりで求めてください。

ただし、文字列 S が式として成り立っているとは、

• S の先頭と末尾の文字は + でも * でもない
• S から連続する 2 文字をとってきたとき、少なくとも一方は + でも * でもない

ことを指します。

また、式に含まれる整数は全て 10 進数表記であるとし、式の計算は普通の四則演算に基づいて行われるものとします。例えば、文字列 22+3*4 の計算結果は 34 にな ります。

制約

• 1 \leq N \leq 10^{18}
• 入力は全て整数である。

入力例1

1

出力例1

45

あり得る文字列は 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 の 9 通りであり、それぞれの計算結果は 1,2,3,4,5,6,7,8,9 となるので、求めるべき値はこれらの総和である 45 になります。

入力例2

3

出力例2

407430

成り立っている式の例として、239 , 2+5 , 5*8 などがあります。

入力例3

1000000000000000000

出力例3

493565653