NPCAPC 2024

A - Welcome to NPCAPC

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英大文字と英小文字からなる長さ N の文字列のうち、 NPCAPC と npcapc の両方を部分文字列(連続でなくてもよい)として含むものの個数を 998244353 で割ったあまりを求めてください。

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

制約

1 \leq N\leq 10^9
1 \leq T\leq 5000

部分点

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

N \leq 2\times 10^5,T \leq 10 を満たすデータセットに正解した場合 10 点が与えられる。
N \leq 10^9,T \leq 10 を満たすデータセットに正解した場合追加で 10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{Case}_1
\mathrm{Case}_2
\vdots
\mathrm{Case}_T

ここで \mathrm{Case}_i は i 番目のテストケースを意味する。それぞれのテストケースは以下の形式で与えられる。

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。

入力例 1

出力例 1

1 番目のテストケースでは、条件を満たす文字列は npcapcNPCAPC や NPCnpcAapPCc などの 924 通りがあります。

入力例 2

出力例 2

333574957
124462731
163251704

B - Some Sum of Subset

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。k=0,1,\dots,N について以下の問題を解いてください。

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

\left\vert T\right\vert=\left\vert S\right\vert-k を満たす S の部分集合 T であって \sum_{i \in T}A_{i}\ge M を満たすものが存在する。

制約

1 \le N \le 3000
1 \le M \le 3000
1 \le A_i \le 3000

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \dots A_N

出力

N+1 行に渡って出力せよ。 i(1\le i\le N+1) 行目には、 k=i-1 の場合の答えを出力すること。

入力例 1

4 7
3 1 5 2

出力例 1

k=1 のときを例に挙げて説明します。

S=\lbrace 1,3,4\rbrace は、T=\lbrace 3,4\rbrace とすると \left\vert T\right\vert=\left\vert S\right\vert-1 かつ \sum_{i\in T} A_i \ge 7 となるため条件を満たします。

他には、S=\lbrace 1,2,3\rbrace,\lbrace 2,3,4\rbrace,\lbrace 1,2,3,4\rbrace の 3 個が条件を満たします。よって、k = 1 のとき答えは 4 です。

入力例 2

1 5
7

出力例 2

1
0

入力例 3

9 18
1 9 5 6 2 7 1 4 8

出力例 3

C - Solve with Friends

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

なむか君は友達のなぷか君と協力して問題 1 , 問題 2 , \dots , 問題 N の N 個の問題を全て解くことになりました。

最初二人とも疲れは 0 ですが、問題を 1 問解くとその問題を解いた人の疲れが 1 増えます。問題 i を疲れが j のときに解くと、なむか君は A_i+C_j 分かかり、なぷか君は B_i+D_j 分かかります。ただし、2 人が同時に別の問題を解くことは出来ません。

なむか君となぷか君が N 個の問題を解く時間の総和の最小値を求めてください。

制約

1 \leq N\leq 2\times 10^5
1 \leq A_i,B_i,C_i,D_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
C_0 C_1 \dots C_{N-1}
D_0 D_1 \dots D_{N-1}

出力

答えを出力せよ。

入力例 1

出力例 1

なむか君が問題 1 , 問題 2 を順に解き、なぷか君が問題 3 を解くとき、解く時間の総和は以下のように計算できます。

なむか君が問題 1 を解く。なむか君の現在の疲れは 0 なので、解くのに A_1+C_0=1+1=2 分かかる。なむか君の疲れが 1 増える。
なむか君が問題 2 を解く。なむか君の現在の疲れは 1 なので、解くのに A_2+C_1=3+2=5 分かかる。なむか君の疲れが 1 増える。
なぷか君が問題 3 を解く。なぷか君の現在の疲れは 0 なので、解くのに B_3+D_0=2+1=3 分かかる。なぷか君の疲れが 1 増える。

よって、総和は 2+5+3=10 分で、このときが最小です。

入力例 2

出力例 2

入力例 3

8
21 85 72 22 81 20 88 28
75 22 78 92 55 56 73 44
39 14 64 27 73 42 16 84
27 7 91 85 69 95 70 27

出力例 3

D - Two Box

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) と Q 個のクエリが与えられます。i 個目のクエリは以下のような内容です。

