Expected Number of SCCs RCTEXSCC SOLUTION Code Chef

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.

 

Input
The first and only line of the input contains three space-separated integers M, N and K.
Output
Print a single line containing one integer P⋅Q−1 modulo 998,244,353.
 
Constraints
1≤M≤2
1≤N≤105
1≤K≤108
Subtasks
Subtask #1 (5 points, time limit 1s):
 
N≤4
K≤5
Subtask #2 (10 points, time limit 2s): M=1
Subtask #3 (10 points, time limit 2s):
 
M=2
N≤500
K≤500
Subtask #4 (75 points, time limit 3s): original constraints
 
Example Input
2 2 2
Example Output
873463811
Explanation
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.
 

4 thoughts on “Expected Number of SCCs RCTEXSCC SOLUTION Code Chef”

Leave a Comment

close
error: Content is protected !!