A - Apple Addiction

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

1 から N までの番号のついた N 個のりんごがあります． りんご i のおいしさは A_i です． A_i が負であることもありえます． また，整数 K が与えられます．

あなたは以下の操作を好きな回数 (0 回でもよい) 繰り返すことができます．

  • 整数 i (1 \leq i \leq N-K+1) を選び，りんご i,i+1,\cdots,i+K-1 を食べる． なお，以前の操作ですでに食べていたりんごについては何もしない．

最終的にあなたが食べたりんごのおいしさの総和としてありうる最大値を求めてください．

制約

  • 1 \leq K \leq N \leq 250000
  • -10^9 \leq A_i \leq 10^9
  • 入力される値はすべて整数．

入力

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

N K
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

4 2
2 -1 2 -2

出力例 1

3

次のような操作が考えられます．

  • i=1 を選び，りんご 1,2 を食べる．
  • i=2 を選び，りんご 3 を食べる．(りんご 2 はすでに食べているので何もしない)

このとき，食べたりんごのおいしさの総和は A_1+A_2+A_3=3 になります． どのように操作を行っても，食べたりんごのおいしさの総和が 3 を超えることはありません． よって答えは 3 です．

入力例 2

5 5
3 1 4 1 5

出力例 2

14

入力例 3

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

出力例 3

0

入力例 4

20 4
573641910 -499039319 421342458 893335602 -961457884 -190195710 -497364364 -954575123 41286305 -310659388 -451608793 122064200 -719921087 87712135 43831420 714154567 -451280 -161259952 488561040 -501663741

出力例 4

2561828581
B - Max Degree Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

1 から N までの番号のついた N 頂点からなる単純連結無向グラフ G があります． G は M 本の辺を持ち，i 番目の辺は頂点 A_i,B_i を結んでいます．

各 k=1,2,\cdots,N について，以下の問題に答えて下さい．

  • G の全域木 T を 1 つ自由にとることを考える． このとき，T における頂点 1,2,\cdots,k の次数の総和としてあり得る最大値を求めよ．

制約

  • 2 \leq N \leq 250000
  • N-1 \leq M \leq 250000
  • 1 \leq A_i,B_i \leq N
  • 与えられるグラフは単純かつ連結．
  • 入力される値はすべて整数．

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

N 行出力せよ． i 行目には，k=i に対する答えを出力せよ．

入力例 1

4 4
1 2
2 3
3 1
1 4

出力例 1

3
4
5
6

k=1 について考えます． 1,3,4 番目の辺を使う全域木を考えると頂点 1 の次数が 3 になり，これが最大です．

k=2 について考えます． 1,2,4 番目の辺を使う全域木を考えると頂点 1,2 の次数がそれぞれ 2,2 になり，その和は 4 です． 頂点 1,2 の次数の和が 4 を超える全域木は存在しないため，答えは 4 です．

入力例 2

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

出力例 2

2
4
5
7
8

入力例 3

2 1
2 1

出力例 3

1
2

入力例 4

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

出力例 4

3
8
10
12
13
14
15
16
17
18
C - Power Convergence

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

整数 N が与えられます．

正整数 x に対し，f(x) を次のように定義します．

  • 非負整数 k であって，x^k \equiv x^{k+1} \mod N が成り立つものを考える． このような k が存在する場合，その最小値を f(x) とする． 存在しない場合 f(x)=0 とする．

\sum_{1 \leq x \leq N} f(x) を求めてください．

1 つの入力ファイルにつき，T 個のテストケースに答えて下さい．

制約

  • 1 \leq T \leq 10
  • 2 \leq N \leq 10^9
  • 入力される値はすべて整数．

入力

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

T
case_1
case_2
\vdots
case_T

各テストケース case_i は以下の形式である．

N

出力

T 行出力せよ． i 行目には case_i の答えを出力せよ．

入力例 1

10
2
3
4
5
6
7
8
9
10
11

出力例 1

1
1
3
1
3
1
9
5
3
1

例えば N=4 のとき f(x) の値は以下のようになります．

  • f(1)=0\ \ \ \ (1^0 \equiv 1^1 \mod 4)
  • f(2)=2\ \ \ \ (2^2 \equiv 2^3 \mod 4)
  • f(3)=0\ \ \ \ (3^k \equiv 3^{k+1} \mod 4 を満たす k は存在しない)
  • f(4)=1\ \ \ \ (4^1 \equiv 4^2 \mod 4)

よって答えは 0+2+0+1=3 です．

入力例 2

10
91
92
93
94
95
96
97
98
99
100

出力例 2

3
7
3
3
3
119
1
27
11
31
D - Two Xor

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

あなたは，次の操作を高々 2 回行うことができます． なお，\oplus はビット単位 \mathrm{XOR} 演算を表します．

  • 非負整数 X を自由に選ぶ． その後，各 i=1,2,\cdots,N について，A_i の値を据え置くかもしくは A_i \oplus X で置き換える．

操作後の A の要素の最大値としてあり得る最小値を求めてください．

ビット単位 \mathrm{XOR} 演算とは

非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。

  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

  • 1 \leq N \leq 2^{18}
  • 0 \leq A_i < 2^{18}
  • 入力される値はすべて整数．

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

4
0 1 2 3

出力例 1

0

例えば，以下のような操作が考えられます．

  • X=1 を選ぶ．
    • i=2 について，A_2 の値を 1 \oplus 1=0 で置き換える．
    • i=4 について，A_4 の値を 3 \oplus 1=2 で置き換える．
  • X=2 を選ぶ．
    • i=3 について，A_3 の値を 2 \oplus 2=0 で置き換える．
    • i=4 について，A_4 の値を 2 \oplus 2=0 で置き換える．

