問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) のうち、B_i=(A_i+K)\bmod M と定義される数列 B が A の並び替えになっているようなものは存在しますか？

余談

NPCA を ROT13 で変換すると ACPN となります。

制約

• 1 \le N \le 10^9
• 1 \le K \le M \le 10^9
• 入力は全て整数

入力例 1

15
6 9

出力例 1

Yes

例えば、A=(2,0,1,3,3,6,7,4,6,7,8,0,1,4,5) の場合、B=(8,6,7,0,0,3,4,1,3,4,5,6,7,1,2) となり、条件を満たします。

入力例 2

2
5 7

出力例 2

No

問題文

長さ N の整数列 A,B が与えられます。

1 \le l \le r \le N を満たす整数の組 (l,r) に対する (\max_{l \le i \le r} A_i) \times (\min_{l \le i \le r} B_i) の最小値を求めてください。

制約

• 入力は全て整数である。
• 1 \le N \le 2 \times 10^5
• -10^9 \le A_i,B_i \le 10^9 \lparen 1 \le i \le N \rparen

入力例 1

3
3 4 8
4 2 5

出力例 1

8

(l,r)=(1,2) のとき (\max_{l \le i \le r} A_i) \times (\min_{l \le i \le r} B_i)=4 \times 2 = 8 となります。

入力例 2

3
-3 -5 8
4 2 -5

出力例 2

-40

A,B の要素は負になることもあります。

問題文

kentand君は爆弾処理をします。

H×W のマス目があり、上から i \lparen 1 \le i \le H \rparen 行目、左から j \lparen 1 \le j \le W \rparen 列目のマス \lparen i,j\rparen は G_{i,j} が # のとき壁で、. のとき道です。

マス目上の道に爆弾が N 個あり、 k \lparen 1 \le k \le N \rparen 個目の爆弾はマス \lparen C_k, D_k \rparen にあります。

kentand君は時刻 0 にマス \lparen 1,1 \rparen におり、1 単位時間ごとに、今いるマスに上下左右に隣接する道のマスに移動します。爆弾のあるマスに移動することも可能です。同じマスにとどまることはできません。

そして、k 個目の爆弾があるマスに S_k,S_k+1,\ldots,T_k のいずれかの時刻にいることでその爆弾を解除できます。解除にかかる時間は無視できます。

適切に行動したとき最大で何個の爆弾を解除できますか？

制約

• 1 \le H, W \le 100
• 1 \le N \le 16
• 1 \le C_k \le H \lparen 1 \le k \le N \rparen
• 1 \le D_k \le W \lparen 1 \le k \le N \rparen
• (C_k,D_k) は相異なる
• 1 \le S_k \le T_k \le 10^9 \lparen 1 \le k \le N \rparen
• G_{i,j} は # か . のどちらか \lparen 1 \le i \le H, 1 \le j \le W \rparen
• 爆弾のあるマス及びマス \lparen 1,1 \rparen は道
• マス (1,1) に隣り合う道のマスが 1 つ以上存在する
• H, W, N, C_k, D_k, S_k, T_k は整数

入力例 1

3 3 2
1 3 2 5
3 2 3 4
.#.
...
#.#

例えば、(1,1),(2,1),(2,2),(3,2),(2,2),(2,3),(1,3) と移動することで、時刻 3 の時に爆弾 2 を解除できます。時刻 6 の時に爆弾 1 のある場所にいますが、爆弾 1 は時刻 2 以上 5 以下の時しか解除できません。

出力例 1

1

入力例 2

1 2 1
1 2 1000000000 1000000000
..

出力例 2

0

問題文

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

KoD 君は N 頂点の単純無向グラフを持っており、頂点には 1 から N の番号が付けられています。このグラフは連結とは限りません。

あなたの目標は、KoD 君が持っているグラフに閉路が存在するかどうか判定することです。そのために、以下の質問を行うことができます。

• 頂点集合を指定し、両端がその集合に属するような辺が何本あるかを聞く。

4500 回以下の質問回数で判定してください。

制約

• 2 \leq N \leq 250
• N は整数
• KoD 君が持っているグラフには自己ループや多重辺が存在しない。

入出力

最初に、グラフの頂点数 N を標準入力から受け取ってください。

N

次に、グラフに閉路が存在するかどうか判定できるまで質問を繰り返してください。質問は、以下の形式で標準出力に出力してください。

? n a_1 \ldots a_n

