Minimum of Degrees
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There is a graph with N vertices and no edges. Chef is going to add all N*(N-1)/2 possible undirected edges to the graph, in a random order. The cost of adding an edge between vertices x and y is equal to min(degree(x), degree(y)). Here, degree(x) denotes the number of edges incident on x before adding the new edge (between x and y).
Find the expected total cost of adding all the edges and print it modulo 998244353. See more details in the output section below.
The input contains a single integer N, denoting the number of vertices.
For the constraints given below, it can be proved that the answer (the expected value of the total cost) can be expressed as a rational P/Q for some integers P and Q, where Q isn't divisible by 998244353. Print one integer: P*Q-1 modulo 998244353. Here, Q-1 denotes the modular inverse with respect to 998244353.
- 2 ≤ N ≤ 300,000
Input1: 3 Output1: 1 Input2: 4 Output2: 199648875
Example #1. The graph contains 3 vertices and Chef will add 3 edges. No matter what the order of adding edges is, the cost of adding the first edge is 0 because degrees of vertices are 0 initially. Similarly, the cost of adding the second edge is 0 because at least one of two vertices connected with a new edge has degree 0. Finally, the third edge connects vertices that both have degree 1 after adding first two edges, so the cost is min(1, 1) = 1. The total cost is always 1, so its expected value is 1 as well.
Example #2. There are 4 vertices and Chef will add 6 edges. The answer is 22/5, so you should print 22 * 5-1 = 22 * 598946612 = 13176825464 = 199648875 (modulo 998244353). Let's analyze one possible scenario:
- Initially, all degrees are equal to 0. Add the edge 2-3 (an edge between vertices 2 and 3) with cost min(0, 0) = 0.
- Degrees of vertices 1, 2, 3, 4 are 0, 1, 1, 0 respectively. Add the edge 1-3 with cost min(0, 1) = 0.
- Degrees are 1, 1, 2, 0. Add the edge 1-4 with cost min(1, 0) = 0.
- Degrees are 2, 1, 2, 1. Add the edge 1-2 with cost min(2, 1) = 1.
- Degrees are 3, 2, 2, 1. Add the edge 2-4 with cost min(2, 1) = 1.
- Degrees are 3, 3, 2, 2. Add the edge 3-4 with cost min(2, 2) = 2.
The total cost in the analyzed scenario is 1 + 1 + 2 = 4.
|Time Limit:||1.75 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.