問題文

長さ N の攪乱順列の転倒数の最大値を求めてください。

攪乱順列とは、1 \le i \le N に対して P_i \neq i を満たす順列のことです。

転倒数とは、1 \le i < j \le N かつ P_i > P_j を満たす整数の組 (i,j) の個数です。

制約

• 入力は全て整数である。
• 2 \le N \le10^9

入力例 1

3

出力例 1

2

P=(2,3,1) の場合、これは攪乱順列であり、転倒数は 2 です。

P=(3,2,1) の場合、転倒数が 3 となりますが P_2 = 2 であるためこれは攪乱順列ではありません。

問題文

\lbrace 1,2,...,N \rbrace の部分集合 A のうち、以下の条件を全て満たすものの個数を 998244353 で割ったあまりを求めてください。

• |A| = K
• 1 \le i \le N を満たす整数 i 全てに対し、A の中に i の倍数が存在する。

制約

• 入力は全て整数である。
• 1 \le K \le N \le 2 \times 10^5

入力例 1

3 2

出力例 1

1

条件を満たすのは、\lbrace 2,3 \rbrace の 1 個のみです。

入力例 2

100 53

出力例 2

19600

問題文

maguro君は文化祭の展示でとあるゲームを作りました。

そのゲームでは H \times W のグリッド型のダンジョンが使われます。上から i\ (1 \leq i \leq H) 番目、左から j\ (1 \leq j \leq W) 番目のマスを (i,j) とします。

(i,j) のスタート時の状態は、A_{i,j} が . のとき道、# のとき壁、@ のときマグマです。

プレイヤーは最初 (1, 1) にいて、スタートから 1 秒ごとに上下左右に隣接する道のマスに 1 マス動きます（ただし、ダンジョンの外は壁となっており進めません）。しかし、スタートしてから K, 2K, 3K \dots 秒経ったタイミングでマグマが上下左右に隣接する道のマスに浸食します。プレイヤーがマグマのあるマスに入るか、プレイヤーがいるマスにマグマが浸食するとゲームオーバーです。

なお、プレイヤーが (H, W) に到達した瞬間にプレイヤーのいるマスにマグマが浸食してもゲームオーバーとなります。

プレイヤーが (H,W) のマスに到達し、かつその瞬間にマグマがプレイヤーのいるマスに浸食しなかった場合、ゲームクリアとなります。

maguro君はこのゲームがクリア可能かどうかを確かめようとしましたが、文化祭の準備で忙しかったので、プログラマーであるあなたに頼んできました。このゲームがクリア可能か判定してください。

制約

• 2 \leq H \leq 2000
• 2 \leq W \leq 2000
• 1 \leq K \leq 2000
• A_{i,j} は ., #, @ のいずれか
• A_{1,1} = ., A_{H,W} = .
• H,W,K は整数

入力例 1

4 4 2
..@#
#.#.
....
@##.

出力例 1

Yes

以下のように進むとゲームをクリアすることが可能です。（黒が壁、赤がマグマ）

入力例 2

4 4 2
...@
.#.#
....
@##.

出力例 2

No

どのように進んでも必ずマグマのあるマスに入ってしまいます。

入力例 3

4 4 2
.#.#
....
###.
@...

出力例 3

No

この場合、プレイヤーが (H, W) のマスにたどり着いた瞬間にマグマが (H, W) に浸食するため、ゲームオーバーとなってしまいます。

入力例 4

4 4 2
....
#...
@#.#
..#.

出力例 4

No

プレイヤーは (H, W) にたどり着くことができず、ゲームをクリアすることができません。

問題文

正整数 N が与えられます。

(0,1, \dots, N - 1) を並べ替えて得られる数列 P = (P_1, \dots, P_N) であって、以下の条件を満たすものは存在しますか？

• 1 \leq i \leq N に対し Q_i = \left(\sum_{j = 1}^i P_j\right) \bmod N とおくと、Q_1, \dots, Q_N は (0, 1,\dots, N - 1) を並べ替えて得られる。

存在するならばその一例を示し、存在しないならばそのことを報告してください。

制約

• 1 \leq N \leq 2 \times 10^5
• N は整数

入力例 1

4

出力例 1

0 1 2 3

P = (0, 1, 2, 3) のとき Q = (0, 1, 3, 2) となるため条件を満たします。他にも、例えば P = (0, 3, 2, 1) が条件を満たします。

入力例 2

3

出力例 2

-1

条件を満たす P は存在しません。

問題文

