問題文

2N+1 行、2N+1 列のマス目があります。上から i 行目、左から j 列目のマス目のことをマス (i,j) と呼ぶことにします。

また、(2N+1) \times (2N+1) 整数行列 A が与えられます。

ここで、マス (1,N+1),(2N+1,N+1) を除く各マスには壁を設置することができ、マス (i,j) に壁を設置するコストは A_{i,j} です。

いま、マス (1,N+1) に駒が置かれています。この駒は今いるマス目と上下左右に隣接し、かつ壁が置かれていないマス目に移動するという操作を任意の回数行うことができます。

厳密には、マス (x,y) に駒が置かれている時、マス (x',y') であって次の条件を全て満たすマスに移動することができます。

• 1 \le x',y' \le 2N+1
• マス (x',y') に壁が設置されていない。
• |x-x'|+|y-y'| = 1

あなたは、壁をいくつか配置することで駒がどんな動きをしたとしてもマス (2N+1,N+1) に到達できないようにしたいです。このとき、配置した壁のコストの和として考えられる最小値を求めてください。

制約

• 1 \le N \le 300
• (1,N+1),(2N+1,N+1) でない (i,j) について、 1 \le A_{i,j} \le 10^9
• A_{1,N+1} = A_{2N+1,N+1} = -1
• 入力は全て整数

入力例 1

1
1 -1 5
2 4 6
3 -1 7

出力例 1

10

入力例 2

2
8 1 -1 5 5
7 4 9 9 3
3 2 1 1 8
4 4 3 3 4
3 5 -1 5 8

出力例 2

10

問題文

長さ N の正整数列 A が与えられます。これからこの数列に以下の M 回の処理を行います。

• i\ (1 \le i \le M) 回目の処理 : 1 \le j \le N を満たす整数 j を選ぶ。 A_j を \max(A_j,B_i) に置き換える。

処理の結果できる A として考えられるものの個数を 998244353 で割った余りを求めてください。

制約

• 1 \le N,M \le 3000
• 1 \le A_i,B_j \le N+M
• 入力は全て整数

入力例 1

6 1
1 2 3 4 5 6
5

出力例 1

5

操作後の A としてありうるのは (5,2,3,4,5,6),(1,5,3,4,5,6),(1,2,5,4,5,6),(1,2,3,5,5,6),(1,2,3,4,5,6) の 5 通りです。

入力例 2

3 3
1 1 1
1 1 1

出力例 2

1

入力例 3

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

出力例 3

203

問題文

この問題においては、「1 番目の文字」で文字 a を、「2 番目の文字」で文字 b を、...、「26 番目の文字」で文字 z を指すものとします。

英小文字からなる文字列 S が与えられます。

あなたは 1\leq L\leq R\leq |S| となる整数 L, R および (1,2,\ldots,26) の順列 (p_1,p_2,\ldots,p_{26}) を選びます。その後、以下の手順で新たな文字列 T を作ります。

1. S' を S の L 文字目から R 文字目を取り出してできる文字列とする。
2. 1 以上 26 以下の全ての整数 i について、S' に含まれる「i 番目の文字」を「p_i 番目の文字」で置き換える。この操作は全ての i に対して同時に行う。この結果できる文字列を T とする。

T として考えられる文字列のうち辞書順で最大のものを求めてください。

制約

• 1\leq |S|\leq 10^5
• S は英小文字のみからなる

入力例 1

abcba

出力例 1

zyzx

L=2,R=5,(p_1,p_2,\ldots,p_{26})=(24,26,25,1,2,3,\ldots,23) とすると、T は zyzx になります。T としてありえるものの中でこれが辞書順で最大です。

入力例 2

nolemonnomelon

出力例 2

zzyxwvyz

入力例 3

hhhhhqqqhhhhhjjhhhhhpppp

出力例 3

zzzzzyyzzzzzxxxx

問題文

ここに N 個の箱があり、箱 i には A_i 個のボールが入っています。あなたは、以下の操作を 0 回以上 2 \times 10^6 回以下行うことができます。

• 整数対 (X,Y)(X \neq Y) であって、「箱 X に入っているボールの個数」が「箱 Y に入っているボールの個数」以下であるものを選ぶ。

  そして、箱 X に入っているボールの数だけ箱 Y から箱 X にボールを移す。

