C - Maintain Multiple Sequences

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数からなる数列が N 個あります。
i \, (1 \leq i \leq N) 番目の数列は L_i 項からなり、i 番目の数列の第 j \, (1 \leq j \leq L_i) 項 は a_{i, j} です。

Q 個のクエリが与えられます。k \, (1 \leq k \leq Q) 番目のクエリでは、整数 s_k, t_k が与えられるので、s_k 番目の数列の第 t_k 項を求めてください。

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • L_i \geq 1 \, (1 \leq i \leq N)
  • \sum_{i=1}^N L_i \leq 2 \times 10^5
  • 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
  • 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
  • 入力は全て整数

入力

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

出力

Q 行出力せよ。k \, (1 \leq k \leq Q) 行目には、k 番目のクエリに対する答えを出力せよ。


入力例 1

2 2
3 1 4 7
2 5 9
1 3
2 1

出力例 1

7
5

1 番目の数列は (1, 4, 7)、2 番目の数列は (5, 9) です。
それぞれのクエリに対する答えは次のようになります。

  • 1 番目の数列の第 3 項は 7 です。
  • 2 番目の数列の第 1 項は 5 です。

入力例 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

出力例 2

128
1
26535
901

Score : 200 points

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • L_i \geq 1 \, (1 \leq i \leq N)
  • \sum_{i=1}^N L_i \leq 2 \times 10^5
  • 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
  • 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
  • All values in the input are integers.

Input

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

N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots 
s_Q t_Q

Output

Print Q lines. The k-th (1 \leq k \leq Q) line should contain the answer to the k-th query.


Sample Input 1

2 2
3 1 4 7
2 5 9
1 3
2 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

  • The 3-rd term of the 1-st sequence is 7.
  • The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

128
1
26535
901
D - Practical Computing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

以下のような N 個の整数列 A_0,\ldots,A_{N-1} を求めてください。

  • 各 i (0\leq i \leq N-1) について、A_i の長さは i+1 である。
  • 各 i,j (0\leq i \leq N-1, 0 \leq j \leq i) について、A_i の j+1 番目の値 a_{i,j} は次のように定められる。

    • j=0 または j=i の時、a_{i,j}=1
    • それ以外の時、a_{i,j} = a_{i-1,j-1} + a_{i-1,j}

制約

  • 1 \leq N \leq 30
  • N は整数

入力

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

N

出力

N 行出力せよ。 i 行目には A_{i-1} の値を順に空白区切りで出力せよ。


入力例 1

3

出力例 1

1
1 1
1 2 1

入力例 2

10

出力例 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Score : 200 points

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

  • For each i (0\leq i \leq N-1), the length of A_i is i+1.
  • For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
    • a_{i,j}=1, if j=0 or j=i.
    • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

  • 1 \leq N \leq 30
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain the terms of A_{i-1} separated by spaces.


Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
E - Matrix Reducing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

H_1 行 W_1 列の行列 A と、H_2 行 W_2 列の行列 B が与えられます。

  • 1 \leq i \leq H_1 かつ 1 \leq j \leq W_1 を満たす整数の組 (i, j) について、行列 A の i 行目 j 列目の要素は A_{i, j} です。
  • 1 \leq i \leq H_2 かつ 1 \leq j \leq W_2 を満たす整数の組 (i, j) について、行列 B の i 行目 j 列目の要素は B_{i, j} です。

行列 A に対して、下記の 2 つの操作のうちどちらかを行うことを、好きなだけ( 0 回でも良い)繰り返すことができます。

  • A の行を任意に 1 つ選んで削除する。
  • A の列を任意に 1 つ選んで削除する。

行列 A を行列 B に一致させることができるかどうかを判定して下さい。

制約

  • 1 \leq H_2 \leq H_1 \leq 10
  • 1 \leq W_2 \leq W_1 \leq 10
  • 1 \leq A_{i, j} \leq 10^9
  • 1 \leq B_{i, j} \leq 10^9
  • 入力中の値はすべて整数

入力

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

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

出力

行列 A を行列 B に一致させることができる場合は Yes を、 一致させることができない場合は No を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。


入力例 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

出力例 1

Yes

初期状態の行列 A から 2 列目を削除すると、行列 A は

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

となります。そこからさらに 3 行目を削除すると、行列 A は

1 3 4 5
6 8 9 10
16 18 19 20

となります。そこからさらに 1 行目を削除すると、行列 A は

6 8 9 10
16 18 19 20

となります。そこからさらに 4 列目を削除すると、行列 A は

6 8 9
16 18 19

となります。これは行列 B と一致します。 操作の繰り返しによって行列 A を行列 B に一致させることができるので Yes を出力します。


入力例 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

出力例 2

No

どのように操作を行っても、 行列 A を行列 B に一致させることはできません。 よって、No を出力します。

Score : 300 points

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

  • For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
  • For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

  • Choose an arbitrary row of A and remove it.
  • Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

  • 1 \leq H_2 \leq H_1 \leq 10
  • 1 \leq W_2 \leq W_1 \leq 10
  • 1 \leq A_{i, j} \leq 10^9
  • 1 \leq B_{i, j} \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

Output

