Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
Expected Number of SCCs RCTEXSCC SOLUTION Chef has a matrix A with size M×N. He wants to fill each of its cells with a random integer between 1 and K (inclusive); these integers are independent.
Then, Chef builds a directed graph on this matrix: for each ordered pair of side-adjacent cells of the matrix such that the value in the first cell is greater than or equal to the value in the second cell, he adds an edge from the first cell to the second cell.Expected Number of SCCs RCTEXSCC SOLUTION
Find the expected value of the number of strongly connected components (SCC) in this graph. It can be proved that the answer can be represented as a fraction P/Q, where P and Q are positive integers and Q is coprime with 998,244,353. You should compute P⋅Q−1 modulo 998,244,353, where Q−1 denotes the multiplicative inverse of Q modulo 998,244,353.
The first and only line of the input contains three space-separated integers M, N and K.
Print a single line containing one integer P⋅Q−1 modulo 998,244,353.
Subtask #1 (5 points, time limit 1s):
Subtask #2 (10 points, time limit 2s): M=1
Subtask #3 (10 points, time limit 2s):
Subtask #4 (75 points, time limit 3s): original constraints
2 2 2
The total number of ways to fill the matrix is 16. We get:
- 1 SCC with a probability 2/16
- 2 SCCs with a probability 12/16
- 3 SCCs with a probability 0/16
- 4 SCCs with a probability 2/16
The expected number of SCCs is 2/16+24/16+8/16=34/16=34⋅16−1=873463811. We can check that indeed, 873463811⋅16=34 modulo 998244353.
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef