実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
2^n \gt n^2 ですか？
制約
- n は 1 以上 10^9 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
n
出力
2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。
入力例 1
5
出力例 1
Yes
2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。
入力例 2
2
出力例 2
No
n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。
入力例 3
623947744
出力例 3
Yes
Score : 100 points
Problem Statement
Does 2^n \gt n^2 hold?
Constraints
- n is an integer between 1 and 10^9 (inclusive).
Input
Input is given from Standard Input in the following format:
n
Output
If 2^n \gt n^2, print Yes; otherwise, print No.
Sample Input 1
5
Sample Output 1
Yes
Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.
Sample Input 2
2
Sample Output 2
No
For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.
Sample Input 3
623947744
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
上下左右に広がる H 行 W 列のマス目があり、各マスにはコマが置かれているか、何も置かれていないかのどちらかです。
マス目の状態は H 個の長さ W の文字列 S_1, S_2, \ldots, S_H によって表され、
S_i の j 文字目が # のとき上から i 行目かつ左から j 列目のマスにはコマが置かれていることを、
S_i の j 文字目が . のとき上から i 行目かつ左から j 列目のマスには何も置かれていないことを表しています。
マス目上のマスのうち、コマが置かれているようなものの個数を求めてください。
制約
- 1\leq H,W \leq 10
- H,W は整数
- S_i は
#と.のみからなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
コマが置かれているマスの個数を整数で出力せよ。
入力例 1
3 5 #.... ..... .##..
出力例 1
3
- 上から 1 行目かつ左から 1 列目のマス
- 上から 3 行目かつ左から 2 列目のマス
- 上から 3 行目かつ左から 3 列目のマス
の計 3 つのマスにコマが置かれているため、3 を出力します。
入力例 2
1 10 ..........
出力例 2
0
どのマスにもコマは置かれていないため、0 を出力します。
入力例 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
出力例 3
16
Score : 100 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Each square has a piece placed on it or is empty.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W.
If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left has a piece on it;
if the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is empty.
How many squares in the grid have pieces on them?
Constraints
- 1\leq H,W \leq 10
- H and W are integers.
- S_i is a string of length W consisting of
#and..
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Print the number of squares with pieces as an integer.
Sample Input 1
3 5 #.... ..... .##..
Sample Output 1
3
The following three squares have pieces on them:
- the square at the 1-st row from the top and 1-st column from the left;
- the square at the 3-rd row from the top and 2-nd column from the left;
- the square at the 3-rd row from the top and 3-rd column from the left.
Thus, 3 should be printed.
Sample Input 2
1 10 ..........
Sample Output 2
0
Since no square has a piece on it, 0 should be printed.
Sample Input 3
6 5 #.#.# ....# ..##. ####. ..#.. #####
Sample Output 3
16
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S,T が与えられるので、 T が S の(連続する)部分文字列かどうか判定してください。
なお、文字列 X に以下の操作を 0 回以上施して文字列 Y が得られる時、またその時に限り Y は X の(連続する)部分文字列であると言います。
- 以下の 2 つの操作から 1 つを選択して、その操作を行う。
- X の先頭の 1 文字を削除する。
- X の末尾の 1 文字を削除する。
例えば tag は voltage の(連続する)部分文字列ですが、 ace は atcoder の(連続する)部分文字列ではありません。
制約
- S,T は英小文字からなる
- 1 \le |S|,|T| \le 100 ( |X| は文字列 X の長さ )
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
T が S の(連続する)部分文字列なら Yes 、そうでないなら No と出力せよ。
入力例 1
voltage tag
出力例 1
Yes
tag は voltage の(連続する)部分文字列です。
入力例 2
atcoder ace
出力例 2
No
ace は atcoder の(連続する)部分文字列ではありません。
入力例 3
gorilla gorillagorillagorilla
出力例 3
No
入力例 4
toyotasystems toyotasystems
出力例 4
Yes
S=T である場合もあります。
Score : 200 points
Problem Statement
You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.
A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.
- Do one of the following.
- Delete the first character in X.
- Delete the last character in X.
For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.
Constraints
- S and T consist of lowercase English letters.
- 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)
Input
The input is given from Standard Input in the following format:
S T
Output
If T is a (contiguous) substring of S, print Yes; otherwise, print No.
Sample Input 1
voltage tag
Sample Output 1
Yes
tag is a (contiguous) substring of voltage.
Sample Input 2
atcoder ace
Sample Output 2
No
ace is not a (contiguous) substring of atcoder.
Sample Input 3
gorilla gorillagorillagorilla
Sample Output 3
No
Sample Input 4
toyotasystems toyotasystems
Sample Output 4
Yes
It is possible that S=T.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は 2 次元コード TaK Code を考案しました。以下の条件を全て満たすものが TaK Code です。
- 縦 9 マス 横 9 マスの領域である
- 左上及び右下の縦 3 マス 横 3 マスの領域に含まれる計 18 マスは全て黒である
- 左上及び右下の縦 3 マス 横 3 マスの領域に八方位で隣接する計 14 マスは全て白である
TaK Code を回転させることはできません。
縦 N マス、横 M マスのグリッドがあります。
グリッドの状態は N 個の長さ M の文字列 S_1,\ldots,S_N で与えられ、上から i 行目左から j 列目のマスは S_i の j 文字目が # のとき黒、. のとき白です。
グリッドに完全に含まれる縦 9 マス横 9 マスの領域で、TaK Code の条件を満たす箇所を全て求めてください。
制約
- 9 \leq N,M \leq 100
- N,M は整数である
- S_i は
.および#のみからなる長さ M の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
上から i 行目左から j 列目のマスを左上とする縦 9 マス 横 9 マスの領域が TaK Code の条件を満たす (i,j) の組全てを辞書順の昇順で 1 行に 1 組ずつ、i,j をこの順に空白区切りで出力せよ。
(i,j) の組の辞書順の昇順とは、i の昇順、i が等しい組は j の昇順にすることである。
入力例 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
出力例 1
1 1 1 10 7 7 10 2
TaK Code は以下のものです。# が黒マス、. が白マス、? が白黒どちらでもよいマスを表します。
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
入力で与えられたグリッドの上から 10 マス目左から 2 列目のマスを左上とする縦 9 マス 横 9 マスの領域は以下のようになっており、TaK Code の条件を満たします。
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
入力例 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
出力例 2
1 1
入力例 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
出力例 3
TaK Code の条件を満たす箇所が 1 つもないこともあります。
Score : 200 points
Problem Statement
Takahashi invented Tak Code, a two-dimensional code. A TaK Code satisfies all of the following conditions:
- It is a region consisting of nine horizontal rows and nine vertical columns.
- All the 18 cells in the top-left and bottom-right three-by-three regions are black.
- All the 14 cells that are adjacent (horizontally, vertically, or diagonally) to the top-left or bottom-right three-by-three region are white.
It is not allowed to rotate a TaK Code.
You are given a grid with N horizontal rows and M vertical columns.
The state of the grid is described by N strings, S_1,\ldots, and S_N, each of length M. The cell at the i-th row from the top and j-th column from the left is black if the j-th character of S_i is #, and white if it is ..
Find all the nine-by-nine regions, completely contained in the grid, that satisfy the conditions of a TaK Code.
Constraints
- 9 \leq N,M \leq 100
- N and M are integers.
- S_i is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
For all pairs (i,j) such that the nine-by-nine region, whose top-left cell is at the i-th row from the top and j-th columns from the left, satisfies the conditions of a TaK Code, print a line containing i, a space, and j in this order.
The pairs must be sorted in lexicographical ascending order; that is, i must be in ascending order, and within the same i, j must be in ascending order.
Sample Input 1
19 18 ###......###...... ###......###...... ###..#...###..#... ..............#... .................. .................. ......###......### ......###......### ......###......### .###.............. .###......##...... .###.............. ............###... ...##.......###... ...##.......###... .......###........ .......###........ .......###........ ........#.........
Sample Output 1
1 1 1 10 7 7 10 2
A TaK Code looks like the following, where # is a black cell, . is a white cell, and ? can be either black or white.
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
In the grid given by the input, the nine-by-nine region, whose top-left cell is at the 10-th row from the top and 2-nd column from the left, satisfies the conditions of a TaK Code, as shown below.
###...... ###...... ###...... ......... ..##..... ..##..... ......### ......### ......###
Sample Input 2
9 21 ###.#...........#.### ###.#...........#.### ###.#...........#.### ....#...........#.... #########...######### ....#...........#.... ....#.###...###.#.... ....#.###...###.#.... ....#.###...###.#....
Sample Output 2
1 1
Sample Input 3
18 18 ######............ ######............ ######............ ######............ ######............ ######............ .................. .................. .................. .................. .................. .................. ............###### ............###### ............###### ............###### ............###### ............######
Sample Output 3
There may be no region that satisfies the conditions of TaK Code.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
xy 平面上に 1 から N までの番号が付いた N 個の点があります。
点 i は座標 (X_i,Y_i) にあり、相異なる 2 点は異なる位置に存在します。
この N 点から 3 点を選ぶとき、選ばれた 3 点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めてください。
制約
- 入力は全て整数である
- 3 \le N \le 300
- -10^9 \le X_i,Y_i \le 10^9
- i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
出力
答えを整数として出力せよ。
入力例 1
4 0 1 1 3 1 1 -1 -1
出力例 1
3
点を図示すると、以下のようになります。
三角形をなすような点の選び方は、 \{1,2,3\},\{1,3,4\},\{2,3,4\} の 3 つです。
入力例 2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
出力例 2
1124
Score : 300 points
Problem Statement
In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.
Constraints
- All values in input are integers.
- 3 \le N \le 300
- -10^9 \le X_i,Y_i \le 10^9
- (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.
Input
Input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
Output
Print the answer as an integer.
Sample Input 1
4 0 1 1 3 1 1 -1 -1
Sample Output 1
3
The figure below illustrates the points.
There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.
Sample Input 2
20 224 433 987654321 987654321 2 0 6 4 314159265 358979323 0 0 -123456789 123456789 -1000000000 1000000000 124 233 9 -6 -4 0 9 5 -7 3 333333333 -333333333 -9 -1 7 -10 -1 5 324 633 1000000000 -1000000000 20 0
Sample Output 2
1124
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
1 以上 N 以下の整数からなる集合が M 個あり、順に S_1, S_2, \dots, S_M と呼びます。
S_i は C_i 個の整数 a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i} からなります。
M 個の集合から 1 個以上の集合を選ぶ方法は 2^M-1 通りあります。
このうち、次の条件を満たす選び方は何通りありますか？
- 1 \leq x \leq N を満たす全ての整数 x に対して、選んだ集合の中に x を含む集合が少なくとも 1 個存在する。
制約
- 1 \leq N \leq 10
- 1 \leq M \leq 10
- 1 \leq C_i \leq N
- 1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
C_1
a_{1,1} a_{1,2} \dots a_{1,C_1}
C_2
a_{2,1} a_{2,2} \dots a_{2,C_2}
\vdots
C_M
a_{M,1} a_{M,2} \dots a_{M,C_M}
出力
問題文の条件を満たす集合の選び方の数を出力せよ。
入力例 1
3 3 2 1 2 2 1 3 1 2
出力例 1
3
入力で与えられている集合はそれぞれ S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace です。
問題文の条件を満たす集合の選び方は次の 3 通りです。
- S_1, S_2 を選ぶ。
- S_1, S_2, S_3 を選ぶ。
- S_2, S_3 を選ぶ。
入力例 2
4 2 2 1 2 2 1 3
出力例 2
0
問題文の条件を満たす選び方が存在しない場合もあります。
入力例 3
6 6 3 2 3 6 3 2 4 6 2 3 6 3 1 5 6 3 1 3 6 2 1 4
出力例 3
18
Score : 300 points
Problem Statement
There are M sets, called S_1, S_2, \dots, S_M, consisting of integers between 1 and N.
S_i consists of C_i integers a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}.
There are (2^M-1) ways to choose one or more sets from the M sets.
How many of them satisfy the following condition?
- For all integers x such that 1 \leq x \leq N, there is at least one chosen set containing x.
Constraints
- 1 \leq N \leq 10
- 1 \leq M \leq 10
- 1 \leq C_i \leq N
- 1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
C_1
a_{1,1} a_{1,2} \dots a_{1,C_1}
C_2
a_{2,1} a_{2,2} \dots a_{2,C_2}
\vdots
C_M
a_{M,1} a_{M,2} \dots a_{M,C_M}
Output
Print the number of ways to choose sets that satisfy the conditions in the Problem Statement.
Sample Input 1
3 3 2 1 2 2 1 3 1 2
Sample Output 1
3
The sets given in the input are S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace.
The following three ways satisfy the conditions in the Problem Statement:
- choosing S_1, S_2;
- choosing S_1, S_2, S_3;
- choosing S_2, S_3.
Sample Input 2
4 2 2 1 2 2 1 3
Sample Output 2
0
There may be no way to choose sets that satisfies the conditions in the Problem Statement.
Sample Input 3
6 6 3 2 3 6 3 2 4 6 2 3 6 3 1 5 6 3 1 3 6 2 1 4
Sample Output 3
18
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
1, 2, \ldots, N の番号のついた N 人の候補者から当選者を 1 人選ぶ選挙において、M 票の投票がありました。
各票ではそれぞれちょうど 1 人が投票先として選ばれており、i 票目の投票先は候補者 A_i です。
これから 1 票目から順に開票を行い、 1 票ごとにその時点で開票が終了した場合の当選者を更新して表示します。
開票された票において最も得票数が多かった候補者が当選となります。ただし、最も得票数が多かった候補者が複数いる場合は、その中で最も番号の小さい候補者が当選となります。
各 i = 1, 2, \ldots, M について、1, 2, \ldots, i 票目のみを開票した場合の当選者を求めてください。
制約
- 1 \leq N,M \leq 200000
- 1 \leq A_i \leq N
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_M
出力
M 行出力せよ。
i 行目には 1, 2, \ldots, i 票目のみを開票した場合の当選者の番号を出力せよ。
入力例 1
3 7 1 2 2 3 1 3 3
出力例 1
1 1 2 2 1 1 3
候補者 i の得票数を C_i で表すこととします。
- 1 票目までが開票された時点では、(C_1, C_2, C_3) = (1, 0, 0) なので当選者は 1 です。
- 2 票目までが開票された時点では、(C_1, C_2, C_3) = (1, 1, 0) なので当選者は 1 です。
- 3 票目までが開票された時点では、(C_1, C_2, C_3) = (1, 2, 0) なので当選者は 2 です。
- 4 票目までが開票された時点では、(C_1, C_2, C_3) = (1, 2, 1) なので当選者は 2 です。
- 5 票目までが開票された時点では、(C_1, C_2, C_3) = (2, 2, 1) なので当選者は 1 です。
- 6 票目までが開票された時点では、(C_1, C_2, C_3) = (2, 2, 2) なので当選者は 1 です。
- 7 票目までが開票された時点では、(C_1, C_2, C_3) = (2, 2, 3) なので当選者は 3 です。
入力例 2
100 5 100 90 80 70 60
出力例 2
100 90 80 70 60
入力例 3
9 8 8 8 2 2 8 8 2 2
出力例 3
8 8 8 2 8 8 8 2
Score : 350 points
Problem Statement
There is an election to choose one winner from N candidates with candidate numbers 1, 2, \ldots, N, and there have been M votes cast.
Each vote is for exactly one candidate, with the i-th vote being for candidate A_i.
The votes will be counted in order from first to last, and after each vote is counted, the current winner will be updated and displayed.
The candidate with the most votes among those counted is the winner. If there are multiple candidates with the most votes, the one with the smallest candidate number is the winner.
For each i = 1, 2, \ldots, M, determine the winner when counting only the first i votes.
Constraints
- 1 \leq N, M \leq 200000
- 1 \leq A_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_M
Output
Print M lines.
The i-th line should contain the winner's candidate number when counting only the first i votes.
Sample Input 1
3 7 1 2 2 3 1 3 3
Sample Output 1
1 1 2 2 1 1 3
Let C_i denote the number of votes for candidate i.
- After the first vote is counted, (C_1, C_2, C_3) = (1, 0, 0), so the winner is 1.
- After the second vote is counted, (C_1, C_2, C_3) = (1, 1, 0), so the winner is 1.
- After the third vote is counted, (C_1, C_2, C_3) = (1, 2, 0), so the winner is 2.
- After the fourth vote is counted, (C_1, C_2, C_3) = (1, 2, 1), so the winner is 2.
- After the fifth vote is counted, (C_1, C_2, C_3) = (2, 2, 1), so the winner is 1.
- After the sixth vote is counted, (C_1, C_2, C_3) = (2, 2, 2), so the winner is 1.
- After the seventh vote is counted, (C_1, C_2, C_3) = (2, 2, 3), so the winner is 3.
Sample Input 2
100 5 100 90 80 70 60
Sample Output 2
100 90 80 70 60
Sample Input 3
9 8 8 8 2 2 8 8 2 2
Sample Output 3
8 8 8 2 8 8 8 2
実行時間制限: 3.5 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 頂点 M 辺の単純無向グラフがあり、各頂点には 1,\ldots,N と番号が付けられています。 i=1,\ldots,M に対し、 i 番目の辺は頂点 a_i と頂点 b_i を結びます。また、各頂点の次数は 3 以下です。
i=1,\ldots,Q に対し、次のクエリに答えてください。
- 頂点 x_i との距離が k_i 以下であるような頂点の番号の総和を求めよ。
制約
- 1 \leq N \leq 1.5 \times 10^5
- 0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})
- 1 \leq a_i \lt b_i \leq N
- i\neq j ならば (a_i,b_i) \neq (a_j,b_j)
- 与えられるグラフの各頂点の次数は 3 以下
- 1 \leq Q \leq 1.5 \times 10^5
- 1 \leq x_i \leq N
- 0 \leq k_i \leq 3
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 \vdots a_M b_M Q x_1 k_1 \vdots x_Q k_Q
出力
Q 行出力せよ。 i 行目には i 番目のクエリへの答えを出力せよ。
入力例 1
6 5 2 3 3 4 3 5 5 6 2 6 7 1 1 2 2 2 0 2 3 4 1 6 0 4 3
出力例 1
1 20 2 20 7 6 20
1 番目のクエリでは、頂点 1 との距離が 1 以下であるような頂点は頂点 1 のみなので 1 が答えです。
2 番目のクエリでは、頂点 2 との距離が 2 以下であるような頂点は頂点 2,3,4,5,6 なのでこれらの総和の 20 が答えになります。
3 番目以降のクエリも同様にして答えを求められます。
Score : 500 points
Problem Statement
We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1,\ldots,N. For each i=1,\ldots,M, the i-th edge connects Vertex a_i and Vertex b_i. Additionally, the degree of each vertex is at most 3.
For each i=1,\ldots,Q, answer the following query.
- Find the sum of indices of vertices whose distances from Vertex x_i are at most k_i.
Constraints
- 1 \leq N \leq 1.5 \times 10^5
- 0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})
- 1 \leq a_i \lt b_i \leq N
- (a_i,b_i) \neq (a_j,b_j), if i\neq j.
- The degree of each vertex in the graph is at most 3.
- 1 \leq Q \leq 1.5 \times 10^5
- 1 \leq x_i \leq N
- 0 \leq k_i \leq 3
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 \vdots a_M b_M Q x_1 k_1 \vdots x_Q k_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
6 5 2 3 3 4 3 5 5 6 2 6 7 1 1 2 2 2 0 2 3 4 1 6 0 4 3
Sample Output 1
1 20 2 20 7 6 20
For the 1-st query, the only vertex whose distance from Vertex 1 is at most 1 is Vertex 1, so the answer is 1.
For the 2-nd query, the vertices whose distances from Vertex 2 are at most 2 are Vertex 2, 3, 4, 5, and 6, so the answer is their sum, 20.
The 3-rd and subsequent queries can be answered similarly.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
高橋君と青木君は、これから N 日間アルバイトをします。
高橋君のシフト表は文字列 S により与えられ、S の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤します。
これをもとに、青木君は以下のようにシフト表を作りました。
- まず、N でない N の正の約数 M をとる。
- 次に、1 日目から M 日目までの勤怠を決める。
- 最後に、i = 1, 2, \ldots, N - M の順に M + i 日目の勤怠が i 日目の勤怠と一致するように M + i 日目の勤怠を決める。
ここで、M の値が異なる場合でも最終的にできたシフトが同じものとなることがあることに注意してください。
N 日すべてについて高橋君と青木君の少なくとも一方が出勤することになったとき、青木君のシフト表として考えられるものの個数を 998244353 で割った余りを求めてください。
制約
- N は 2 以上 10^5 以下の整数
- S は 長さ N の
#、.からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
6 ##.#.#
出力例 1
3
高橋君は 1 \cdot 2 \cdot 4 \cdot 6 日目に出勤します。
青木君のシフト表を表す文字列を T とし、青木君は T の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤するとします。
T としてあり得るものは ###### \cdot #.#.#. \cdot .##.## の 3 つです。
1 つめのシフト表は M を 1 または 2 または 3、2 つめのシフト表は M = 2、3 つめのシフト表は M = 3 とすることにより実現できます。
入力例 2
7 ...####
出力例 2
1
入力例 3
12 ####.####.##
出力例 3
19
Score : 525 points
Problem Statement
Takahashi and Aoki will work part-time for the next N days.
Takahashi's shift schedule is given by the string S, where the i-th character of S is # if he works on the i-th day, and . if he is absent on the i-th day.
Based on this, Aoki created his shift schedule as follows.
- First, take a positive divisor M of N that is not equal to N.
- Next, decide the attendance for the first M days.
- Finally, for i = 1, 2, \ldots, N - M in this order, decide the attendance for the (M + i)-th day so that it matches the attendance for the i-th day.
Note that different values of M may lead to the same final shift schedule.
Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the N days, modulo 998244353.
Constraints
- N is an integer between 2 and 10^5, inclusive.
- S is a string of length N consisting of
#and..
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
6 ##.#.#
Sample Output 1
3
Takahashi works on days 1, 2, 4, and 6.
Let T be the string representing Aoki's shift schedule, where the i-th character of T is # if he works on the i-th day, and . if he is absent on the i-th day.
There are three possible strings for T: ######, #.#.#., and .##.##.
The first shift schedule can be realized by choosing M = 1 or 2 or 3, the second by choosing M = 2, and the third by choosing M = 3.
Sample Input 2
7 ...####
Sample Output 2
1
Sample Input 3
12 ####.####.##
Sample Output 3
19