A_{x_i} を y_i に変更し、その後の A について以下の問題の答えを求める。

白い箱と黒い箱と 1 から M の番号が付いた M 個のボールがあります。始め、全てのボールは白い箱に入っています。

ここで、あなたは以下の操作を N 回繰り返します。

1 \le x \le M を満たす整数 x を選ぶ。ボール x を今入っている箱からもう一方の箱に移動させる。

i 回目の操作終了後、黒い箱に入っているボールの番号は全て A_i 以下である必要があります。操作列としてあり得るものの個数を 998244353 で割ったあまりを求めてください。

クエリを順に処理してください。

制約

1 \le N,Q \le \textcolor{red}{3 \times 10^4}
1 \le M \le 15
1 \le x_i \le N
1 \le A_i,y_i \le M

部分点

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

N \le 2000,M \le 10,Q = 1 を満たすデータセットに正解した場合 10 点が与えられる。
Q = 1 を満たすデータセットに正解した場合追加で 10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N M Q
A_1 A_2 \dots A_N
x_1 y_1
x_2 y_2
\vdots
x_Q y_Q

出力

Q 行出力せよ。i 行目には i 個目のクエリの答えを出力せよ。

入力例 1

出力例 1

5
14

1 番目のクエリの際、A=(1,3,2) となっています。このとき、操作列としては例えば以下のようなものが考えられます。

x = 1 とする。白い箱から黒い箱にボール 1 が移動する。黒い箱の中にはボール 1 が入っている。
x = 3 とする。白い箱から黒い箱にボール 3 が移動する。黒い箱の中にはボール 1,3 が入っている。
x = 3 とする。黒い箱から白い箱にボール 1 が移動する。黒い箱の中にはボール 1 が入っている。

このほかに x の列として考えられるものは (1,1,1),(1,1,2),(1,2,1),(1,2,2) の 4 通りです。よって操作列としてあり得るのは 5 通りです。

入力例 2

6 8 1
3 8 7 7 1 6
1 4

出力例 2

入力例 3

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

出力例 3

E - Aim High

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

あなたは 2 次元平面を用いてゲームをします。始め、-100 \le x \le 100,-100 \le y \le 0 を満たす格子点 (x,y) に駒が 1 個ずつ置かれています。

あなたは以下の操作を 0 回以上行うことが出来ます。

2 個の点の組 (a,b),(c,d) であって、|a-c|+|b-d| = 1 かつ (a,b),(c,d) 両方に駒が 1 個以上あるものを選ぶ。(a,b) にある駒 1 個を (c,d) を中心として時計回りか反時計周りに 90 度回転させた点に置き、(c,d) にある駒を 1 個消す。（既に移動先の点に駒が置かれていても良い。）

あなたの目標は操作が全て終わったときに y 座標が N 以上であるいずれかの点に駒が置かれている状態にすることです。目標が達成可能か判定し、可能ならば操作列を 1 個構築してください。

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

制約

1 \le T \le 6
1 \le N \le 6

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで、\mathrm{case}_i とは i 番目のテストケースを意味する。各テストケースは以下の形式で与えられる。

出力

T 個のテストケースへの出力を与えられた順に改行区切りで出力せよ。

それぞれのテストケースについては、目標を達成することが出来ないならば -1 を、そうでないならば操作回数を K、i 回目の操作で (a_i,b_i) にある駒を (c_i,d_i) を中心として (e_i,f_i) に移動させるとき以下のように出力せよ。

K
a_1 b_1 c_1 d_1 e_1 f_1
a_2 b_2 c_2 d_2 e_2 f_2
\vdots
a_K b_K c_K d_K e_K f_K

入力例 1

1
1

出力例 1

1
1 0 0 0 0 1

1 回目の操作で、(1,0) にある駒を (0,0) を中心に時計回りに 90 度回転させて (0,1) に置きます。

この操作によって y 座標が 1 以上である点 (0,1) に駒を置くことが出来たので、目標を達成できました。

F - Train Seats

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N の番号がついた N 人の人が一列に並べられた M 個の椅子に座ります。左から i 番目の椅子を椅子 i と呼びます。人 i は椅子 A_i に座ります。

