問題文

UT 大学にはテント列というサークル紹介イベントがあります。長さ L の道があり、 umg くんは位置 0 から位置 L まで一方通行で歩きます。 umg くんには気力というパラメータがあり、その初期値を T とします。ここで、T は整数値とします。 umg くんは、距離 1 歩くごとに、気力が T 未満である場合は 気力が 1 回復します。気力が T である場合は回復しません。

道上には N 個のテントがあり、i 番目のテントは位置 X_i にあります。 umg くんは i 番目のテントに着くとサークル勧誘にあい、気力が A_i 減少します。もしここで気力が 0 未満になると、 umg くんはその場で倒れてしまいます。

umg くんが途中で倒れずに位置 L までたどり着くのに必要な、気力の初期値 T の最小値を求めてください。

制約

• 入力は全て整数である。
• 1 \leq N \leq 2\times 10^5
• N \lt L \leq 10^9
• 0\lt X_1 \lt X_2 \lt \cdots \lt X_N \lt L
• 1 \leq A_i \leq 10^9 \ (1\leq i \leq N)

入力例1

2 7
1 5
4 4

出力例1

6

気力の初期値 T=6 でスタートした場合は以下のような気力の変動になります。

• 1 番目のテントにたどり着いて気力が 5 減少し、気力が 1 になる。
• 2 番目のテントにたどり着くまでに気力が 3 回復し、気力が 4 になる。
• 2 番目のテントにたどり着いて気力が 4 減少し、気力が 0 になる。
• 位置 7 にたどり着くまでに気力が 3 回復し、気力 3 の状態でテント列を終える。

気力の初期値 T=5 でスタートすると、2 番目のテントで気力が 0 未満になってしまうので、答えは 6 となります。

入力例2

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

出力例2

42

問題文

「ジャンケン文字列」とは、R , S , P の 3 種類の文字のみからなる文字列のことです。
「ジャンケンマシーン」とは、ジャンケン文字列を入力として受け取って、長さの 1 小さい別のジャンケン文字列を出力する装置です。装置の挙動は以下のように定義されます。

• 入力文字列を S 、出力文字列を T とする。S の i 文字目を S_i、T の i 文字目を T_i と表すことにすると、T_i = f(S_i, S_{i+1}) (1 \le i \le |S|-1)となる文字列 T が出力される。ここで関数 f の出力は以下の表に対応する。（直感的には、2 人でジャンケンをした際に、負けない方の手。）

整数 k と、ジャンケン文字列 S が与えられます。長さ k + |S| のジャンケン文字列は 3^{k+|S|} 個存在しますが、これらのうち、ジャンケンマシーンへの入力を k 回繰り返すことで S を得ることができるようなものの個数を 998244353 で割った余りを求めてください。

制約

• 1 \leq |S| \leq 3000
• 1 \leq k \leq 3000
• S は R, S, P からなる

入力例 1

SSRP
1

出力例 1

3

SSSRP , SPSRP , PSSRP の 3 通りです。

入力例 2

SSPPP
3

出力例 2

88

入力例 3

RRRPPP
20

出力例 3

88454144

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

問題文

長さ N の整数列 A_1, \ldots, A_N と 1 以上 N 以下の正の整数 D が与えられます。以下の操作を繰り返すことを考えます。

• 1 \leq L \leq R \leq N かつ R-L+1=D であるような整数 L , R および整数 X を選び、A_L, A_{L+1}, \ldots ,A_R を一斉に、(X-A_L), (X-A_{L+1}), \ldots, (X-A_R) に書きかえる。

A_1, A_2, \ldots, A_N を有限回の操作で B_1, B_2, \ldots, B_N に一致させられるかを判定し、可能な場合はその操作手順の中で以下の条件をすべて満たすものを 1 つ構成してください。

• 操作回数が 3\times 10^5 回以下。( 0 回でも良い。)
• 各操作における X の絶対値が 10^{13} 以下。

制約

• 入力は全て整数である。
• 1 \leq D \leq N \leq 3\times 10^5
• \lvert A_i \rvert \leq 10^6
• \lvert B_i \rvert \leq 10^6

部分点

• 1 \leq N \leq 3\times 10^4 を満たすデータセットに正解した場合は 50 点が与えられる。

入力例1

4 2
1 2 3 4
4 4 3 3

出力例1

