Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
AtCoder 国の暦では、1 年は 1 月から M 月までの M ヶ月からなり、どの月も 1 日から D 日までの D 日からなります。
AtCoder 国の暦で y 年 m 月 d 日の翌日は何年何月何日であるか求めてください。
制約
- 1000 \leq y \leq 9000
- 1 \leq m \leq M \leq 99
- 1 \leq d \leq D \leq 99
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
M D y m d
出力
AtCoder 国の暦で y 年 m 月 d 日の翌日が y' 年 m' 月 d' 日であるとき、y',m',d' をこの順に空白区切りで出力せよ。
入力例 1
12 30 2023 12 30
出力例 1
2024 1 1
AtCoder 国の暦では 1 年は 12 ヶ月であり、どの月も 30 日からなります。 よって、2023 年 12 月 30 日の翌日は 2024 年 1 月 1 日になります。
入力例 2
36 72 6789 23 45
出力例 2
6789 23 46
AtCoder 国の暦では 1 年は 36 ヶ月であり、どの月も 72 日からなります。 よって、6789 年 23 月 45 日の翌日は 6789 年 23 月 46 日になります。
入力例 3
12 30 2012 6 20
出力例 3
2012 6 21
Score : 100 points
Problem Statement
In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.
What day follows year y, month m, day d in this calendar?
Constraints
- 1000 \leq y \leq 9000
- 1 \leq m \leq M \leq 99
- 1 \leq d \leq D \leq 99
- All input values are integers.
Input
The input is given from Standard Input in the following format:
M D y m d
Output
If the day following year y, month m, day d in the calendar of AtCoder Kingdom is year y', month m', day d', print y', m', and d' in this order, separated by spaces.
Sample Input 1
12 30 2023 12 30
Sample Output 1
2024 1 1
In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.
Sample Input 2
36 72 6789 23 45
Sample Output 2
6789 23 46
In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.
Sample Input 3
12 30 2012 6 20
Sample Output 3
2012 6 21
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
ナオヒロ君はモンスターを飼っています。モンスターの現在の体力は H です。
また、ナオヒロ君は N 種類の傷薬を持っています。傷薬は効き目の弱い順に 1 から N までの番号がついています。
傷薬 n をモンスターに与えると、モンスターの体力が P_n 増加します。ここで、P_1 \lt P_2 \lt \dots \lt P_N が成り立ちます。
ナオヒロ君は傷薬を 1 つモンスターに与えることで、モンスターの体力を X 以上にしたいです。
目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力してください。(制約下においてそのような傷薬が存在することが保証されています。)
制約
- 2 \leq N \leq 100
- 1 \leq H \lt X \leq 999
- 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N H X P_1 P_2 \dots P_N
出力
目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力せよ。
入力例 1
3 100 200 50 200 999
出力例 1
2
それぞれの傷薬をモンスターに 1 つ与えたときのモンスターの体力の変化は以下の通りです。
- 傷薬 1 をモンスターに与えるとモンスターの体力は 100 + 50 = 150 になります。
- 傷薬 2 をモンスターに与えるとモンスターの体力は 100 + 200 = 300 になります。
- 傷薬 3 をモンスターに与えるとモンスターの体力は 100 + 999 = 1099 になります。
与えた後に体力が X = 200 以上になっている傷薬は、傷薬 2 と傷薬 3 です。このうち最も効き目の弱い傷薬である傷薬 2 が答えになります。
入力例 2
2 10 21 10 999
出力例 2
2
入力例 3
10 500 999 38 420 490 585 613 614 760 926 945 999
出力例 3
4
Score : 100 points
Problem Statement
Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.
He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)
Constraints
- 2 \leq N \leq 100
- 1 \leq H \lt X \leq 999
- 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H X P_1 P_2 \dots P_N
Output
Print the number of the least effective potion that can achieve the purpose.
Sample Input 1
3 100 200 50 200 999
Sample Output 1
2
Below is the change in the monster's health when one of the potions is given to the monster.
- If potion 1 is given, the monster's health becomes 100 + 50 = 150.
- If potion 2 is given, the monster's health becomes 100 + 200 = 300.
- If potion 3 is given, the monster's health becomes 100 + 999 = 1099.
The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.
Sample Input 2
2 10 21 10 999
Sample Output 2
2
Sample Input 3
10 500 999 38 420 490 585 613 614 760 926 945 999
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
各要素が 0 あるいは 1 である N 行 N 列の行列 A, B が与えられます。
A の i 行目 j 列目の要素を A_{i,j}、B の i 行目 j 列目の要素を B_{i,j} で表します。
A を適切に回転することで、 A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできるか判定してください。
ただし、A を回転するとは、以下の操作を好きな回数(0 回でもよい)繰り返すことをいいます。
- 1 \leq i, j \leq N を満たすすべての整数の組 (i, j) について同時に A_{i,j} を A_{N + 1 - j,i} で置き換える
制約
- 1 \leq N \leq 100
- A, B の各要素は 0 か 1 のいずれか
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
出力
A を適切に回転することで、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできる場合 Yes を、そうでない場合 No を出力せよ。
入力例 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
出力例 1
Yes
はじめ、A は
0 1 1 1 0 0 0 1 0
です。
1 回操作を行うと、A は
0 1 0 1 0 1 0 0 1
となります。
もう 1 度操作を行うと、A は
0 1 0 0 0 1 1 1 0
となります。
このとき、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているので、Yes を出力します。
入力例 2
2 0 0 0 0 1 1 1 1
出力例 2
Yes
入力例 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
出力例 3
No
Score : 200 points
Problem Statement
You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:
- for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.
Constraints
- 1 \leq N \leq 100
- Each element of A and B is 0 or 1.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} \ldots A_{1,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
B_{1,1} B_{1,2} \ldots B_{1,N}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,N}
Output
If it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, print Yes; otherwise, print No.
Sample Input 1
3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1
Sample Output 1
Yes
Initially, A is :
0 1 1 1 0 0 0 1 0
After performing the operation once, A is :
0 1 0 1 0 1 0 0 1
After performing the operation once again, A is :
0 1 0 0 0 1 1 1 0
Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.
Sample Input 2
2 0 0 0 0 1 1 1 1
Sample Output 2
Yes
Sample Input 3
5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S が与えられます。S に最も多く出現する文字を求めてください。そのような文字が複数ある場合は、そのうちアルファベット順で最も早いものを答えてください。
制約
- 1 \leq |S| \leq 1000(|S| は文字列 S の長さ)
- S の各文字は英小文字である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に最も多く出現する文字のうちアルファベット順で最も早いものを出力せよ。
入力例 1
frequency
出力例 1
e
frequency には e が 2 回出現し、これは他のどの文字よりも多いため e を出力します。
入力例 2
atcoder
出力例 2
a
atcoder には a, t, c, o, d, e, r が 1 回ずつ出現するため、このうちアルファベット順で最も早い a を出力します。
入力例 3
pseudopseudohypoparathyroidism
出力例 3
o
Score: 200 points
Problem Statement
You are given a string S consisting of lowercase English letters. Find the character that appears most frequently in S. If multiple such characters exist, report the one that comes earliest in alphabetical order.
Constraints
- 1 \leq |S| \leq 1000 (|S| is the length of the string S.)
- Each character in S is a lowercase English letter.
Input
The input is given from Standard Input in the following format:
S
Output
Among the characters that appear most frequently in S, print the one that comes earliest in alphabetical order.
Sample Input 1
frequency
Sample Output 1
e
In frequency, the letter e appears twice, which is more than any other character, so you should print e.
Sample Input 2
atcoder
Sample Output 2
a
In atcoder, each of the letters a, t, c, o, d, e, and r appears once, so you should print the earliest in alphabetical order, which is a.
Sample Input 3
pseudopseudohypoparathyroidism
Sample Output 3
o
Time Limit: 2 sec / Memory Limit: 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
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。 S の各文字は色 1 、色 2 、\ldots 、色 M の M 色のうちのいずれかで塗られており、 i = 1, 2, \ldots, N について、S の i 文字目は色 C_i で塗られています。
各 i = 1, 2, \ldots, M について、この順番に下記の操作を行います。
- S の色 i で塗られた文字からなる部分を、右に 1 つ巡回シフトする。 すなわち、S の 色 i で塗られた文字の位置が先頭のものから順に p_1, p_2, p_3, \ldots, p_k 文字目であるとき、 S の p_1, p_2, p_3, \ldots, p_k 文字目を、それぞれ、S の p_k, p_1,p_2, \ldots, p_{k-1} 文字目で同時に置き換える。
上記の操作をすべて行った後の、最終的な S を出力してください。
なお、M 色あるどの色についても、その色で塗られた S の文字が必ず 1 つ以上存在することが、制約として保証されます。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq M
- N, M, C_i はすべて整数
- S は英小文字からなる長さ N の文字列
- 任意の整数 1 \leq i \leq M に対して、ある整数 1 \leq j \leq N が存在して C_j = i が成り立つ
入力
入力は以下の形式で標準入力から与えられる。
N M S C_1 C_2 \ldots C_N
出力
答えを出力せよ。
入力例 1
8 3 apzbqrcs 1 2 3 1 2 2 1 2
出力例 1
cszapqbr
はじめ、S = apzbqrcs です。
- i = 1 に対する操作では、S の 1, 4, 7 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cpzaqrbsとなります。 - i = 2 に対する操作では、S の 2, 5, 6, 8 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cszapqbrとなります。 - i = 3 に対する操作では、S の 3 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cszapqbrとなります(操作の前後で S は変わりません)。
よって、最終的な S である cszapqbr を出力します。
入力例 2
2 1 aa 1 1
出力例 2
aa
Score : 300 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.
For each i = 1, 2, \ldots, M in this order, let us perform the following operation.
- Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.
Print the final S after the above operations.
The constraints guarantee that at least one character of S is painted in each of the M colors.
Constraints
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq M
- N, M, and C_i are all integers.
- S is a string of length N consisting of lowercase English letters.
- For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.
Input
The input is given from Standard Input in the following format:
N M S C_1 C_2 \ldots C_N
Output
Print the answer.
Sample Input 1
8 3 apzbqrcs 1 2 3 1 2 2 1 2
Sample Output 1
cszapqbr
Initially, S = apzbqrcs.
- For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S =
cpzaqrbs. - For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S =
cszapqbr. - For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S =
cszapqbr(here, S is not changed).
Thus, you should print cszapqbr, the final S.
Sample Input 2
2 1 aa 1 1
Sample Output 2
aa
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N 人のスポーツ選手がいます。
N 人の選手たちには互いに相性の悪い選手のペアが M 組あり、相性の悪い組のうち i\ (1\leq i\leq M) 組目は A _ i 番目の選手と B _ i 番目の選手です。
あなたは、選手を T チームに分けます。 どの選手もちょうど一つのチームに属さなければならず、どのチームにも少なくとも一人の選手が属さなければなりません。 さらに、どの i=1,2,\ldots,M についても、 A _ i 番目の選手と B _ i 番目の選手が同じチームに属していてはいけません。
この条件を満たすチーム分けの方法は何通りあるか求めてください。 ただし、チーム分けの方法が異なるとは、ある二人が存在して、彼らが一方のチーム分けでは同じチームに所属し、もう一方では異なるチームに所属することをいいます。
制約
- 1\leq T\leq N\leq10
- 0\leq M\leq\dfrac{N(N-1)}2
- 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
- (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N T M A _ 1 B _ 1 A _ 2 B _ 2 \vdots A _ M B _ M
出力
答えを 1 行で出力せよ。
入力例 1
5 2 2 1 3 3 4
出力例 1
4
次の 4 通りのチーム分けが条件を満たします。

他に条件を満たすチーム分けは存在しないので、4 を出力してください。
入力例 2
5 1 2 1 3 3 4
出力例 2
0
条件を満たすチーム分けがひとつも存在しないこともあります。
入力例 3
6 4 0
出力例 3
65
相性の悪いペアがひとつも存在しないこともあります。
入力例 4
10 6 8 5 9 1 4 3 8 1 6 4 10 5 7 5 6 3 7
出力例 4
8001
Score : 400 points
Problem Statement
There are N sports players.
Among them, there are M incompatible pairs. The i-th incompatible pair (1\leq i\leq M) is the A_i-th and B_i-th players.
You will divide the players into T teams. Every player must belong to exactly one team, and every team must have one or more players. Additionally, for each i=1,2,\ldots,M, the A_i-th and B_i-th players must not belong to the same team.
Find the number of ways to satisfy these conditions. Here, two divisions are considered different when there are two players who belong to the same team in one division and different teams in the other.
Constraints
- 1\leq T\leq N\leq10
- 0\leq M\leq\dfrac{N(N-1)}2
- 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
- (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T M A _ 1 B _ 1 A _ 2 B _ 2 \vdots A _ M B _ M
Output
Print the answer in a single line.
Sample Input 1
5 2 2 1 3 3 4
Sample Output 1
4
The following four divisions satisfy the conditions.

No other division satisfies them, so print 4.
Sample Input 2
5 1 2 1 3 3 4
Sample Output 2
0
There may be no division that satisfies the conditions.
Sample Input 3
6 4 0
Sample Output 3
65
There may be no incompatible pair.
Sample Input 4
10 6 8 5 9 1 4 3 8 1 6 4 10 5 7 5 6 3 7
Sample Output 4
8001
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。また、各頂点の次数は 10 以下です。
頂点 1 を始点とする単純パス(同じ頂点を複数回通らないパス)の個数を K とします。\min(K, 10^6) を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)
- 1 \leq u_i, v_i \leq N
- 入力で与えられるグラフは単純グラフ
- 入力で与えられるグラフの頂点の次数はすべて 10 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
答えを出力せよ。
入力例 1
4 2 1 2 2 3
出力例 1
3
条件を満たすパスは次の 3 個です。(長さが 0 のパスも数えるのに注意してください。)
- 頂点 1
- 頂点 1, 頂点 2
- 頂点 1, 頂点 2, 頂点 3
入力例 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 2
16
入力例 3
8 21 2 6 1 3 5 6 3 8 3 6 4 7 4 6 3 4 1 5 2 4 1 2 2 7 1 4 3 5 2 5 2 3 4 5 3 7 6 7 5 7 2 8
出力例 3
2023
Score : 500 points
Problem Statement
You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i. The degree of each vertex is at most 10.
Let K be the number of simple paths (paths without repeated vertices) starting from vertex 1. Print \min(K, 10^6).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)
- 1 \leq u_i, v_i \leq N
- The given graph is simple.
- The degree of each vertex in the given graph is at most 10.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print the answer.
Sample Input 1
4 2 1 2 2 3
Sample Output 1
3
We have the following three paths that count. (Note that a path of length 0 also counts.)
- Vertex 1;
- vertex 1, vertex 2;
- vertex 1, vertex 2, vertex 3.
Sample Input 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 2
16
Sample Input 3
8 21 2 6 1 3 5 6 3 8 3 6 4 7 4 6 3 4 1 5 2 4 1 2 2 7 1 4 3 5 2 5 2 3 4 5 3 7 6 7 5 7 2 8
Sample Output 3
2023
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
N 頂点の木があります。頂点には 1 から N までの番号が付いており、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。
x=1,2,\ldots,N に対して次の問題を解いてください。
- 木の頂点の部分集合 V であって空でないものは 2^N-1 通り存在するが、そのうち V による誘導部分グラフの連結成分数が x であるようなものは何通りあるかを 998244353 で割った余りを求めよ。
誘導部分グラフとは
S をグラフ G の頂点の部分集合とします。このとき、G の S による誘導部分グラフとは、頂点集合が S で、辺集合が「G の辺であって両端が S に含まれるものすべて」であるようなグラフです。制約
- 1 \leq N \leq 5000
- 1 \leq a_i \lt b_i \leq N
- 与えられるグラフは木
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
出力
N 行出力せよ。
i 行目には x=i に対する出力をせよ。
入力例 1
4 1 2 2 3 3 4
出力例 1
10 5 0 0
以下の 5 通りでは誘導部分グラフの連結成分数が 2、これら以外では 1 になります。
- V = \{1,2,4\}
- V = \{1,3\}
- V = \{1,3,4\}
- V = \{1,4\}
- V = \{2,4\}
入力例 2
2 1 2
出力例 2
3 0
入力例 3
10 3 4 3 6 6 9 1 3 2 4 5 6 6 10 1 8 5 7
出力例 3
140 281 352 195 52 3 0 0 0 0
Score : 500 points
Problem Statement
You are given a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects vertex a_i and vertex b_i.
Solve the following problem for each x=1,2,\ldots,N:
- There are (2^N-1) non-empty subsets V of the tree's vertices. Find the number, modulo 998244353, of such V that the subgraph induced by V has exactly x connected components.
What is an induced subgraph?
Let S be the subset of the vertices of a graph G; then the subgraph of G induced by S is a graph whose vertex set is S and whose edge set consists of all edges of G whose both ends are contained in S.Constraints
- 1 \leq N \leq 5000
- 1 \leq a_i \lt b_i \leq N
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Output
Print N lines.
The i-th line should contain the answer for x=i.
Sample Input 1
4 1 2 2 3 3 4
Sample Output 1
10 5 0 0
The induced subgraph will have two connected components in the following five cases and one in the others.
- V = \{1,2,4\}
- V = \{1,3\}
- V = \{1,3,4\}
- V = \{1,4\}
- V = \{2,4\}
Sample Input 2
2 1 2
Sample Output 2
3 0
Sample Input 3
10 3 4 3 6 6 9 1 3 2 4 5 6 6 10 1 8 5 7
Sample Output 3
140 281 352 195 52 3 0 0 0 0