ある人が座った時に、その人の左右それぞれで最も近い座っている人のいる椅子の番号（それぞれない場合は 0,M+1）を L,R としたとき、座った人のスコアを R - L とします。

N 人が順番に座る方法は N! 通りありますが、N 人のスコアの総和としてあり得る最大値を求めてください。

制約

1 \le N \le 2 \times 10^5
N \le M \le 10^9
1 \le A_i \le M
i \neq j ならば A_i \neq A_j

部分点

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

N \le 500 を満たすデータセットに正解した場合 10 点が与えられる。
N \le 3000 を満たすデータセットに正解した場合追加で 10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3 10
3 7 10

出力例 1

例えば、人 3、人 1、人 2 の順に座る場合のスコアは以下のようになります。

人 3 が座る時、 L = 0,R = 11 となり、この人のスコアは 11 - 0 = 11 となる。
人 1 が座る時、 L = 0,R = 10 となり、この人のスコアは 10 - 0 = 10 となる。
人 2 が座る時、 L = 3,R = 10 となり、この人のスコアは 10 - 3 = 7 となる。

よって、スコアの総和は 11 + 10 + 7 = 28 となり、この時が最大です。

入力例 2

5 20
3 10 11 14 17

出力例 2

入力例 3

10 1000000000
136909656 243332691 643531997 505919307 43553384 657638276 57213246 179732866 357373203 182482400

出力例 3

7649951260

G - Many Common Segment Problems

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

PCT 君は以下のような問題を作りました。

Common Segment

N 個の区間 [L_1,R_1],[L_2,R_2],\dots,[L_N,R_N] が与えられます。ここで [L, R] は L 以上 R 以下の全ての整数からなる区間を意味します。

ここから 1 個以上の区間を選ぶ方法は 2^N-1 通りありますが、そのうち選んだ全ての区間の共通部分が空でないものの個数を 998244353 で割ったあまりを求めてください。

PCT 君は間違えてテストケースの L_i,R_i のうち一部の値をなくしてしまいました。困った彼のために以下の問題を解いてください。

Many Common Segment Testcases

Common Segment のテストケースが与えられます。ただし、なくしてしまった L_i,R_i の値は代わりに -1 が与えられます。

このとき、元のテストケースは 1 \le L_i \le R_i \le M\ (1 \le i \le N) を満たしていたとのことです。元のテストケースとしてあり得るもの全てに対して Common Segment を解き、答えの総和を 998244353 で割ったあまりを求めてください。

制約

1 \le N,M \le 10^5
L_i = -1 または 1 \le L_i \le M
R_i = -1 または 1 \le R_i \le M
L_i,R_i \ge 1 ならば L_i \le R_i

部分点

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

L_i,R_i \ge 1 を満たすデータセットに正解した場合 10 点が与えられる。
N,M \le 2000 を満たすデータセットに正解した場合 10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N M
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

答えを出力せよ。

入力例 1

出力例 1

テストケースとしてあり得るもの全てとそのテストケースに対する Common Segment の答えは以下の通りです。

(L_i,R_i) = (1,1),(2,2),(2,3) のとき、4 通り
(L_i,R_i) = (1,2),(2,2),(2,3) のとき、7 通り
(L_i,R_i) = (1,3),(2,2),(2,3) のとき、7 通り

よって、答えは 4 + 7 + 7 = 18 となります。

入力例 2

出力例 2

入力例 3

10 13
4 -1
-1 -1
7 11
-1 -1
-1 -1
-1 -1
11 -1
3 8
-1 9
-1 -1

出力例 3

841024210

H - Music Game

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N の番号がついた N 個のスイッチがあります。今全てのスイッチはオフになっています。
これからスイッチを自由な順番で 1 個ずつ押していきますが、それぞれのスイッチは壊れています。具体的には、スイッチ i は押すのに T_i 秒かかり、押すと以下のような挙動を示します。

確率 \frac{A_i}{B_i} でオンになる。
確率 1 - \frac{A_i}{B_i} で N 個のスイッチが全てオフになる。

スイッチがオンになるかどうかはスイッチを押す毎に独立に選択されます。また、あるスイッチを押している間他のスイッチを押すことは出来ません。