一つの箱にすべてのボールが入っている状態にできるか判定し、可能ならば操作列を一つ構築してください。

制約

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

入力例 1

3
1 3 4

出力例 1

Yes
3
1 2
2 1
3 2

以下のように操作が行われます。

1. 箱 2 から箱 1 にボールを 1 つ移す。
2. 箱 1 から箱 2 にボールを 2 つ移す。
3. 箱 2 から箱 3 にボールを 4 つ移す。

最終的に箱 3 にボールが 8 つ入っている状態になります。

なお、たとえば次のような出力も正解とみなされます。

Yes
3
1 2
1 2
1 3

入力例 2

4
7 2 3 1

出力例 2

No

2\times 10^6 回以内の操作では一つの箱にすべてのボールが入っている状態にできないことが証明できます。

入力例 3

5
2 6 2 1 5

出力例 3

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

問題文

1 以上 2 \times 10^6 以下の整数からなる長さ 10^5 の数列の組 (A,B) であって、以下の条件を満たすものを一つ構築してください。

• 1 以上 2 \times 10^6 以下のすべての整数 k について、 A_i\times B_j=k を満たす整数対 (i,j) が存在する。

問題文

0 以上 2^M 未満の整数からなる長さ N の数列 A=(A_0,A_1,\ldots,A_{N-1}) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• すべての整数 i\ (0 \le i \le N-1) について、 A_i \oplus A_{(i+1) \bmod N} \neq T_i かつ A_i \oplus A_{(i+1) \bmod N} \neq U_i が成り立つ

ただし \oplus はビット単位 \mathrm{XOR} 演算を表します。

制約

• 2 \le N \le 2\times 10^5
• 1 \le M \le 30
• 0 \le T_i < U_i < 2^M
• 入力は全て整数

入力例 1

3 2
0 1
1 2
2 3

出力例 1

8

A としてありうるのは (0,2,1),(0,3,0),(1,3,0),(1,2,1),(2,0,3),(2,1,2),(3,1,2),(3,0,3) の 8 通りです。

入力例 2

3 1
0 1
0 1
0 1

出力例 2

0

入力例 3

5 10
31 415
92 653
58 979
32 384
62 643

出力例 3

552613140

問題文

N\times N 整数行列 A が与えられます。以下の条件を満たす N \times N 整数行列 B が存在するか判定してください。

• すべての整数対 (i,j) について、 A_{i,j} \neq -1 ならば A_{i,j}=B_{i,j}
• B のどの 4 \times 4 の部分正方形を取り出しても、その部分正方形は 1 以上 16 以下の整数をすべて含む。

制約

• 4 \le N \le 500
• A_{i,j}=-1 または 1 \le A_{i,j} \le 16
• 入力は全て整数

入力例 1

4
1 2 -1 -1
5 -1 7 -1
9 10 -1 -1
13 14 15 -1

出力例 1

Yes

入力例 2

5
1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 -1 -1 -1

出力例 2

No

入力例 3

6
1 -1 -1 -1 -1 1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1

出力例 3

No

問題文

想定解に誤りが見つかったため、正しい解法に差し替えたうえで問題の制約を変更しました。(M \le 10^{12} から M \le 10^9)影響を受けた方、申し訳ありません。(15:29)

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

0\leq K\leq N-1 を満たす全ての K に対して、次の値を 998244353 で割った余りを求めてください。

• 1 以上 M 以下の整数のみからなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) であって、A_i \times A_{i+1} が平方数であるような i\,(1\leq i\leq N-1) がちょうど K 個存在するようなものの総数

制約

• 2\leq N\leq 2000
• 1 \le M \le 10^{9}
• 入力は全て整数

入力例 1

3 2

出力例 1

2
4
2

• K=0 のとき、数えるべき A は (1,2,1),(2,1,2) の 2 つです。
• K=1 のとき、数えるべき A は (1,1,2),(1,2,2),(2,1,1),(2,2,1) の 4 つです。
• K=2 のとき、数えるべき A は (1,1,1),(2,2,2) の 2 つです。

入力例 2

7 9

出力例 2

1236360
1801104
1168800
444960
111630
17796
2319

入力例 3

10 1000000000

出力例 3

463421383
80897715
609130572
681545366
345958046
718253740
76864047
286280738
642996694
527041309