N 頂点 M 辺の単純無向グラフが与えられます。
頂点には 1, \dots, N の番号がつけられており、頂点 i \, (1 \leq i \leq N) には整数 A_i が書かれています。
また、i \, (1 \leq i \leq M) 番目の辺は頂点 B_i と頂点 C_i を結びます。

KoD 君はグラフから好きな本数（0 本でもよい）の辺を選んで取り除きます。
KoD 君が獲得するスコアを、操作後のグラフにおいて次数が偶数である頂点に書かれた整数の和として定めます。ただし、操作後に次数が偶数である頂点が存在しない場合、スコアは 0 です。

KoD 君が獲得するスコアとしてあり得る最大の値を求めてください。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• |A_i| \leq 10^9 \, (1 \leq i \leq N)
• 1 \leq B_i \lt C_i \leq N \, (1 \leq i \leq M)
• (B_i, C_i) \neq (B_j, C_j) \, (i \neq j)
• 入力は全て整数である。

入力例 1

3 2
-10 2 3
1 2
2 3

出力例 1

3

2 番目の辺を取り除くと、頂点 3 のみ次数が偶数となるので、KoD 君が獲得するスコアは 3 となります。

スコアを 4 以上にすることはできないので、答えは 3 となります。

入力例 2

4 2
1 2 3 -100
1 3
2 3

出力例 2

-94

与えられるグラフは連結とは限りません。

問題文

長さ N の順列 P_1,P_2,\dots,P_N のうち、以下を満たすものの個数を 998244353 で割ったあまりを求めてください。

• 整数 X=1 がある。X を P_X で置き換える操作を M 回繰り返した後に X=K となっている。

制約

• 入力は全て整数である。
• 1 \le N,M \le 2 \times 10^5
• 1 \le K \le N

入力例 1

3 2 1

出力例 1

4

例えば、P=(2,1,3) の場合、X は 1,2,1 となり条件を満たします。

入力例 2

2022 53 54

出力例 2

294327113

問題文

N 行 M 列のマス目があります。上から i 番目、左から j 番目のマス目を (i,j) で表します。

PCT 君は、(1,1) から、右のマスか下のマスに移動することを繰り返し (N,M) に行こうとしています。

しかし、下のマスが存在する (N-1)M マスのうちいずれかでは下のマスに移動することができません。

下に移動することのできないマスの組は 2^{(N-1)M} 通りありますが、そのうち PCT 君が (1,1) から (N,M) に移動できるものの個数を 998244353 で割ったあまりを求めてください。

制約

• 入力は全て整数である。
• 1 \le N,M \le 2 \times 10^5

入力例 1

2 2

出力例 1

3

もし、下に移動できないマスが (1,1) のみの場合は、(1,1),(1,2),(2,2) と移動すればいいです。

PCT 君が (1,1) から (2,2) に移動できないのは、(1,1),(1,2) の両方が下に移動できない 1 通りのみなので、答えは 3 通りです。

入力例 2

2022 5354

出力例 2

63679225

問題文

NPCA 王国には N 個の町と N-1 個の道があります。i 番目の道は長さが 1 で、町 u_i と町 v_i を双方向に結んでいます。また、どの町からどの町へもいくつかの道路を通ることで移動することができます。

クエリが Q 個与えられます。i 番目のクエリは以下です。

旅人の PCT 君が、好きな町を出発し、K_i 個の町 A_{i,1},A_{i,2},\ldots,A_{i,K_i} を訪れ、好きな町で旅を終えるとき、移動する距離の最小値を求めよ。ただし、訪れる順番は何でもよい。

最短距離で移動したい PCT 君のために、Q 個のクエリをすべて処理してください。

制約

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq u_i < v_i \leq N
• 与えられるグラフは木
• 2 \leq K_i
• \sum_{i=1}^{Q}K_i \leq 2\times 10^5
• 1 \leq A_{i,1} < A_{i,2} < \ldots < A_{i,K_i} \leq N
• 入力は全て整数

入力例 1

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

出力例 1

1
2

2 番目のクエリでは、例えば町 3 を出発して町 3 →町 2 →町 1 と移動すれば移動距離は 2 です。

入力例 2

2 1
1 2
2 1 2

出力例 2

1

入力例 3

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

出力例 3

5
2
2
7

問題文

NPCA 王国は 2 次元平面上の N 個の町からなり、町 i\,(1 \leq i \leq N) の座標は (x_i,y_i) です。

次が成り立つとき、またこの時に限り、町 i と町 j を双方向に結ぶ長さ c_i+c_j の道があります。

• \min(|x_i-x_j|,|y_i-y_j|) \leq K

町 1 から町 N への最短距離を求めてください。