あなたの目標は出来るだけ早く全てのスイッチをオンにすることです。あなたが適切にスイッチを押したときに、全てのスイッチをオンにするのにかかる秒数の期待値 \bmod\ 998244353 を求めてください。

期待値 \bmod\ 998244353 の定義

求める期待値は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \neq 0 \pmod{998244353} となることも証明できます。よって、R \times Q = P \pmod{998244353},0 \le R < 998244353 を満たす整数 R が一意に定まります。この R を答えてください。

制約

1 \le N \le 2 \times 10^5
1 \le T_i \le 10^6
1 \le A_i \le B_i \le 10^6

入力

入力は以下の形式で標準入力から与えられます。

N
T_1 A_1 B_1
T_2 A_2 B_2
⋮
T_N A_N B_N

出力

答えを出力してください。

入力例 1

2
3 3 5
2 4 7

出力例 1

831870305

操作列の一例として、次のようなものが存在します。(この操作列が最適に操作をしているとは限りません。)

スイッチ 1 を 3 秒かけて押す。スイッチ 1 がオンになる。
スイッチ 2 を 2 秒かけて押す。全てのスイッチがオフになる。
スイッチ 2 を 2 秒かけて押す。スイッチ 2 がオンになる。
スイッチ 1 を 3 秒かけて押す。スイッチ 1 がオンになる。

この操作列では、かかる時間は 10 秒であり、このように操作が進む確率は \frac{3}{5} \times \frac{3}{7} \times \frac{4}{7} \times \frac{3}{5} = \frac{108}{1225} です。

また、このケースにおいて適切にスイッチを押したときに全てのスイッチをオンにするのにかかる秒数の期待値は \frac{65}{6} 秒となります。

入力例 2

出力例 2

914017655

入力例 3

出力例 3

923892723

I - Left Equals Right

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

(1,\dots,N) の順列 (P_1,\dots,P_N) であって、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

ある整数 i(1\le i\lt N) が存在して A_{P_1}+\dots+A_{P_i}=A_{P_{i+1}}+\dots+A_{P_N} が成立する。

制約

2 \le N\le 100
1 \le A_i \le 100

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3
4 9 5

出力例 1

(1,2,3) の順列は 3!(=6) 通りありますが、そのうち条件を満たすものは次の 4 つです。

(1,3,2)
(2,1,3)
(2,3,1)
(3,1,2)

例えば、 (1,3,2) は i=2 とすると A_1+A_3=A_2=9 であり、条件を満たしています。

入力例 2

2
100 100

出力例 2

入力例 3

8
3 2 6 3 1 2 4 5

出力例 3

J - Again Permutation Problem

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

(1,2,\dots,N) の順列が M 個与えられます。i 個目の順列は P_i = (P_{i,1},P_{i,2},\dots,P_{i,N}) です。

あなたは数列 Q=(1,2,\dots,N) を持っています。そして、以下の操作を 0 回以上行うことが出来ます。

1 \le i \le M を満たす整数 i を選び、Q を (Q_{P_{i,1}},Q_{P_{i,2}},\dots,Q_{P_{i,N}}) に更新する。

操作後の Q としてあり得る数列全てに対する転倒数の総和を 998244353 で割ったあまりを求めてください。

制約

1 \le N \le 30
1 \le M \le 30
P_i=(P_{i,1},P_{i,2},\dots,P_{i,N}) は (1,2,\dots,N) の順列

部分点

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

N \le 6 を満たすデータセットに正解した場合 10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N M
P_{1,1} P_{1,2} \dots P_{1,N}
P_{2,1} P_{2,2} \dots P_{2,N}
\vdots
P_{M,1} P_{M,2} \dots P_{M,N}

出力

答えを出力せよ。

入力例 1

3 2
1 2 3
2 3 1

出力例 1

あなたが得ることの出来る数列 Q は (1,2,3),(2,3,1),(3,1,2) の 3 個です。それぞれの転倒数は 0,2,2 なので答えは 0 + 2 + 2 = 4 です。

入力例 2

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

出力例 2

入力例 3