問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。 A の要素を自由に並び替えることができるとき、以下の値としてありうる最小値を求めてください。

\displaystyle \sum_{k=1}^N(A_1\lor A_2\lor\cdots\lor A_k)

ただし \lor はビット単位 \operatorname{OR} 演算を表します。

制約

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

入力例 1

3
4 1 2

出力例 1

11

A を (1,2,4) に並べ替えると、(A_1)+(A_1\lor A_2)+(A_1\lor A_2\lor A_3)=1+3+7=11 となります。これが最小です。

入力例 2

3
2 5 6

出力例 2

15

A を (2,6,5) に並べ替えると、(A_1)+(A_1\lor A_2)+(A_1\lor A_2\lor A_3)=2+6+7=15 となります。これが最小です。

入力例 3

4
13 13 13 13

出力例 3

52

入力例 4

6
11 15 10 9 4 12

出力例 4

74

問題文

長さ N の整数列 A が与えられます。長さ N の順列 P が以下の条件を満たすとき、 \displaystyle \max_{1 \le i,j \le N} |iP_i-jP_j| としてありうる最小の値を求めてください。

• すべての i について、 A_i \neq -1 ならば A_i = P_i

制約

• 1 \leq N \leq 5000
• A_i = -1 または 1 \le A_i \le N
• i \neq j について、 A_i \neq -1 かつ A_j \neq -1 ならば A_i \neq A_j
• 入力は全て整数

入力例 1

3
-1 -1 2

出力例 1

4

P=(1,3,2) のとき、 \displaystyle \max_{1 \le i,j \le N} |iP_i-jP_j|=5 、 P=(3,1,2) のとき、 \displaystyle \max_{1 \le i,j \le N} |iP_i-jP_j|=4 ですから、答えは 4 です。

入力例 2

1
-1

出力例 2

0

入力例 3

5
2 4 5 1 3

出力例 3

13

問題文

長さ N の整数列 A = (A_0, A_1, \ldots, A_{N-1}),B=(B_1,B_2,\ldots,B_N) 、長さ M の整数列 C=(C_0,C_1,\ldots,C_{M-1}),D=(D_1,D_2,\ldots,D_M) と非負整数 K が与えられます。

ここで、長さ K+1 の数列 F=(F_0,F_1,\ldots,F_K),G=(G_0,G_1,\ldots,G_K) を以下で定義します。

• F_i = A_i\ (0 \le i < N)
• \displaystyle F_i = \sum_{k=1}^N B_kF_{i-k}\ (N \le i \le K)
• G_j = C_j\ (0 \le j < M)
• \displaystyle G_j = \sum_{k=1}^M D_kG_{j-k}\ (M \le j \le K)

\displaystyle \sum_{i=0}^K F_iG_i を 998244353 で割った余りを求めてください。

制約

• 1 \le N,M \le 50000
• 0 \le K \le 10^9
• 0 \le A_i < 998244353(0 \le i < N)
• 0 \le B_i < 998244353(1 \le i \le N)
• 0 \le C_i < 998244353(0 \le i < M)
• 0 \le D_i < 998244353(1 \le i \le M)
• B_N,D_M \neq 0
• 入力は全て整数

入力例 1

2 2 5
0 1
1 1
0 1
1 1

出力例 1

40

F=(0,1,1,2,3,5),G=(0,1,1,2,3,5) なので、 0\times 0 + 1\times 1+1\times 1+2\times 2+3\times 3+5 \times 5=40 が答えです。

入力例 2

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

出力例 2

23

入力例 3

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

出力例 3

142556085

問題文

0 以上 2^M 未満の整数からなる長さ N の数列 A すべてについて以下の値を考え、その総和を 998244353 で割った余りを求めてください。

• (A_1\times A_2) \oplus (A_2\times A_3) \oplus \ldots \oplus (A_{N-1}\times A_N) を 2^M で割った余り

ただし \oplus はビット単位 \mathrm{XOR} 演算を表します。

制約

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

入力例 1

2 1

出力例 1

1

A=(1,1) の場合のみ A_1\times A_2 = 1 で、それ以外の場合は 0 であるため、答えは 1 です。

入力例 2

2 2

出力例 2

16

入力例 3

314 159

出力例 3

856758166