制約

• 1 \leq N \leq 2\times 10^5
• 0 \leq K \leq 10^9
• 0 \leq x_i,y_i,c_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j)\,(i \neq j)
• 入力はすべて整数

入力例 1

3 3
1 3 10
3 10 5
7 13 5

出力例 1

25

町 1 と町 2 を結ぶ長さ 15 の道と、町 2 と町 3 を結ぶ長さ 10 の道があります。\min(|x_1-x_3|,|y_1-y_3|) = 6 > 3 なので、町 1 と町 3 を結ぶ道はありません。

入力例 2

2 1
1 1 10
10 10 10

出力例 2

-1

入力例 3

6 100
105 203 115
56 51 299
47 85 234
108 277 160
260 237 25
170 147 127

出力例 3

242

問題文

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

Q 個のクエリを処理してください。i \, (1 \leq i \leq Q) 個目のクエリでは、K_i 個の整数 p_{i, 1}, \dots, p_{i, K_i} が与えられるので、A_1, \dots, A_N のうち A_{p_{i, 1}}, \dots, A_{p_{i, K_i}} を除いた N - K_i 個の整数の最小公倍数を 998244353 で割った余りを求めてください。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq K_i \lt N \, (1 \leq i \leq Q)
• \sum_{i = 1}^Q K_i \leq 2 \times 10^5
• 1 \leq p_{i, 1} \lt \dots \lt p_{i, K_i} \leq N \, (1 \leq i \leq Q)
• 入力は全て整数である。

入力例 1

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

出力例 1

12
4
6

1 個目のクエリでは、A_2, A_3, A_4 の最小公倍数である 12 を出力します。
2 個目のクエリでは、A_2 = 4 を出力します。
3 個目のクエリでは、A_1, A_4 の最小公倍数である 6 を出力します。

入力例 2

10
1000000 1000000 999999 999998 999997 999996 999995 999994 999993 999992
1
1 1

出力例 2

143975436

問題文

以下の図のタイル L を A 枚、タイル I を B 枚使い、2 \times N の長方形を敷き詰める方法の個数を 998244353 で割った余りを求めてください。

ただし、同じタイルは区別がつかず、またタイルを回転や反転させて使ってもよいです。

回転や反転によって一致するタイルの敷き詰め方は異なるものとします。

制約

• 入力は全て整数である。
• 0 \le A \le 10^7
• 0 \le B \le 10^7
• 1 \le A+B
• 2N = 3A+2B

入力例 1

4 2 1

出力例 1

6

入力例 2

250 100 100

出力例 2

174250488

問題文

N 頂点の木が与えられます。i 番目の辺は長さが 1 で、頂点 u_i と頂点 v_i を結んでいます。

頂点 1 を出発し、全ての辺を 2 回ずつ通り、頂点 1 に戻ってくる移動方法を考えます。

i 番目の要素が i 番目に通った頂点の深さと定義される数列としてありうる辞書順最小のものを求めてください。ただし、頂点の深さとは頂点 1 との距離を指すとします。

制約

• 2 \leq N \leq 2\times 10^5
• 1 \leq u_i < v_i \leq N
• 与えられるグラフは木
• 入力はすべて整数

入力例 1

4
1 2
2 3
1 4

出力例 1

0 1 0 1 2 1 0

頂点 1 →頂点 4 →頂点 1 →頂点 2 →頂点 3 →頂点 2 →頂点 1 の順に通った場合、深さを並べた数列が辞書順最小となります。

入力例 2

2
1 2

出力例 2

0 1 0

入力例 3

6
2 5
3 5
1 4
4 5
4 6

出力例 3

0 1 2 1 2 3 2 3 2 1 0

問題文

N 枚のカードがあります。それぞれのカードには 1 から N の番号がつけられています。blackyuki 君と KoD 君はこのカードを使ってゲームをすることにしました。

blackyuki 君から初めて、全てのカードがなくなるまで交互に以下の操作を繰り返します。

• 残っているカードから 1 枚選ぶ、選んだカードの番号を i とする。
• \frac{A_i}{B_i} の確率でカード i を手に入れ、操作の初めに戻る。
• 1-\frac{A_i}{B_i} の確率で、何もせず操作を終了する。

ゲーム終了時に blackyuki 君の持っているカードの枚数が KoD 君の持っているカードの枚数以上であれば blackyuki 君の勝ち、そうでなければ KoD 君の勝ちとします。

2 人は、以下のように行動します。

• まず、自分がゲーム終了時に持っているカードの枚数の期待値を最大化するようにカードを選ぶ。
• 上記のみでは選ぶカードの候補が複数ある場合、その中で最も番号が小さいカードを選ぶ。