30 12
1 2 9 4 5 6 7 8 3 10 11 12 19 14 15 25 17 18 20 26 21 22 23 24 16 29 27 28 13 30
9 2 27 4 5 10 7 8 1 25 11 12 24 14 15 16 17 18 19 20 21 22 23 28 6 26 3 13 29 30
1 5 3 29 2 6 7 8 9 10 11 12 13 16 15 18 17 14 19 20 21 22 28 27 25 26 24 23 4 30
7 2 3 25 5 6 1 28 21 15 11 12 13 14 10 17 16 18 19 20 9 22 23 24 4 26 27 8 29 30
1 2 5 4 16 6 7 8 9 11 10 3 13 14 15 12 17 23 19 20 21 29 18 24 25 26 27 28 22 30
19 24 3 4 1 6 7 8 9 10 11 12 13 21 15 16 17 18 5 22 20 14 23 2 25 26 27 28 29 30
1 2 3 4 5 6 27 8 9 10 29 12 24 14 15 16 17 18 30 20 7 22 13 23 25 26 21 28 11 19
1 2 25 4 5 6 7 8 9 20 23 12 13 14 15 16 17 18 19 10 29 22 3 24 11 26 27 28 30 21
1 2 16 4 5 6 3 8 9 10 11 12 22 29 13 7 17 18 19 20 21 15 23 24 14 26 27 28 25 30
1 13 3 4 5 6 21 8 24 10 7 12 20 14 15 16 17 2 19 18 11 22 23 9 25 26 27 28 29 30
1 2 3 4 5 6 25 8 9 19 11 12 13 7 10 16 21 18 15 20 17 22 23 24 28 26 27 14 29 30
1 2 27 21 5 6 7 8 9 10 18 24 13 14 15 16 17 12 19 11 4 22 23 20 25 26 3 28 29 30

出力例 3

701414999

K - Peace with Magic

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

NPCA 国は横一列に並んだ N 個のマスからなり、左から順に 1 から N の番号がつけられています。ここで、マス i の高さを H_i とします。始め、H_1=H_2=\dots=H_N=0 となっています。

各 1\le i\le N-1 について、 H_i と H_{i+1} の差の絶対値が D_i 未満であるとき、マス i とマス i+1 の間で争いが起こってしまいます。さて、平和を愛する NPCA 国の王のなぷか君の目標はどの隣り合うマスの間でも争いが起きなくなることです。そのため、なぷか君は以下の魔法を 0 回以上かけることが出来ます。

H_i=H_{i+1}=\dots=H_{j} を満たす整数 i,j(1\le i\le j\le N) を選んで H_i,H_{i+1},\dots,H_{j} に 1 を加算する。

なぷか君が目標を達成するのに必要な魔法をかける回数としてあり得る最小値を求めてください。

制約

2 \le N \le 100
0 \le D_i \le 1000

入力

入力は以下の形式で標準入力から与えられる。

N
D_1 D_2 \dots D_{N-1}

出力

答えを出力せよ。

入力例 1

4
2 3 1

出力例 1

始め、(H_1,H_2,H_3,H_4)=(0,0,0,0) です。例えば、次のように魔法をかけることができます。

(i,j)=(1,3) とする。(H_1,H_2,H_3,H_4)=(1,1,1,0) となる。
(i,j)=(1,2) とする。(H_1,H_2,H_3,H_4)=(2,2,1,0) となる。
(i,j)=(2,2) とする。(H_1,H_2,H_3,H_4)=(2,3,1,0) となる。
(i,j)=(2,2) とする。(H_1,H_2,H_3,H_4)=(2,4,1,0) となる。

目標を達成するまでに魔法を 4 回かけており、これが最小です。 i=j となる i,j を選んでもよいことに注意してください。

入力例 2

3
0 0

出力例 2

入力例 3

10
1 9 5 6 2 7 1 4 8

出力例 3

L - Construction of Town

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N-1 の広義単調増加である正整数列 X=(X_1,X_2,\dots,X_{N-1}) が与えられます。

N 頂点 M 辺単純連結無向グラフ G のコストを \sum_{i=1}^{N} \sum_{j=i+1}^{N} X_{d(i,j)} と定義します。ただし、d(i,j) は G 上で頂点 i から頂点 j へ移動するまでに通る辺の本数としてあり得る最小値として定義します。