これは、頂点集合として \{ a_1, \dots, a_n \} を指定することを表します。このとき、n > 0 でなければならず、a_1, \dots, a_n は相異なる 1 以上 N 以下の整数でなければなりません。

質問に対する応答は、次の形式で標準入力から与えられます。

M

• 無効な質問を行った場合（質問回数が 4500 回を超えた場合を含む）、M = -1 です。この場合、プログラムをただちに終了させてください。
• 有効な質問を行った場合、M は指定した頂点集合に両端が含まれるような辺の本数を表します。

グラフに閉路が存在するかどうか判定できたら、解答を以下の形式で標準出力に出力してください。

! S

S はあなたの解答を表す文字列であり、閉路が存在するなら Yes、存在しないなら No でなければなりません。

注意

• 出力のたびに改行し、標準出力をflushしてください。そうしない場合、ジャッジ結果が TLE となる可能性があります。
• 解答を出力した後、あなたのプログラムは直ちに終了しなければなりません。そうしない場合、ジャッジ結果が AC とならない可能性があります。
• 途中で不正な出力を行った場合は不正解となりますが、そのときのジャッジ結果は不定です。WA になるとは限りません。

入出力例

問題文

N 頂点の完全グラフがあります。頂点 i と頂点 j を結ぶ辺の長さは \min(|A_i-A_j|,|B_i-B_j|) です。

頂点 1 を出発し、頂点 2 から N をそれぞれ 1 回ずつ通り、頂点 1 に帰ってくるサイクル全てについて、サイクルの長さの総和を 998244353 で割った余りを求めてください。

制約

• 入力は全て整数である。
• 2 \le N \le 2 \times 10^5
• -10^9 \le A_i,B_i \le 10^9(1 \le i \le N)

入力例 1

3
1 2
3 5
4 2

出力例 1

6

頂点 1、頂点 2、頂点 3、頂点 1 と通った場合、サイクルの長さは 2+1+0=3 です。

頂点 1、頂点 3、頂点 2、頂点 1 と通った場合、サイクルの長さは 0+1+2=3 です。

よって答えは 6 です。

問題文

N 個の給水機と 1 つの空のコップがあります。PCT 君はこのコップにできるだけ多くの水を入れたいです。

給水機 i\,(1 \leq i \leq N) は時刻 S_i から時刻 T_i のみ使えます。また、1 秒あたりの給水量は A_i リットルで、蓄えている水の量は A_i\times B_i リットルです。つまり、合計 B_i 秒よりも長く給水することはできません。

適切に行動すると最大で何リットルの水をコップに入れることができますか？ただし、同時に 2 つ以上の給水機からコップに水を入れることはできません。

制約

• 1 \leq N \leq 500
• 1 \leq S_i < T_i \leq 10^9
• 1 \leq A_i,B_i \leq 10^9
• 入力はすべて整数

入力例 1

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

出力例 1

7

時刻 1 から時刻 2 までの 1 秒間は給水機 1 から 1 リットルの水をコップに入れます。

時刻 2 から時刻 3 までの 1 秒間は給水機 2 から 3 リットルの水をコップに入れます。

時刻 3 から時刻 4 までの 1 秒間は給水機 3 から 2 リットルの水をコップに入れます。

時刻 4 から時刻 5 までの 1 秒間は給水機 1 から 1 リットルの水をコップに入れます。

このように行動すると合計 7 リットルの水をコップに入れることができます。

入力例 2

1
1 100 100 3

出力例 2

300

入力例 3

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

出力例 3

17

問題文

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

k = 1, \dots, M について、以下の条件を全て満たす正整数列 C = (C_1, \dots, C_N) の総数を 998244353 で割った余りを求めてください。

• A_i \leq C_i \leq B_i \, (1 \leq i \leq N)
• \mathrm{gcd} (C_1, \dots, C_N) = k

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \leq B_i \leq 10^5 \, (1 \leq i \leq N)
• 入力は全て整数である。

入力例 1

3 10
1 9
4 8
7 10

出力例 1

151
20
3
3
1
0
1
1
0
0

k = 4 のとき、C = (4, 4, 8), (8, 4, 8), (4, 8, 8) が条件を満たします。

入力例 2

1 1
2 100000

出力例 2

0

問題文

N 頂点 M 辺の単純連結無向グラフが与えられます。i \, (1 \leq i \leq M) 本目の辺は頂点 A_i, B_i を結びます。

1 \leq s \lt t \leq N を満たす整数の組 (s, t) に対し、以下の値を f(s, t) とおきます。