このとき，操作後の A の要素の最大値は 0 になります． これは明らかに達成可能な最小値なので，答えは 0 です．

入力例 2

3
1 4 10

出力例 2

1

入力例 3

5
2023 2023 2023 2023 2023

出力例 3

0

入力例 4

27
206264 140501 79 66028 206233 140291 206082 140347 65912 140301 65824 140404 65851 65986 140497 140526 206162 140513 66031 206294 206085 186 206157 66019 140407 65923 65806

出力例 4

192
E - Min Subtraction

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

あなたは以下の操作を好きな回数 (0 回でもよい) 繰り返すことができます．

  • 整数 i (1 \leq i \leq N-1) を選ぶ． v=\min(A_i,A_{i+1}) とする．A_i の値を A_i-v で置き換え，A_{i+1} の値を A_{i+1}-v で置き換える．

操作後の A に含まれる 0 の個数の最大値を求めて下さい．

制約

  • 2 \leq N \leq 250000
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数．

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

4
1 2 1 2

出力例 1

3

次のように操作を行えばよいです．

  • i=1 で操作し，A=(0,1,1,2) になる．
  • i=2 で操作し，A=(0,0,0,2) になる．

このとき，A は 3 個の 0 を含みます． A が 4 個の 0 を含むようにすることはできないので，3 が答えになります．

入力例 2

5
1 1 1 1 1

出力例 2

4

入力例 3

6
6 5 4 3 2 1

出力例 3

5

入力例 4

20
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

出力例 4

13
F - Adjacent Binomial Coefficients

Time Limit: 10 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

整数 N,M,K が与えられます．

長さ N の非負整数列 A=(A_1,A_2,\cdots,A_N) であって，以下の条件を両方満たすものをよい数列と呼ぶことにします．

  • \sum_{1 \leq i \leq N}A_i=M
  • A_1=K

よい数列 A に対して，f(A) を次のように定義します．

\[ f(A)=\prod_{1 \leq i \leq N-1} {A_i+A_{i+1} \choose A_i } \]

すべてのよい数列に対する f(A) の総和を 998244353 で割った余りを求めてください．

制約

  • 2 \leq N \leq 250000
  • 0 \leq K \leq M \leq 250000
  • 入力される値はすべて整数．

入力

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

N M K

出力

答えを出力せよ．

入力例 1

3 2 1

出力例 1

3

よい数列は 2 通りあり，対応する f(A) の値は以下のとおりです．

  • A=(1,0,1): f(A)={1 \choose 1} \times {1 \choose 0}=1

  • A=(1,1,0): f(A)={2 \choose 1} \times {1 \choose 1}=2

よって答えは 1+2=3 です．

入力例 2

5 10 3

出力例 2

27670

入力例 3

100 0 0

出力例 3

1

入力例 4

100 1000 10

出力例 4

75806874
G - Fusion

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1600 点

問題文

1 から N までの番号のついた N 頂点からなる木 T があります． i 番目の辺は頂点 A_i と B_i を結んでいます． また，各頂点には整数が書かれており，頂点 i に書かれている整数は V_i です．

あなたは今から以下の操作を N-1 回行います．

  • T の辺を 1 つ選び，縮約する． 縮約前の 2 つの頂点に書かれていた整数を x,y とおき，縮約後の頂点には x \times y+1 を書き込む．

操作を行う方法は (N-1)! 通りあります． 全ての方法について，最終的に残る 1 頂点に書かれた値を求めたとします． これら (N-1)! 個の値の総和を 998244353 で割った余りを求めてください．

辺の縮約とは

グラフ G について，辺 (u,v) を縮約する操作とは，頂点 u,v を 1 つの頂点にまとめる操作です． より正確には，縮約とは G を以下のように変化させる操作です．

  • G から辺 (u,v) および頂点 u,v を削除し，新しい頂点 (これを w と呼ぶ) を追加する．
  • u に接続する各辺 (u,x) を削除し，変わりに辺 (w,x) を追加する．
  • v に接続する各辺 (v,x) を削除し，変わりに辺 (w,x) を追加する．

制約

  • 1 \leq N \leq 5000
  • 1 \leq V_i < 998244353
  • 1 \leq A_i,B_i \leq N
  • 入力されるグラフは木．
  • 入力される値はすべて整数．

入力

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

N
V_1 V_2 \cdots V_N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

答えを出力せよ．

入力例 1

3
1 2 3
1 2
3 2

出力例 1

18

操作を行う方法は以下の 2 通りあります．

  • 最初の操作で辺 (1,2) を選んだ場合，縮約後の頂点には 1 \times 2+1=3 が書き込まれます． 次の操作では，縮約によってできた頂点と頂点 3 を縮約します． すると，3 \times 3+1=10 が書かれた頂点が残ります．
  • 最初の操作で辺 (3,2) を選んだ場合，縮約後の頂点には 3 \times 2+1=7 が書き込まれます． 次の操作では，縮約によってできた頂点と頂点 1 を縮約します． すると，7 \times 1+1=8 が書かれた頂点が残ります．

よって求める答えは 10+8=18 です．

入力例 2

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

出力例 2

136

入力例 3

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

出力例 3

54388564

入力例 4

20
785439575 250040586 709423541 945005786 19237226 404191280 250876593 22672564 519729087 344065187 273714213 560047126 139793597 542901248 520999410 855572558 498896933 418633758 742973826 248730679
12 9
19 18
9 5
6 20
8 16
3 6
4 14
6 12
16 12
3 17
14 19
15 16
17 13
11 14
17 2
9 7
18 10
19 3
1 18

出力例 4

768399804