コストが最小になる N 頂点 M 辺単純連結無向グラフ G を 1 個構築してください。

制約

2 \le N \le 100
N-1 \le M \le \frac{N(N-1)}{2}
1 \le X_1 \le X_2 \le \dots \le X_{N-1} \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 X_2 \dots X_{N-1}

出力

グラフにおいて i 本目の辺が頂点 A_i と頂点 B_i を結ぶとき、以下のように M 行出力せよ。

A_1 B_1
A_2 B_2
\vdots
A_M B_M

入力例 1

3 2
4 5

出力例 1

1 2
1 3

この出力の場合、コストは X_{d(1,2)} + X_{d(1,3)} + X_{d(2,3)} = X_1 + X_1 + X_2 = 13 となります。

コストが 12 以下になる 3 頂点 2 辺無向グラフは存在しないため、この出力は正答です。

入力例 2

4 6
12 34 56

出力例 2

M - Admired Person

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

なむか君は長さ N の数列 A=(A_1,A_2,\dots, A_N) を、なむか君のあこがれの人は長さ M の数列 B=(B_1,B_2,\dots,B_M) を持っています。

なむか君はあこがれの人に近づくために A から異なる M 個の要素を選び、好きな順番で並べて長さ M の数列 C=(C_1, C_2,\dots,C_M) を作ります。

このとき、\sum_{i=1}^M \left\vert B_i-C_i\right\vert としてあり得る最小値を求めてください。

制約

1 \leq M\leq N\leq 5000
1 \leq A_i,B_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

出力

答えを出力せよ。

入力例 1

5 3
2 6 5 1 1
6 3 8

出力例 1

例えば、 C=(6,2,5) とすることで最小値 \left\vert 6-6\right\vert+\left\vert 3-2\right\vert+\left\vert 8-5\right\vert=4 を達成できます。

入力例 2

3 2
1 1 9
1 1

出力例 2

入力例 3

11 7
13 21 9 5 16 32 15 29 20 40 4
24 34 43 39 18 30 11

出力例 3

N - Product Matrix

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 100 点

注意

この問題の TL は厳しめに設定されています。

問題文

各要素が 1 次の多項式である N 次正方行列 P(x) が与えられます。P(x) の (i,j) 成分は a_{i,j} x + b_{i,j} です。

\prod_{i=0}^{M-1} P(2^ix) = P(x) P(2x) \dots P(2^{M-1}x) の (1,1) 成分 f(x) = \sum_{i=0}^{M} c_ix^i の各係数 c_0,c_1,\dots,c_M を \bmod\ 10^9 + 7 で求めてください。

制約

1 \le N \le 6
1 \le M \le 5 \times 10^5
0 \le a_{i,j},b_{i,j} < 10^9 + 7

入力

入力は以下の形式で標準入力から与えられる。

N M
a_{1,1} a_{1,2} \dots a_{1,N}
a_{2,1} a_{2,2} \dots a_{2,N}
\vdots
a_{N,1} a_{N,2} \dots a_{N,N}
b_{1,1} b_{1,2} \dots b_{1,N}
b_{2,1} b_{2,2} \dots b_{2,N}
\vdots
b_{N,1} b_{N,2} \dots b_{N,N}

出力

c_0,c_1,\dots,c_M を \bmod\ 10^9 + 7 でこの順に改行区切りで出力せよ。なお、c_i は 0 以上 10^9 + 7 未満で出力せよ。

入力例 1

出力例 1

4
8
14

P(x)P(2x) = \begin{pmatrix} x+2 & 2x \\ 3x+1 & 4x+2 \end{pmatrix} \begin{pmatrix} 2x+2 & 4x \\ 6x+1 & 8x+2 \end{pmatrix} = \begin{pmatrix} 14x^2+8x+4 & 20x^2 + 12x \\ 30x^2+24x+4 & 44x^2+28x+4 \end{pmatrix} であるため、f(x) = 14x^2 + 8x + 4 です。

入力例 2

4 10
520471651 866160932 848899741 650346545
756377215 402412491 920748640 255249004
371442152 93295238 350011159 679848583
528399020 957465601 22001245 407745834
363922864 418156995 324388560 611306817
671914474 323815171 638034305 796072406
765823638 254662378 175686978 123364350
786531344 396717902 774813609 895184869

