E - Simple path

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 頂点の木 T があり、 i (1\leq i\leq N-1) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

T 上の相異なる 2 頂点 X,Y が与えられるので、 頂点 X から頂点 Y への単純パス上の頂点（端点含む）を順に列挙してください。

ただし、木上の任意の相異なる 2 頂点 a,b について、a から b への単純パスがただ一つ存在することが証明できます。

単純パスとは？ グラフ G 上の頂点 X,Y に対して、頂点列 v_1,v_2, \ldots, v_k であって、 v_1=X, v_k=Y かつ、1\leq i\leq k-1 に対して v_i と v_{i+1} が辺で結ばれているようなものを頂点 X から頂点 Y への パス と呼びます。 さらに、v_1,v_2, \ldots, v_k がすべて異なるようなものを頂点 X から頂点 Y への 単純パス と呼びます。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq X,Y\leq N
  • X\neq Y
  • 1\leq U_i,V_i\leq N
  • 入力はすべて整数
  • 与えられるグラフは木

入力

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

頂点 X から頂点 Y への単純パス上の頂点番号を順に空白区切りで出力せよ。

入力例 1

5 2 5
1 2
1 3
3 4
3 5

出力例 1

2 1 3 5

木 T は以下のような形であり、頂点 2 から頂点 5への単純パスは 頂点 2 \to 頂点 1 \to 頂点 3 \to 頂点 5 となります。
よって、2,1,3,5 をこの順に空白区切りで出力します。

入力例 2

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

出力例 2

1 2

木 T は以下のような形です。

Score : 300 points

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

What is a simple path? For vertices X and Y in a graph G, a path from vertex X to vertex Y is a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for each 1\leq i\leq k-1. Additionally, if all of v_1,v_2, \ldots, v_k are distinct, the path is said to be a simple path from vertex X to vertex Y.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq X,Y\leq N
  • X\neq Y
  • 1\leq U_i,V_i\leq N
  • All values in the input are integers.
  • The given graph is a tree.

Input

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

N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

Output

Print the indices of all vertices along the simple path from vertex X to vertex Y in order, with spaces in between.

Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

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

Sample Output 2

1 2

The tree T is shown below.
F - Dice Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？

  • 1\le A_i \le M (1 \le i \le N)

  • \displaystyle\sum _{i=1}^N A_i \leq K

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。

制約

  • 1 \leq N, M \leq 50
  • N \leq K \leq NM
  • 入力は全て整数

入力

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

N M K

出力

答えを 998244353 で割った余りを出力せよ。

入力例 1

2 3 4

出力例 1

6

条件を満たす数列は以下の 6 つです。

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

入力例 2

31 41 592

出力例 2

798416518

答えを 998244353 で割った余りを出力してください。

Score : 300 points

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

  • 1\le A_i \le M (1 \le i \le N)

  • \displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

  • 1 \leq N, M \leq 50
  • N \leq K \leq NM
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

6

The following six sequences satisfy the conditions.

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

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.
G - Weak Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

縦 H 行、横 W 行の H \times W マスからなるグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 C_{i, j} で表され、C_{i, j} = . ならばマス (i, j) は空きマスであり、C_{i, j} = # ならばマス (i, j) は壁です。

高橋君がグリッド上を歩こうとしています。彼がマス (i, j) にいるとき、マス (i, j + 1) またはマス (i + 1, j) に移動することができます。ただし、グリッドの外に出るような移動や、壁のマスへの移動を行うことはできません。高橋君は、移動することのできるマスが無くなった時点で立ち止まります。

高橋君がマス (1, 1) から歩き始めるとき、彼が立ち止まるまでに通ることのできるマスは最大で何マスですか？

制約

  • 1 \leq H, W \leq 100
  • H, W は整数
  • C_{i, j} = . または C_{i, j} = # (1 \leq i \leq H, 1 \leq j \leq W)
  • C_{1, 1} = .

入力

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

H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}

出力

答えを出力せよ。

入力例 1

3 4
.#..
..#.
..##

出力例 1

4

例えば (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) と進むことで、4 マス通ることができます。

5 マス以上通ることはできないので、4 と出力します。

入力例 2

1 1
.

出力例 2

1

入力例 3

5 5
.....
.....
.....
.....
.....

出力例 3

9

Score : 400 points

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.

Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.

When starting on (1, 1), at most how many squares can Takahashi visit before he stops?

Constraints

  • 1 \leq H, W \leq 100
  • H and W are integers.
  • C_{i, j} = . or C_{i, j} = #. (1 \leq i \leq H, 1 \leq j \leq W)
  • C_{1, 1} = .

Input

Input is given from Standard Input in the following format:

H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}

Output

Print the answer.

Sample Input 1

3 4
.#..
..#.
..##

