A - Chords and Checkered

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

整数 L,K 及び長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます． ここで，2K < L 及び 0 \leq A_1 < A_2 < \cdots < A_N < L が保証されます．

周の長さが L の円を考えます． この円の適当な点を基準点としてとり，そこから円周上を距離 x だけ時計回りに進んだ場所を座標 x の点と呼ぶことにします． また，各 i (1 \leq i \leq N) について， 座標 A_i の点と座標 A_i+K の点を結ぶ弦を考え，これを弦 i と呼ぶことにします．

弦の集合 s に対して，以下の手順で スコアを定めます．

  • s に含まれる弦をすべて描く．描いた弦によって円がいくつかの領域に分かれるので，それらを白と黒で塗る． まず円の中心が含まれる領域を白く塗り，残りの領域は，(長さ正の線分で)隣接する領域の色が異なるように塗る． このような塗り方は常に一意に存在することが証明できる． ここで黒く塗られた領域の個数をスコアとする．

s としてあり得る集合は 2^N 通りあります． これらすべてに対するスコアの総和を 998244353 で割ったあまりを求めてください．

制約

  • 1 \leq K
  • 2K < L \leq 10^9
  • 1 \leq N \leq 250000
  • 0 \leq A_1 < A_2 < \cdots < A_N < L
  • 入力はすべて整数

入力

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

L K N
A_1 A_2 \ldots A_N

出力

答えを出力せよ．

入力例 1

5 2 2
0 1

出力例 1

4
  • 弦を 1 つも選ばない場合，スコアは 0 です．
  • 弦 1 を選ぶ場合，スコアは 1 です．
  • 弦 2 を選ぶ場合，スコアは 1 です．
  • 弦 1,2 を選ぶ場合，スコアは 2 です．

よって，これらの合計である 4 が答えです．

入力例 2

3 1 1
2

出力例 2

1

入力例 3

5 2 5
0 1 2 3 4

出力例 3

80

入力例 4

7 3 3
0 2 3

出力例 4

12

Score : 700 points

Problem Statement

You are given integers L, K and a length-N non-negative integer sequence A = (A_1, A_2, \ldots, A_N). Here, 2K < L and 0 \leq A_1 < A_2 < \cdots < A_N < L are guaranteed.

Consider a circle with circumference L. Take an arbitrary point on this circle as the reference point, and call the point reached by traveling clockwise distance x along the circumference from there the point with coordinate x. Also, for each i (1 \leq i \leq N), consider the chord connecting the point with coordinate A_i and the point with coordinate A_i + K, and call this chord i.

For a set of chords s, the score is determined by the following procedure:

  • Draw all chords contained in s. The drawn chords divide the circle into several regions; color them with white and black. First, color the region containing the center of the circle white, and color the remaining regions so that adjacent regions (connected by a line segment of positive length) have different colors. It can be proved that such a coloring method always exists uniquely. The score is the number of regions colored black.

There are 2^N possible sets for s. Find the sum, modulo 998244353, of scores for all of these.

Constraints

  • 1 \leq K
  • 2K < L \leq 10^9
  • 1 \leq N \leq 250000
  • 0 \leq A_1 < A_2 < \cdots < A_N < L
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

L K N
A_1 A_2 \ldots A_N

Output

Output the answer.

Sample Input 1

5 2 2
0 1

Sample Output 1

4
  • When no chords are chosen, the score is 0.
  • When chord 1 is chosen, the score is 1.
  • When chord 2 is chosen, the score is 1.
  • When chords 1, 2 are chosen, the score is 2.

Therefore, the answer is 4, which is the sum of these.

Sample Input 2

3 1 1
2

Sample Output 2

1

Sample Input 3

5 2 5
0 1 2 3 4

Sample Output 3

80

Sample Input 4

7 3 3
0 2 3

Sample Output 4

12
B - Cyclic Jump

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1000 点

問題文

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

あなたは今，数直線上の座標 0 の位置に立っており，今から以下の操作を好きな回数行います．

  • A の好きな要素 A_i を自由に選ぶ．また，正負のうち好きな方向を選ぶ． そして，選んだ方向に距離 A_i だけジャンプする．

あなたは以下の条件を満たす操作列に興味があります．

  • 操作を 1 回以上行い，最終的に座標 0 に戻ってくる．
  • 途中で座標が負の領域に入らない．
  • 連続して同じ距離かつ異なる方向にジャンプすることがない．