Print Yes if it is possible to make the matrix A equal the matrix B; print No otherwise. Note that the judge is case-sensitive.


Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.


Sample Input 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

F - Equilateral Triangle

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

円周が L の円があり、この円周上に点 1,2,\ldots,N が配置されています。i=1,2,\ldots,N-1 に対し、点 i+1 は点 i から時計回りに円周上を d_i 進んだ位置にあります。

整数の組 (a,b,c)\ (1\leq a\lt b\lt c\leq N) であって、以下の 2 つをともに満たすものの個数を求めてください。

  • 3 点 a,b,c はすべて異なる位置にある。
  • 3 点 a,b,c を頂点とする三角形は正三角形である。

制約

  • 3\leq L,N\leq 3\times 10^5
  • 0\leq d_i\lt L
  • 入力は全て整数

入力

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

N L
d_1 d_2 \ldots d_{N-1}

出力

答えを出力せよ。


入力例 1

5 6
4 3 1 2

出力例 1

2

5 つの点の配置は以下のようになります。条件を満たすのは (a,b,c)=(1,2,4),(1,4,5) の 2 つです。


入力例 2

4 4
1 1 1

出力例 2

0

入力例 3

10 12
4 4 5 7 1 7 0 8 5

出力例 3

13

Score : 300 points

Problem Statement

There is a circle with circumference L, and points 1,2,\ldots,N are placed on this circle. For i=1,2,\ldots,N-1, point i+1 is located at a position that is d_i clockwise from point i on the circle.

Find the number of integer triples (a,b,c)\ (1\leq a\lt b\lt c\leq N) that satisfy both of the following conditions:

  • The three points a, b, and c are all at different positions.
  • The triangle with vertices at the three points a, b, and c is an equilateral triangle.

Constraints

  • 3\leq L,N\leq 3\times 10^5
  • 0\leq d_i\lt L
  • All input values are integers.

Input

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

N L
d_1 d_2 \ldots d_{N-1}

Output

Output the answer.


Sample Input 1

5 6
4 3 1 2

Sample Output 1

2

The arrangement of the five points is as follows. Two pairs satisfy the conditions: (a,b,c)=(1,2,4),(1,4,5).


Sample Input 2

4 4
1 1 1

Sample Output 2

0

Sample Input 3

10 12
4 4 5 7 1 7 0 8 5

Sample Output 3

13
G - Avoid K Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

A, B, ? からなる N 文字の文字列 S が与えられます。

正整数 K が与えられます。 A, B からなる文字列 T が次の条件を満たすとき、T は良い文字列であるということにします。

  • T の長さ K の連続する部分文字列で、回文であるものが存在しない。

S に含まれる ? の個数を q 個とします。 q 個の ? をそれぞれ A, B のどちらかに置き換えて得られる文字列は 2 ^ q 通りありますが、その中に良い文字列がいくつあるか求めてください。

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

制約

  • 2\leq K\leq N\leq 1000
  • K\leq 10
  • S は A, B, ? からなる文字列
  • S の長さは N
  • N,K は整数

入力

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

N K
S

出力

答えを出力せよ。


入力例 1

7 4
AB?A?BA

出力例 1

1

与えられた文字列の中に ? は 2 個あります。 2 個の ? をそれぞれ A, B のどちらかに置き換えて得られる文字列は次の 4 通りあります。

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

このうち、最初の ABAAABA 以外の 3 つの文字列は、長さ 4 の回文 ABBA を連続する部分文字列として含むため、良い文字列ではありません。

よって、1 を出力してください。


入力例 2

40 7
????????????????????????????????????????

出力例 2

116295436

良い文字列の個数を 998244353 で割った余りを求めることに注意してください。


入力例 3

15 5
ABABA??????????

出力例 3

0

? をどのように置き換えても良い文字列にならないこともあります。


入力例 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

出力例 4

259240

Score : 450 points

Problem Statement

You are given a string S of length N consisting of characters A, B, and ?.

You are also given a positive integer K. A string T consisting of A and B is considered a good string if it satisfies the following condition:

  • No contiguous substring of length K in T is a palindrome.

Let q be the number of ? characters in S. There are 2^q strings that can be obtained by replacing each ? in S with either A or B. Find how many of these strings are good strings.

The count can be very large, so find it modulo 998244353.

Constraints

  • 2 \leq K \leq N \leq 1000
  • K \leq 10
  • S is a string consisting of A, B, and ?.
  • The length of S is N.
  • N and K are integers.

Input

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

N K
S

Output

Print the answer.


Sample Input 1

7 4
AB?A?BA

Sample Output 1

1

The given string has two ?s. There are four strings obtained by replacing each ? with A or B:

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

Among these, the last three contain the contiguous substring ABBA of length 4, which is a palindrome, and thus are not good strings.

Therefore, you should print 1.


Sample Input 2

40 7
????????????????????????????????????????

Sample Output 2

116295436

Ensure to find the number of good strings modulo 998244353.


Sample Input 3

15 5
ABABA??????????

Sample Output 3

0

It is possible that there is no way to replace the ?s to obtain a good string.


Sample Input 4

40 8
?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA

Sample Output 4

259240