# Expected Number of SCCs RCTEXSCC SOLUTION Code Chef

Page Contents

## Expected Number of SCCs RCTEXSCC SOLUTION Code Chef

Chef has a matrix AA with size M×NM×N. He wants to fill each of its cells with a random integer between 11 and KK (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.

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/QP/Q, where PP and QQ are positive integers and QQ is coprime with 998,244,353998,244,353. You should compute P⋅Q−1P⋅Q−1 modulo 998,244,353998,244,353, where Q−1Q−1 denotes the multiplicative inverse of QQ modulo 998,244,353998,244,353.

### Input

• The first and only line of the input contains three space-separated integers MM, NN and KK.

### Output

Print a single line containing one integer P⋅Q−1P⋅Q−1 modulo 998,244,353998,244,353.

### Constraints

• 1≤M≤21≤M≤2
• 1≤N≤1051≤N≤105
• 1≤K≤1081≤K≤108

Subtask #1 (5 points, time limit 1s):

• N≤4N≤4
• K≤5K≤5

Subtask #2 (10 points, time limit 2s): M=1M=1

Subtask #3 (10 points, time limit 2s):

• M=2M=2
• N≤500N≤500
• K≤500K≤500

Subtask #4 (75 points, time limit 3s): original constraints

```2 2 2
```

### Example Output

```873463811
```

### Explanation

The total number of ways to fill the matrix is 1616. We get:

• 11 SCC with a probability 2/162/16
• 22 SCCs with a probability 12/1612/16
• 33 SCCs with a probability 0/160/16
• 44 SCCs with a probability 2/162/16

The expected number of SCCs is 2/16+24/16+8/16=34/16=34⋅16−1=8734638112/16+24/16+8/16=34/16=34⋅16−1=873463811. We can check that indeed, 873463811⋅16=34873463811⋅16=34 modulo 998244353998244353.

## Solution

Program Python:

```N = 100001

# array to store inverse of 1 to N
factorialNumInverse = [None] * (N + 1)

# array to precompute inverse of 1! to N!
naturalNumInverse = [None] * (N + 1)

# array to store factorial of
# first N numbers
fact = [None] * (N + 1)

# Function to precompute inverse of numbers
def InverseofNumber(p):
naturalNumInverse = naturalNumInverse = 1
for i in range(2, N + 1, 1):
naturalNumInverse[i] = (naturalNumInverse[p % i] *
(p - int(p / i)) % p)

# Function to precompute inverse
# of factorials
def InverseofFactorial(p):
factorialNumInverse = factorialNumInverse = 1

# precompute inverse of natural numbers
for i in range(2, N + 1, 1):
factorialNumInverse[i] = (naturalNumInverse[i] *
factorialNumInverse[i - 1]) % p

# Function to calculate factorial of 1 to N
def factorial(p):
fact = 1

# precompute factorials
for i in range(1, N + 1):
fact[i] = (fact[i - 1] * i) % p

# Function to return nCr % p in O(1) time
def Binomial(N, R, p):

# n C r = n!*inverse(r!)*inverse((n-r)!)
ans = ((fact[N] * factorialNumInverse[R])% p *
factorialNumInverse[N - R])% p
return ans
def calculate(p, q):
mod = 998244353
expo = 0
expo = mod - 2
while (expo):
if (expo & 1):
p = (p * q) % mod
q = (q * q) % mod
expo >>= 1
return p
import math
def ncr(n, r, p):
num = den = 1
for i in range(r):
num = (num * (n - i)) % p
den = (den * (i + 1)) % p
return (num * pow(den, p - 2,p)) % p
p = 998244353
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
M,N,K = map(int,input().split())
xx = 998244353
if M==2:
exit(0)
ans = 0
power = 1
for i in range(1,N+1):
ans = (ans%xx+(((Binomial(N-1,i-1,xx)*((i*K)%xx))%xx)*(power%xx))%xx)%xx
power = ((power%xx)*((K-1)%xx))%xx
print(int(calculate(ans,pow(K,N))))```

Program C++:

```#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ulli;
const ll MOD = 1000000007;
const ll mod = 998244353;
{
ulli expo;
expo = mod - 2;
while (expo) {
if (expo & 1) {
p = (p * q) % mod;
}
q = (q * q) % mod;
expo >>= 1;
}
return p;
}
ll power(ll a, ll b)
{
if (b == 0)
return 1;
if (b == 1)
return a;
if (b % 2 == 1)
return (power(a, b - 1) * a) % mod;
ll q = power(a, b / 2);
return (q * q) % mod;
}
void solve()
{
ll m, n, k;
cin >> m >> n >> k;
if (m == 2)
{
ll x = power(k, 2 * n);
x = power(x, mod - 2);
if (k == 1)
{
cout << x << endl;
return;
}
ll dp[n];
memset(dp, 0, sizeof dp);
dp = k;
dp = (2 * k * (k - 1)) % mod;
for (int i = 1; i < n; i++)
{
dp[i] += ((k - 1) * (dp[i - 1] + (k * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += dp[i - 1];
dp[i] %= mod;
dp[i] += (2LL * dp[i - 1]) % mod;
dp[i] %= mod;
dp[i] += ((k - 2) * (dp[i - 1] + (((k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += ((k - 1) * (dp[i - 1] + (k * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += ((k - 1) * (dp[i - 1] + (k * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += ((((k - 2) * (k - 1)) % mod) * (dp[i - 1] + (2 * k * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += dp[i - 1];
dp[i] %= mod;
dp[i] += ((((k - 2)) % mod) * (dp[i - 1] + (((k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += ((((k - 2)) % mod) * (dp[i - 1] + (((k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += ((((k - 2)) % mod) * (dp[i - 1] + ((2 * (k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += ((((k - 1)) % mod) * (dp[i - 1] + ((2 * (k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
dp[i] += ((((k - 2) * (max(k - 3, 0LL))) % mod) * (dp[i - 1] + ((2 * (k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod;
dp[i] %= mod;
}
ll ans = dp[n - 1] + dp[n - 1];
ans %= mod;
ans *= x;
ans %= mod;
cout << ans << endl;
}
else if (m==1)
{
n=n-1,k=k-1;
ll p = ((n%mod)*(k%mod))%mod;
}
}
int main()
{
std::ios::sync_with_stdio(false);
int t = 1;
while (t--)
{
solve();
}
return 0;
}```

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

1. I just could not go away your website prior to suggesting that I
actually loved the usual information a person provide to your guests?
Is gonna be back incessantly in order to investigate cross-check new posts

2. Hi giá cam sành, Arjun here an editor. Regarding hosting plan or server’s I don’t have much info on that, except that this site is hosted on shared hosting.
The reason, why the site loads, much faster is because CYBER GEEK(Admin) has really put months of effort into it. As, point of user experience during pandemic many student’s looks for answer online and time is a key factor just imagine giving an exam in which 1 min is given to 1 question, what if the site itself takes 10 sec to 11 sec to load on top of that images loading takes it’s on time. User’s look for what they have came and if they don’t find the result, they simply hit back button which increases bounce rate, which is really bad for the site.

If you want to increase your site speed, you must focus on how your site structure works, which CSS files can be avoided during the loading process and still won’t break the site and still provide great response in less than 2 sec.
Sorry, I can’t suggest you a hosting provider as I personally have no knowledge about it. I hope you understand my standing.

Thank You,
CYBER GEEK TEAM

3. 