条件を満たす操作列のコストを，その操作列に従って動いた際に訪れる座標の最大値とします． 条件を満たす操作列のコストとしてあり得る最小値を求めてください． なおこの問題の制約より，条件を満たす操作列は必ず存在します．

1 つの入力につき，T 個のテストケースを解いてください．

制約

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}
  • 1 つの入力における N の総和は 250000 を超えない
  • 入力はすべて整数

入力

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

T
case_1
case_2
\vdots
case_T

各テストケースは以下の形式で与えられる．

N
A_1 A_2 \cdots A_N

出力

各テストケースに対し，答えを出力せよ．

入力例 1

5
2
2 3
2
3 6
3
3 5 6
2
999999999999999999 1000000000000000000
3
999999999999999998 999999999999999999 1000000000000000000

出力例 1

4
6
6
1999999999999999998
1000000000000000000

1 つ目のテストケースについて考えます． 座標 0 \to 2 \to 4 \to 1 \to 3 \to 0 という移動方法は条件を満たし，このときのコストは 4 です． コストが 4 未満になる操作列は存在しないため，答えは 4 になります．

Score : 1000 points

Problem Statement

You are given a length-N positive integer sequence A = (A_1, A_2, \ldots, A_N).

You are now standing at coordinate 0 on the number line, and will perform the following operation any number of times:

  • Choose any element A_i from A freely. Also, choose either positive or negative direction freely. Then, jump distance A_i in the chosen direction.

You are interested in operation sequences that satisfy the following conditions:

  • Perform the operation at least once and finally return to coordinate 0.
  • Never enter the negative region during the process.
  • Never jump consecutively the same distance in different directions.

The cost of an operation sequence satisfying the conditions is the maximum value among the coordinates visited when moving according to that operation sequence. Find the minimum possible cost among operation sequences satisfying the conditions. Under the constraints of this problem, an operation sequence satisfying the conditions always exists.

Solve T test cases for one input.

Constraints

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 1 \leq A_1 < A_2 < \cdots < A_N \leq 10^{18}
  • The sum of N in one input does not exceed 250000.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

For each test case, output the answer.

Sample Input 1

5
2
2 3
2
3 6
3
3 5 6
2
999999999999999999 1000000000000000000
3
999999999999999998 999999999999999999 1000000000000000000

Sample Output 1

4
6
6
1999999999999999998
1000000000000000000

Consider the first test case. The movement method 0 \to 2 \to 4 \to 1 \to 3 \to 0 satisfies the conditions, and the cost in this case is 4. There is no operation sequence with cost less than 4, so the answer is 4.
C - Product of Max of Sum of Subtree

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1400 点

問題文

1 から N までの番号がついた N 頂点からなる木があり，i 番目の辺は頂点 A_i と頂点 B_i を結んでいます．

今からこの木の各頂点に -(N-1) 以上 1 以下の実数をランダムに書き込みます． 乱数の分布はすべて独立な一様分布です．

その後，木のスコアを次のように定義します．

  • 各頂点 i について，x_i を以下のように定義する．
    • 頂点 i を含むような連結な部分グラフの頂点に書かれた値の総和の最大値
  • 0 \leq x_i \leq 1 を満たさない i が存在する場合，木のスコアは 0 となる．
  • そうでない場合，木のスコアは \prod_{1 \leq i \leq N} x_i となる．

木のスコアの期待値を \text{mod }{998244353} で求めてください．

期待値 \text{mod }{998244353} の定義

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

制約

  • 1 \leq N \leq 5000
  • 1 \leq A_i,B_i \leq N
  • 入力されるグラフは木である

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

答えを出力せよ．

入力例 1

1

出力例 1

499122177

スコアの期待値は 1/2 です．

入力例 2

2
1 2

出力例 2

873463809

スコアの期待値は 1/8 です．

入力例 3

3
1 2
2 3

出力例 3

842653798

スコアの期待値は 13/648 です．

入力例 4

5
1 2
2 3
3 4
4 5

出力例 4

132050425

スコアの期待値は 41/187500 です．

入力例 5

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

出力例 5

243711918

スコアの期待値は 2477/30064771072 です．

Score : 1400 points

Problem Statement

There is a tree with N vertices numbered from 1 to N, where the i-th edge connects vertices A_i and B_i.

We will now randomly write real numbers between -(N-1) and 1 (inclusive) on each vertex of this tree. The random number distributions are all independent uniform distributions.