頂点 s を出発し、頂点 t に到達した後頂点 s に戻ってくるような経路における、s 以外の頂点のうち 2 回以上通るものの個数の最小値

\displaystyle \sum_{s = 1}^{N - 1} \sum_{t = s + 1}^N f(s, t) を求めてください。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \, (1 \leq i \lt j \leq M)
• 与えられるグラフは連結
• 入力は全て整数である

入力例 1

4 4
1 2
2 3
1 3
3 4

出力例 1

2

例えば f(1, 4) = 1, f(3, 4) = 0 です。

入力例 2

2 1
1 2

出力例 2

0

問題文

長さ N の正整数列 A = (A_1, \dots, A_N) と N の正の約数 K が与えられます。(1, 2,\dots, N) を並べ替えて得られる数列 P に対し、以下のように P のスコアを定めます。

i = 1, \dots, N に対し、B_i = A_{P_i} と定める。
i = 1, \dots, \frac{N}{K} に対し、G_i = \gcd(B_{(i - 1)K + 1}, B_{(i - 1)K + 2} \dots, B_{iK}) と定める。
\mathrm{lcm}(G_1, \dots, G_{\frac{N}{K}}) が P のスコアである。

P としてあり得るものは N! 通りありますが、それら全てに対する P のスコアの総積を \bold{10^9 + 7} で割った余りを求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• K は N の正の約数
• 1 \leq A_i \leq 2 \times 10^5
• 入力は全て整数

入力例 1

4 2
1 2 3 4

出力例 1

256

例えば、P = (2, 4, 1, 3) のスコアは次のように計算できます。

B = (2, 4, 1, 3) である。
G = (\gcd(B_1, B_2), \gcd(B_3, B_4)) = (2, 1) である。
P のスコアは \mathrm{lcm}(G_1, G_2) = 2 である。

入力例 2

9 3
12 6 8 9 10 16 4 18 15

出力例 2

822906664

問題文

11 個の整数 c_0, \dots, c_{10} が与えられます。f(x) = \sum_{n = 0}^{10} c_n x^n と定めます。

以下の条件を全て満たす整数列 A, B が存在するか判定し、存在するならばその一例を示してください。

• A, B の長さは 1 以上 5000 以下
• |A_i| \leq 5000 \, (1 \leq i \leq |A|)
• |B_i| \leq 5000 \, (1 \leq i \leq |B|)
• A_i \neq A_j \, (1 \leq i \lt j \leq |A|)
• B_i \neq B_j \, (1 \leq i \lt j \leq |B|)
• A_i \neq B_j \, (1 \leq i \leq |A|, 1 \leq j \leq |B|)
• \sum_{i = 1}^{|A|} f(A_i) = \sum_{j = 1}^{|B|} f(B_j)

制約

• |c_i| \leq 10 \, (0 \leq i \leq 10)
• 入力は全て整数

入力例 1

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

出力例 1

2 0 1
1 2

f(x) = 2x^2 - x + 5 であるので f(0) + f(1) = f(2) = 11 となり条件を満たします。

問題文

NPCA 美術館では、東西方向にまっすぐに伸びる廊下に N 枚の絵が飾られています。絵 i (1\leq i\leq N) は廊下の西端から X_i メートルの位置に飾られており、その価値は V_i です。

館長の PCT 君は以下の条件を満たすように N-M 枚の絵を取り外し、M 枚の絵だけを残すことにしました。

• どの 2 つの絵についても、位置が D メートル以上離れている。

残った絵の価値の総和の最大値を求めてください。

制約

• 1 \leq M \leq N \leq 3\times 10^5
• 1 \leq D \leq 10^9
• 0 \leq X_1 < X_2 < \ldots < X_N \leq 10^9
• |V_i| \leq 10^9
• 入力はすべて整数

入力例 1

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

出力例 1

8

絵 2 と絵 3 を取り外すのが最適です。

入力例 2

4 3 2
0 1 2 3
1 1 1 1

出力例 2

impossible

入力例 3

5 2 4
0 3 5 6 9
-4 -8 3 -10 -6

出力例 3

-1

問題文

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

区間 [l,r] \,(1 \le l \le r \le N) のスコアを以下で定義します。

• |\min(A_l,A_{l+1},\ldots,A_r)-\min(B_l,B_{l+1},\ldots,B_r)|

k=0,1,\ldots,N-1 について、r-l=k を満たす [l,r] を選んだときのスコアとしてあり得る最小値を求めてください。