Yes
3
1 2 5
3 4 7
2 3 7

• 初期状態から(L,R,X)=(1,2,5)として操作を行うと [1,2,3,4]\to [4,3,3,4] となります。
• 次に(L,R,X)=(3,4,7)として操作を行うと [4,3,3,4]\to [4,3,4,3] となります。
• 最後に(L,R,X)=(2,3,7)として操作を行うと[4,3,4,3]\to [4,4,3,3] となり、 B と一致しています。

入力例2

2 2
1 2
1 3

出力例2

No

どのように操作しても一致させることができません。

問題文

N 人組アイドルグループのプロデューサーである Motsu-P は、その中の K 人でグループ内ユニットを編成することにしました。強運の持ち主をユニットメンバーに選ぶべく、 K 人のユニットメンバーは、ライブ直前に一様ランダムに選出することにしました。

アイドル i\ (1\leq i\leq N) は、 M_i 個の衣装 1,\ 2,\ldots,M_i を所持しています。新ユニットお披露目ライブには、どの衣装を着てきても良いと彼女たちには伝えたため、彼女たちは各々が持っている衣装の中から一様ランダムに 1 つ選びます。しかし今になって、ユニット衣装は揃っていた方が良いと気付きました。ところがすでにライブ当日であり、今から衣装の変更をすることは間に合いません。Motsu-P の精神安定のために、ユニット衣装が偶然揃っている確率を計算してください。

ただし、ユニット全員の衣装のナンバーが同一であるとき、またそのときに限って、ユニット衣装が揃っているとします。また求める確率は有理数であることが証明できるので、注記で述べるように\bmod 998244353 で出力してください。

制約

• 入力は全て整数である。
• 1 \leq K \leq N \leq 10^5
• 1 \leq M_i \leq 10^8\ (1\leq i\leq N)

部分点

• 1 \leq N \leq 2000 を満たすデータセットに正解した場合は 50 点が与えられる。

入力例 1

3 2
1 2 3

出力例 1

55458020

選ばれたアイドルの組を (x,y) のように表すと、ユニット衣装が揃っている確率は、 (1,2) のとき \frac12, (1,3) のとき \frac13 , (2,3) のとき \frac13 であるから、全体として \frac13\left(\frac12+\frac13+\frac13\right)=\frac7{18} となります。\bmod 998244353 で答えることに注意してください。

入力例 2

10 5
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751

出力例 2

819006280

問題文

Enjapma くんは、(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) を持っています。

Enjapma くんは、以下の操作をちょうど 1 回だけ行います。

• 整数 k (\geq 0) と、1 \leq l_1 \lt r_1 \lt l_2 \lt r_2 \lt \cdots \lt l_k \lt r_k \leq N を満たす整数列 (l_1, r_1, l_2, r_2, \ldots , l_k, r_k) を選んだ後、各 i (1 \leq i \leq k) に対して、P_{l_i}, P_{l_{i}+1}, \ldots, P_{r_i} を昇順に並び替える。

操作後の P としてありうる順列の個数を、998244353 で割った余りを求めてください。

制約

• 入力は全て整数である。
• 1 \leq N \leq 2\times 10^5
• 1 \leq P_i \leq N
• P_1, P_2, \ldots, P_N は全て異なる。

部分点

• 1 \leq N \leq 3000 を満たすデータセットに正解した場合は 50 点が与えられる。

入力例1

4
3 2 4 1

出力例1

6

• k = 0 とすると、P = (3, 2, 4, 1) になります。
• k = 1 として、(l_1, r_1) = (1, 2) を選択すると、P = (2, 3, 4, 1) になります。
• k = 1 として、(l_1, r_1) = (1, 4) を選択すると、P = (1, 2, 3, 4) になります。
• k = 1 として、(l_1, r_1) = (2, 4) を選択すると、P = (3, 1, 2, 4) になります。
• k = 1 として、(l_1, r_1) = (3, 4) を選択すると、P = (3, 2, 1, 4) になります。
• k = 2 として、(l_1, r_1,l_2, r_2) = (1, 2, 3, 4) を選択すると、P = (2, 3, 1, 4) になります。

他にも操作の方法はありますが、以上の 6 通りのいずれかと重複する結果になります。

入力例2

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

出力例2

300

問題文

あなたは、魔物の群れに遭遇しました。群れは N 種類の魔物により構成されていて、 i 種類目の魔物が A_i 匹います。