blackyuki 君の勝つ確率 \bmod\ 998244353 を求めてください。

注記

求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P,Q を用いて \frac{P}{Q} と表した時、R \times Q \equiv P(\bmod\ 998244353) かつ 0 \le R < 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

• 入力は全て整数である。
• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le B_i \le 2 \times 10^5

入力例 1

1
1 2

出力例 1

665496236

カード 1 を選び続けるしかありません。blackyuki 君がカード 1 を手に入れる確率は \frac{2}{3} です。

入力例 2

2
1 1
1 1

出力例 2

1

初めに、blackyuki 君がカード 1 を選んだとします。\frac{A_1}{B_1}=1 なので、カード 1 を必ず取ることができます。

そして、blackyuki 君は次にカード 2 を選ぶしかありません。\frac{A_2}{B_2}=1 なので、カード 2 も必ず取ることができます。

ゲーム終了時において、必ず blackyuki 君の持っているカードの枚数が KoD 君の持っているカードの枚数以上であるため、1 を出力します。

入力例 3

8
100660 113169
10964 152336
57329 77239
98640 167660
103515 136455
98695 99571
14421 149410
12488 21041

出力例 3

743177673

問題文

長さ N の整数列 A = (A_1, \dots, A_N) があります。はじめ、全ての要素は 0 です。

\{(a, b) \, | \, a \in \mathbb{N}, b \in \mathbb{N}, 1 \leq a \leq b \leq N \} の部分集合 S であって、以下の条件を全て満たすものの総数を 998244353 で割った余りを求めてください。

• |S| = M
• S の全ての要素 (l, r) に対して以下を行った後、全ての 1 \leq i \leq N について A_i = B_i が成り立つ。
  • l \leq i \leq r を満たす全ての i に対し、A_i を 1 - A_i で置き換える。

制約

• 1 \leq N \leq 3000
• 1 \leq M \leq \min\left(\frac{N(N + 1)}{2}, 3000\right)
• B_i \in \{0, 1\} \, (1 \leq i \leq N)
• 入力は全て整数である

入力例 1

3 2
1 1 0

出力例 1

2

S = \{(1, 1), (2, 2)\}, \{(1, 3), (3, 3)\} が条件を満たします。

入力例 2

3 1
1 0 1

出力例 2

0

条件を満たす S は存在しません。

入力例 3

10 20
1 0 1 1 0 1 1 1 1 1

出力例 3

71696207

問題文

N 個の机が横一列に並んでいます。机 i\,(1 \leq i \leq N) は初期状態で左から i 番目にあり、重さは A_i です。PCT 君は以下の操作を任意回行うことができます。

• 隣り合っている 2 つの机を選ぶ。これらの重さの和が K 以下のとき、これらの場所を入れ替える。

Q 個の独立なクエリが与えられます。i 番目のクエリでは、PCT 君が机 s_i を左から t_i 番目に移動させることができるか判定してください。

制約

• 1 \leq N,Q \leq 2\times 10^5
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 \leq s_i,t_i \leq N
• 入力はすべて整数

入力例 1

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

出力例 1

Yes
No
No

1 番目のクエリでは、机 1 と机 2 を入れ替えた後、机 1 と机 3 を入れ替えると、机 1 を左から 3 番目に移動させることができるので、Yes を出力します。

入力例 2

4 1 1
100 100 100 100
1 1

出力例 2

Yes

操作を行わなくても構いません。

入力例 3

8 3 10
4 1 1 3 6 4 3 6
5 7
3 3
1 1

出力例 3

Yes
Yes
Yes

問題文

長さ N かつ全ての要素が 1 以上 M 以下である整数列 A に対する \max_{1 \le i < j \le N} (A_j - A_i) の総和を 998244353 で割った余りを求めてください。

制約

• 入力は全て整数である。
• 2 \le N,M \le 10^5

部分点

この問題には、部分点が設定されている。

• 2 \le N,M \le 2000 を満たすデータセットに正解した場合は、700 点が与えられる。

入力例 1

2 2

出力例 1

0

f(A_1,A_2,\dots,A_N) = \max_{1 \le i < j \le N} (A_j - A_i) とします。

f(1,1)=0,f(1,2)=1,f(2,1)=-1,f(2,2)=0 より、解は 0 です。

このケースは部分点の制約を満たします。

入力例 2

3 4

出力例 2

76

このケースは部分点の制約を満たします。

入力例 3

100 20000

出力例 3

388129947

このケースは部分点の制約を満たしません。