Codeforces Round 700 (Div. 1)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1479 Codeforces Round 700 (Div. 1) FINISHED False 8100 124557862 Feb. 7, 2021, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 220 ) E School Clubs PROGRAMMING dp fft math number theory probabilities

B"In Homer's school, there are n students who love clubs. Initially, there are m clubs, and each of the n students is in exactly one club. In other words, there are a_i students in the i -th club for 1 <= q i <= q m and a_1+a_2+ ... +a_m = n . The n students are so unfriendly that every day one of them (chosen uniformly at random from all of the n students) gets angry. The student who gets angry will do one of the following things. Homer wonders the expected number of days until every student is in the same club for the first time. We can prove that the answer can be represented as a rational number frac p q with gcd(p, q) = 1 . Therefore, you are asked to find the value of pq^{-1} bmod 998 ,244 ,353 . It can be shown that q bmod 998 ,244 ,353 neq 0 under the given constraints of the problem. The first line contains an integer m ( 1 <= q m <= q 1000 ) -- the number of clubs initially. The second line contains m integers a_1, a_2, ... , a_m ( 1 <= q a_i <= q 4 cdot 10^8 ) with 1 <= q a_1+a_2+ ... +a_m <= q 4 cdot 10^8 , where a_i denotes the number of students in the i -th club initially. Print one integer -- the expected number of days until every student is in the same club for the first time, modulo 998 ,244 ,353 . In the first example, no matter which student gets angry, the two students will become in the same club with probability frac 1 4 . So the expected number of days until every student is in the same club should be 4 . In the second example, we note that in the first day: In the fourth example, there is only one club initially. That is, every student has already been in the same club. So the answer is 0 . "...

Tutorials

Editorial of Codeforces Round #700

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
106873892 liouzhou_101 E Feb. 8, 2021, 4:55 a.m. OK GNU C++17 TESTS 95 592 2560000
106849081 maroonrk E Feb. 7, 2021, 7:06 p.m. OK GNU C++17 (64) TESTS 95 483 40243200
106847859 ecnerwala E Feb. 7, 2021, 6:57 p.m. OK GNU C++17 (64) TESTS 95 1716 0
106809809 hos.lyric E Feb. 7, 2021, 3:54 p.m. OK GNU C++17 (64) TESTS 95 1965 0
106861209 Benq E Feb. 7, 2021, 11:48 p.m. OK GNU C++17 (64) TESTS 95 2090 0
106848127 Benq E Feb. 7, 2021, 6:59 p.m. OK GNU C++17 (64) TESTS 95 2948 0
106862710 Benq E Feb. 8, 2021, 12:56 a.m. OK GNU C++17 (64) TESTS 95 3166 11776000
106846880 ecnerwala E Feb. 7, 2021, 6:51 p.m. OK GNU C++17 (64) TESTS 95 3338 0

remove filters

Back to search problems