あなたは、以下の 2 種類のスキルを使い分けることによって、全ての魔物を倒すことにしました。

• スキル 1 : 魔力を X 消費する。魔物を K 匹まで選び、倒す。ただし、選ぶ魔物は全て 同じ 種類である必要がある。
  
• スキル 2 : 魔力を Y 消費する。魔物を K 匹まで選び、倒す。ただし、選ぶ魔物は全て 違う 種類である必要がある。

全ての魔物を倒すために消費する必要がある魔力の最小値を求めてください。

制約

• 入力は全て整数である。
• 1 \leq K \leq N \leq 10^5
• 1 \leq X, Y \leq 10^5
• 1 \leq A_i \leq 10^5

入力例 1

5 2
10 15
1 1 1 1 2

出力例 1

40

種類 1 から 種類 4 までの魔物が 1 匹ずつと、種類 5 の魔物が 2 匹います。
次のようにスキルを使うことで、40 の消費魔力で魔物を倒すことができます。

• 種類 1 の魔物と 種類 2 の魔物にスキル 2 を使う。魔力を 15 消費する。
• 種類 3 の魔物と 種類 4 の魔物にスキル 2 を使う。魔力を 15 消費する。
• 種類 5 の魔物 2 匹にスキル 1 を使う。魔力を 10 消費する。

これよりも少ない消費魔力で全ての魔物を倒すことはできないため、 40 が答えとなります。

入力例 2

5 2
15 10
1 1 1 1 2

出力例 2

30

この場合は、次のようにスキルを使うことで、30 の消費魔力で魔物を倒すことができます。

• 種類 1 の魔物と 種類 2 の魔物にスキル 2 を使う。魔力を 10 消費する。
• 種類 3 の魔物と 種類 5 の魔物にスキル 2 を使う。魔力を 10 消費する。
• 種類 4 の魔物と 種類 5 の魔物にスキル 2 を使う。魔力を 10 消費する。

これよりも少ない消費魔力で全ての魔物を倒すことはできないため、 30 が答えとなります。

入力例 3

5 2
10 25
1 1 1 1 2

出力例 3

50

この場合は、次のようにスキルを使うことで、50 の消費魔力で魔物を倒すことができます。

• 種類 1 の魔物にスキル 1 を使う。魔力を 10 消費する。
• 種類 2 の魔物にスキル 1 を使う。魔力を 10 消費する。
• 種類 3 の魔物にスキル 1 を使う。魔力を 10 消費する。
• 種類 4 の魔物にスキル 1 を使う。魔力を 10 消費する。
• 種類 5 の魔物 2 匹にスキル 1 を使う。魔力を 10 消費する。

これよりも少ない消費魔力で全ての魔物を倒すことはできないため、 50 が答えとなります。

問題文

整数 N と N \times N 行列 A が与えられます。 以下の条件を満たす整数 M と M 個の N\times N 行列 B_1 , \ldots , B_M を出力してください。

• 1 \leq M \leq 1000
• 任意の 1\leq i \leq M について、B_i の全ての成分は絶対値が 40 以下の整数
• 任意の 1 \leq i \leq M について、 \det(B_i) = \det(A)
• \sum_{i=1}^{M} B_i = \text{diag}(MA_{11} , MA_{22} , \ldots , MA_{NN})

入力の条件下で、上記の制約を満たす出力が可能であることが証明できます。

制約

• 入力は全て整数である。
• 2\leq N \leq 8
• |A_{ij}| \leq 40

入力例1

3
1 0 0
0 1 0
0 0 1

出力例1

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

出力された行列は、 \begin{pmatrix} -2&-1&2 \\ 0&1&1 \\ 1&0&-2 \end{pmatrix} と \begin{pmatrix} 0&0&-1 \\ -1&2&-2 \\ 0&1&1 \end{pmatrix} と \begin{pmatrix} 5&1&-1 \\ 1&0&1 \\ -1&-1&4 \end{pmatrix} の 3 つであり、

問題文

umg くんは縦 H 行、横 W 列のグリッドを持っています。各マスは白色または黒色です。上から i 行目、左から j 列目のマスの色は S_{ij} で表され、 . のとき白、 # のとき黒です。 umg くんは、以下の 2 種類の操作を好きな順序で好きな回数行うことでポイントを得ます。