Then, the score of the tree is defined as follows:

  • For each vertex i, define x_i as follows:
    • The maximum value of the sum of values written on vertices of connected subgraphs that contain vertex i
  • If there exists i that does not satisfy 0 \leq x_i \leq 1, the tree's score is 0.
  • Otherwise, the tree's score is \prod_{1 \leq i \leq N} x_i.

Find the expected value \text{mod }{998244353} of the tree's score.

Definition of expected value \text{mod }{998244353}

It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when the value is expressed as an irreducible fraction \frac{P}{Q}, we have Q \neq 0 \pmod{998244353}. Therefore, an integer R satisfying R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 is uniquely determined. Answer this R.

Constraints

  • 1 \leq N \leq 5000
  • 1 \leq A_i, B_i \leq N
  • The input graph is a tree.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Output the answer.

Sample Input 1

1

Sample Output 1

499122177

The expected value of the score is 1/2.

Sample Input 2

2
1 2

Sample Output 2

873463809

The expected value of the score is 1/8.

Sample Input 3

3
1 2
2 3

Sample Output 3

842653798

The expected value of the score is 13/648.

Sample Input 4

5
1 2
2 3
3 4
4 5

Sample Output 4

132050425

The expected value of the score is 41/187500.

Sample Input 5

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

Sample Output 5

243711918

The expected value of the score is 2477/30064771072.
D - Four Jewels

Time Limit: 15 sec / Memory Limit: 1024 MiB

配点 : 1700 点

問題文

この世界には 1 から K(=4) までの番号がついた K 種類の宝石があります． 種類 i の宝石の大きさ 1 あたりの価値は W_i です．

すぬけくんは N 個の宝石を持っています． i 番目の宝石は種類 A_i で，大きさ B_i です． また，すぬけくんは N 個の箱を持っており，i 番目の箱は大きさ i です．

すぬけくんは今から，それぞれの箱に宝石を 1 つずつ入れます． 宝石の大きさが箱より大きいときは，箱に入るように宝石を削ります． つまり，宝石 i を箱 j に入れると，その価値は W_{A_i} \times \min(B_i,j) になります．

宝石の価値の総和としてありうる最大値を求めてください．

制約

  • K=4
  • 1 \leq W_1 < W_2 < \cdots < W_K \leq 10^6
  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq K
  • 1 \leq B_i \leq N
  • 入力はすべて整数である

入力

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

N K
W_1 W_2 \ldots W_K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ．

入力例 1

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

出力例 1

15

宝石 1,2,3 をそれぞれ箱 3,1,2 に入れると，価値の総和は 4 \times \min(2,3)+1 \times \min(3,1)+3 \times \min(2,2)=15 となり，これが最大です．

入力例 2

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

出力例 2

10

入力例 3

6 4
1 3 8 10
2 2
1 4
2 2
3 1
3 4
4 3

出力例 3

86

入力例 4

15 4
239277 249169 419371 744281
2 14
1 4
1 11
4 12
1 7
2 12
3 15
2 5
3 4
1 8
3 2
4 1
1 15
3 5
2 8

出力例 4

39858078

Score : 1700 points

Problem Statement

In this world, there are K types of gems numbered from 1 to K(=4). The value per unit size of a gem of type i is W_i.

Snuke has N gems. The i-th gem is of type A_i and has size B_i. Also, Snuke has N boxes, where the i-th box has size i.

Snuke will now put one gem in each box. When a gem's size is larger than the box, the gem is cut to fit in the box. That is, when gem i is put in box j, its value becomes W_{A_i} \times \min(B_i, j).

Find the maximum possible sum of gem values.

Constraints

  • K = 4
  • 1 \leq W_1 < W_2 < \cdots < W_K \leq 10^6
  • 1 \leq N \leq 250000
  • 1 \leq A_i \leq K
  • 1 \leq B_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
W_1 W_2 \ldots W_K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer.

Sample Input 1

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

Sample Output 1

15

If gems 1, 2, 3 are put in boxes 3, 1, 2, respectively, the sum of values is 4 \times \min(2, 3) + 1 \times \min(3, 1) + 3 \times \min(2, 2) = 15, which is maximum.

Sample Input 2

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

Sample Output 2

10

Sample Input 3

6 4
1 3 8 10
2 2
1 4
2 2
3 1
3 4
4 3

Sample Output 3

86

Sample Input 4

15 4
239277 249169 419371 744281
2 14
1 4
1 11
4 12
1 7
2 12
3 15
2 5
3 4
1 8
3 2
4 1
1 15
3 5
2 8

Sample Output 4

39858078