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
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
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.
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
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 通りあります。
ABAAABAABAABBAABBAABAABBABBA
このうち、最初の 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:
ABAAABAABAABBAABBAABAABBABBA
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