• i 行目のマスがすべて同じ色であるような i を選び、 i 行目を削除して 1 ポイントを得る。その後、 i-1 行目と i+1 行目は(存在すれば)連結される。
• j 列目のマスがすべて同じ色であるような j を選び、j 列目を削除して 1 ポイントを得る。その後、 j-1 列目と j+1 列目は(存在すれば)連結される。

グリッドのマスが 1 つも存在しない場合、操作を行うことができません。 umg くんは最大で何ポイントを得ることができるでしょうか？

制約

• 1 \leq H,W \leq 2000
• S_{ij} は . または #

入力例1

3 3
.##
...
##.

出力例1

2

次のように操作を行い 2 ポイントを得るのが最適となります。

2 行目を削除して 1 ポイントを得る。その後、グリッドは以下のようになる。

.##
##.

2 列目を削除して 1 ポイントを得る。その後、グリッドは以下のようになる。

.#
#.

もう操作を行うことはできない。

入力例2

7 56
........................................................
.#...#..#####..#####...####..#####..#####..#####..#####.
.#...#....#....#...#..#..........#..#...#......#..#...#.
.#...#....#....####...#......#####..#...#..#####..#...#.
.#...#....#....#......#......#......#...#..#......#...#.
..###.....#....#.......####..#####..#####..#####..#####.
........................................................

出力例2

24

問題文

UTPC 王国には N 個の街 1, \ldots, N と M 本の街道があり、i 番目の街道は街 A_i と街 B_i を結んでいます。 街を頂点、街道を辺としたグラフは無向連結グラフで、多重辺は含まれる可能性がありますが自己ループはありません。

街道には危険なモンスターが出現します。i 番目の街道の危険度とは、出現するモンスターの強さに合わせて定められた整数 C_i です。ただし、C_1, \ldots, C_M は相異なります。

旅とは、ある街から出発していくつかの街道に沿って街に向かう時の街道の列とします。旅 J = (J_1, J_2, \ldots, J_L) の危険度は \sum_{i = 1}^{L} (10^6)^{C_{J_i}} で定義されます。 また、街 i と街 j の仲の悪さを、2 つの街を繋ぐ旅の危険度の最小値で定めます。そのような旅が存在しないとき、仲の悪さは 10^{10^{10}} とします。

UTPC 王国はとても不運な王国で、i 年目には、T_i 番目の街道が災害で通行不可能になります。 街道が通行不可能になったことで仲の悪さが増加した街の組はいがみあってしまい、とても危険な状態になってしまいます。 このような街の組を直接結ぶ街道があれば、それらを同時に封鎖することで通行不可能にし、国の平穏を保つことにしました。また、この措置の影響でいがみあっている街の組が出来てしまった場合、同様の措置を繰り返します。 この操作は有限回で終わることが示されます。一度通行不可能になった街道が再度通行可能になることはありません。

Q 年間の災害で通行不可能になった街道の情報が与えられます。

i 年目に初めて封鎖または災害によって通行不可能になった街道の番号の和 S_i を出力してください。 ただし、T_i は暗号化されていて直接読み込むことはできません。 X_i が入力として与えられ、S_{i-1} \oplus X_i = T_i として、T_i が復元されます。(\oplus は xor を表し、S_0 は 0 であるとします。)

また、災害によって通行不可能になる街道が既に封鎖されている場合もあることに注意してください。

制約

• 入力はすべて整数である。
• 1 \le N, M, Q \le 3 \times 10^5
• 1 \le A_i, B_i \le N
• 1 \le C_i \le 10 ^ 9
• C_i は相異なる。
• 1 \le T_i = S_{i-1} \oplus X_{i} \le M
• T_i は相異なる。
• 街を頂点、街道を辺としたグラフは無向連結グラフで、多重辺は含まれる可能性があるが自己ループは含まれない。

入力例1

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

出力例1

8
2

1 年目では S_0 \oplus 1 = 1 なので 1 番目の街道が災害により通行不可能になります。 これにより、3, 4 番目の街道を封鎖しなければならなくなります。 1, 3, 4 番目の街道が通れなくなるので S_1=8 です。よって 8 を出力します。

2 年目では S_1 \oplus 10 = 2 より 2 番目の街道が災害により通行不可能になります。 新しく封鎖するべき街道はありません。よって 2 を出力します。