Sample Output 1

4

For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.

He cannot visit 5 or more squares, so we should print 4.

Sample Input 2

1 1
.

Sample Output 2

1

Sample Input 3

5 5
.....
.....
.....
.....
.....

Sample Output 3

9
H - LEQ

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

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

A の連続するとは限らない、長さが 2 以上である部分列 A'=(A'_1,A'_2,\ldots,A'_k) のうち以下の条件を満たすものの個数を求めてください。

  • A'_1 \leq A'_k

なお、この値は非常に大きくなることがあるため、998244353 で割ったあまりを出力してください。

ただし、2 つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

A の連続するとは限らない、長さが 2 以上である部分列のうち問題文中の条件を満たすものの個数を、998244353 で割ったあまりを出力せよ。

入力例 1

3
1 2 1

出力例 1

3

A=(1,2,1) の連続するとは限らない、長さが 2 以上である部分列は (1,2), (1,1), (2,1), (1,2,1) の 4 通りあります。

そのうち問題文中の条件を満たすものは、(1,2), (1,1), (1,2,1) の 3 通りです。

入力例 2

3
1 2 2

出力例 2

4

列として同じであっても、取り出す添字が異なる場合 2 つの部分列は区別されることに注意してください。

この入出力例において、問題文中の条件を満たすような部分列は (1,2), (1,2), (2,2), (1,2,2) の 4 通りです。

入力例 3

3
3 2 1

出力例 3

0

問題文中の条件を満たすような部分列が存在しない場合もあります。

入力例 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

出力例 4

830

Score : 500 points

Problem Statement

Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).

Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:

  • A'_1 \leq A'_k.

Since the count can be enormous, print it modulo 998244353.

Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

Constraints

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the condition in Problem Statement.

Sample Input 1

3
1 2 1

Sample Output 1

3

A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).

Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.

Sample Input 2

3
1 2 2

Sample Output 2

4

Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.

Sample Input 3

3
3 2 1

Sample Output 3

0

There may be no subsequence that satisfies the condition.

Sample Input 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

Sample Output 4

830
I - Operations on a Matrix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

縦 N 行、横 M 列の行列があり、はじめ全ての成分は 0 です。

以下のいずれかの形式で表されるクエリを Q 個処理してください。

  • 1 l r x : l 列目、l+1 列目、\ldots、r 列目の成分全てに x を足す。
  • 2 i x : i 行目の成分全てを x で置き換える。
  • 3 i j : (i, j) 成分を出力する。

制約

  • 1 \leq N, M, Q \leq 2 \times 10^5
  • 1 l r x の形式のクエリについて、1 \leq l \leq r \leq M かつ 1 \leq x \leq 10^9
  • 2 i x の形式のクエリについて、1 \leq i \leq N かつ 1 \leq x \leq 10^9
  • 3 i j の形式にクエリについて、1 \leq i \leq N かつ 1 \leq j \leq M
  • 3 i j の形式のクエリが一個以上与えられる
  • 入力は全て整数

入力

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

N M Q
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

i 番目に与えられるクエリを表す \mathrm{Query}_i は以下のいずれかの形式である。

1 l r x

2 i x

3 i j

出力

3 i j の形式の各クエリについて、答えを一行に出力せよ。

入力例 1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

出力例 1

1
2
2
5
3
4

行列は次のように変化します。

\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}

入力例 2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

出力例 2

9000000000

入力例 3

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

出力例 3

6
5
5
13
10
0

Score : 500 points

Problem Statement

We have an N \times M matrix, whose elements are initially all 0.

Process Q given queries. Each query is in one of the following formats.

  • 1 l r x : Add x to every element in the l-th, (l+1)-th, \ldots, and r-th column.
  • 2 i x: Replace every element in the i-th row with x.
  • 3 i j: Print the (i, j)-th element.

Constraints

  • 1 \leq N, M, Q \leq 2 \times 10^5
  • Every query is in one of the formats listed in the Problem Statement.
  • For each query in the format 1 l r x, 1 \leq l \leq r \leq M and 1 \leq x \leq 10^9.
  • For each query in the format 2 i x, 1 \leq i \leq N and 1 \leq x \leq 10^9.
  • For each query in the format 3 i j, 1 \leq i \leq N and 1 \leq j \leq M.
  • At least one query in the format 3 i j is given.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M Q
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

\mathrm{Query}_i, which denotes the i-th query, is in one of the following formats:

1 l r x

2 i x

3 i j

Output

For each query in the format 3 i j, print a single line containing the answer.

Sample Input 1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

Sample Output 1

1
2
2
5
3
4

The matrix transitions as follows.

\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}

Sample Input 2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

Sample Output 2

9000000000

Sample Input 3

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

Sample Output 3

6
5
5
13
10
0