制約

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

入力例 1

3
1 3 4
8 5 7

出力例 1

2
2
4

k=0 のとき、l=2,r=2 とするとスコアが最小になります。

k=1 のとき、l=2,r=3 とするとスコアが最小になります。

k=2 のとき、l=1,r=3 とするとスコアが最小になります。

入力例 2

1
1
1

出力例 2

0

入力例 3

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

出力例 3

0
0
1
1
1
1

問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

• 空文字列
• ある正しい括弧列 A が存在して、(, A, ) をこの順に連結した文字列
• ある空でない正しい括弧列 A, B が存在して、A, B をこの順に連結した文字列

そして、正しい括弧列から末尾の文字を取り除くことを何回か繰り返すことで得られる文字列を美しい括弧列と定義します。

例えば、(((() や ()()、空文字列などは美しい括弧列であり、))()、()) などは美しい括弧列ではありません。

文字列 S と整数 L が与えられます。k=1,2,\ldots ,|S|-L+1 について独立に、以下の問いに答えてください。

S の隣り合う 2 文字を入れ替えることを繰り返すことで、S の k 文字目から k+L-1 文字目までを取り出した部分文字列が美しい括弧列となるようにしたい。操作回数の最小値を求めよ。

制約

• 1 \leq |S| \leq 5 \times 10^5
• S は ( と ) のみからなる文字列
• 1 \leq L \leq |S|
• L は整数

入力例 1

))((
2

出力例 1

2
1
0

k=1 のとき、S を ))(( → )()( → ())( とすると、() は美しい文字列です。操作回数は 2 回です。

入力例 2

))())
4

出力例 2

-1
-1

入力例 3

))()(()
3

出力例 3

4
2
0
1
0

問題文

N 行 M 列のマス目に整数を書き込む方法のうち、以下が成り立つものが存在するか判定し、存在する場合は 1 個構築してください。

ここで、A_{i,j} を上から i 番目、左から j 番目のマスに書かれた整数とします。

• A_{i,j} は 0 以上 X-1 以下である。
• A_{i,j} \equiv A_{i-1,j} + A_{i+1,j} + A_{i,j-1} + A_{i,j+1}\ (\bmod X)
• \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} A_{i,j} > 0

ただし、A_{0,i},A_{N+1,i},A_{i,0},A_{i,M+1} は全て 0 とします。

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

制約

• 1 \le T \le 100
• 1 \le N,M,X \le 100
• 1 個の入力ファイルに対する N の総和は 100 以下である。
• 1 個の入力ファイルに対する M の総和は 100 以下である。
• 入力は全て整数である。

入力例 1

3
2 2 3
2 2 2
52 53 2

出力例 1

2 1 
1 2 
-1
-1

1 個目のテストケースについて、これは条件を満たす書き込み方です。例えば、A_{1,1} \equiv A_{0,1} + A_{2,1} + A_{1,0} + A_{1,2} \ (\bmod X) となっています。

2,3 個目のテストケースについて、条件を満たす書き込み方は存在しません。

問題文

長さ N の順列全てに対する転倒数の M 乗の総和を 998244353 で割ったあまりを求めてください。

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

制約

• 1 \le T \le 1000
• 2 \le N \le 10^7
• 1 \le M \le 100
• 入力は全て整数である。

入力例 1

4
3 2
4 1
53 54
1234 12

出力例 1

19
72
403070452
49172397

1 個目のテストケースでは、0+1+1+4+4+9=19 より、19 が解です。

問題文

N 枚のカードがあり、1 から N の番号が付けられており、全てのカードは初め裏を向けて並べられています。

PCT 君は全てのカードが表を向くまで以下の操作を繰り返します。

• 1 以上 N 以下の整数をランダムに 1 個選ぶ。選んだ整数を x とおく。カード x から x+M-1 のうち、裏を向けているカードのみをひっくり返す。ただし、カード i \, (i > N) はカード i-N のこととする。

操作回数の期待値 \bmod\ 998244353 を求めてください。

注記

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

制約

• 入力は全て整数である。
• 1 \le M \le N \le 500000

入力例 1

3 3

出力例 1

1

1 回操作をすると全てのカードが表を向くため、操作回数の期待値は 1 です。

入力例 2

3 1

出力例 2

499122182

1 以上 3 以下の整数全てが選ばれるまで操作は終わりません。操作回数の期待値は \frac{11}{2} です。

入力例 3

20220 5253

出力例 3

134463961