出力例 2

入力例 3

6 23
101670804 457970042 521121852 851881468 298366530 271962368
881900040 161849089 409608300 527884448 898980182 538728808
624037110 955334452 644656371 684645088 612630196 365375437
135489465 838789241 374389562 238291227 977400760 496900790
921432977 606711088 740916866 405856539 822796504 19906274
631056816 823924205 719574385 332547421 298321832 594473309
145245098 519214077 131200957 702537460 682007417 304700059
419152148 943797679 19640790 464034522 441355576 454665900
822982080 991406863 249537771 45708817 502700323 683669766
326512291 871373558 410675396 208947517 645163777 622674739
606534945 349193474 895660493 579299011 661372605 314032169
497618687 102217570 426720147 363888279 910628723 894753922

出力例 3

O - New School Term

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

NPCA 校には 2N 人の生徒がおり、各生徒には 1 から 2N の順番が付けられています。なぷか君は NPCA 校の教師で、生徒を N 人ずつの 2 つのクラスに分けることになりました。

ここで、クラス分けの不満度を以下のように定義します。

整数 i(1 \le i \le M) のうち、生徒 A_i と生徒 B_i が同じクラスにいるもの全てに対する 2^i の総和

なぷか君のために、不満度が最小となるクラス分けの方法を 1 つ構築してください。

制約

1 \le N\le 5000
0 \le M\le 10^6
1\le A_i< B_i \le 2N
i\ne j ならば (A_i,B_i)\ne (A_j,B_j)
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

以下のように出力せよ。

S_1 S_2 \dots S_{2N}

ここで、S_i は 0 か 1 のいずれかであり、生徒 i がどちらのクラスに属するかを示すものとする。

条件を満たすクラス分けが複数存在する場合は、どれを出力しても正解となる。

入力例 1

出力例 1

生徒 1 と生徒 3 からなるクラスと生徒 2 と生徒 4 からなるクラスに分けたとき、不満度は以下のように計算されます。

i=1 について、生徒 1 と生徒 3 は同じクラスである。
i=2 について、生徒 2 と生徒 4 は同じクラスである。
i=3 について、生徒 1 と生徒 4 は異なるクラスである。
i=4 について、生徒 1 と生徒 2 は異なるクラスである。

以上よりこのクラス分けの不満度は 2^1 + 2^2 = 6 であり、この分け方が最小です。1010 を出力してもよいです。

0111 のように分けると不満度は 4 ですが、N 人ずつのクラスに分かれていないため条件を満たしません。

入力例 2

1 0

出力例 2

入力例 3

出力例 3

P - Make Testcase

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

Universal Cup 参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

PCT 君は次のような問題を作りました。

Shuffle and Increasing

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

A を並び替えて得られる列のうち、A_i < A_{i+1} を満たす i がちょうど M 個あるものの個数を 998244353 で割ったあまりを求めてください。
制約

1 \le N \le 30

0 \le M \le N-1

1 \le A_i \le N

PCT 君は上記の問題で答えが X になる入力を作りたいです。そのような入力が存在するか判定し、存在するならば 1 個構築してください。

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

制約

1 \le T \le 10^4
0 \le X < 998244353

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで、\mathrm{case}_i とは i 個目のテストケースである。それぞれのテストケースは以下の形式で与えられる。

出力

T 個のテストケースへの出力を改行区切りで出力せよ。

それぞれのテストケースについては、もし条件を満たす入力が存在しないならば -1 を、するならば以下のように出力せよ。

N M
A_1 A_2 \dots A_N

入力例 1

出力例 1

4 2
1 3 3 2
6 3
6 2 6 4 5 1 
17 10
8 7 1 14 8 5 12 5 2 17 7 16 15 17 14 15 6 
24 14
16 8 14 18 15 16 21 4 10 14 3 4 22 8 16 11 22 17 11 5 12 2 13 18

1 個目のテストケースについて、A を並び替えて得られる列のうち条件を満たすものは以下の 4 個です。よってこの入力は条件を満たしています。

(1,2,3,3)
(1,3,2,3)
(2,3,1,3)
(3,1,2,3)