Page Contents

*Expected Number of SCCs RCTEXSCC SOLUTION Code Chef*

*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

### Subtasks

**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

### Example Input

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*

*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[0] = naturalNumInverse[1] = 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[0] = factorialNumInverse[1] = 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[0] = 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 answer(ulli p, ulli q) { 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][2]; memset(dp, 0, sizeof dp); dp[0][0] = k; dp[0][1] = (2 * k * (k - 1)) % mod; for (int i = 1; i < n; i++) { dp[i][0] += ((k - 1) * (dp[i - 1][0] + (k * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][0] %= mod; dp[i][0] += dp[i - 1][0]; dp[i][0] %= mod; dp[i][0] += (2LL * dp[i - 1][1]) % mod; dp[i][0] %= mod; dp[i][0] += ((k - 2) * (dp[i - 1][1] + (((k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][0] %= mod; dp[i][1] += ((k - 1) * (dp[i - 1][0] + (k * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; dp[i][1] += ((k - 1) * (dp[i - 1][0] + (k * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; dp[i][1] += ((((k - 2) * (k - 1)) % mod) * (dp[i - 1][0] + (2 * k * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; dp[i][1] += dp[i - 1][1]; dp[i][1] %= mod; dp[i][1] += ((((k - 2)) % mod) * (dp[i - 1][1] + (((k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; dp[i][1] += ((((k - 2)) % mod) * (dp[i - 1][1] + (((k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; dp[i][1] += ((((k - 2)) % mod) * (dp[i - 1][1] + ((2 * (k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; dp[i][1] += ((((k - 1)) % mod) * (dp[i - 1][1] + ((2 * (k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; dp[i][1] += ((((k - 2) * (max(k - 3, 0LL))) % mod) * (dp[i - 1][1] + ((2 * (k * (k - 1)) % mod) * power(k, 2 * (i - 1))) % mod) % mod) % mod; dp[i][1] %= mod; } ll ans = dp[n - 1][0] + dp[n - 1][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; cout << answer(p,k+1)+1 << endl; } } int main() { std::ios::sync_with_stdio(false); int t = 1; while (t--) { solve(); } return 0; }

*January Long Challenge 2021*

*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**

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

Howdy! I could have sworn I’ve been to your blog before but after looking at

some of the posts I realized it’s new to me.

Anyhow, I’m certainly delighted I came across

it and I’ll be bookmarking it and checking back often!

I used to be recommended this blog by way of my cousin. I am now not positive whether or not this submit

is written by means of him as nobody else understand such particular approximately my problem.

You are amazing! Thanks!

Hi there would you mind letting me know which web host you’re working with?

I’ve loaded your blog in 3 different browsers and I

must say this blog loads a lot faster then most. Can you suggest a good hosting provider at

a fair price? Thanks a lot, I appreciate it!

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.

So, I hope you got the point here, loading only the those factors which is usefully to your user is important, like (CSS) fonts and structure, loading time of this is less then a sec, the site loads faster and user is still looking for answer that search period is counted as extra bonus even tho! the user don’t find what he/she is looking for the bounce rate won’t increase, but when the site is loading slowly and on top of that user completed it’s searching and site is still in loading process and user hit’s back button the bounce rate will boom!! up. Keeping this factor in mind Admin has configured the site in such a manner that user get’s what they need even on slow internet. It’s month of work and testing, which they occasionally discuss in groups.

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

you are in point of fact a just right webmaster. The site loading pace is incredible.

It kind of feels that you are doing any unique trick. Furthermore, The

contents are masterpiece. you’ve done a excellent task in this topic!

What’s up, yeah this paragraph is really good and I have learned lot of things from it regarding blogging.

thanks.

Wow, this paragraph is nice, my younger sister is analyzing such

things, thus I am going to convey her.

Write more, thats all I have to say. Literally, it seems as though

you relied on the video to make your point.

You definitely know what youre talking about, why waste your intelligence on just posting videos to your site when you could be giving us something

enlightening to read?

Somebody essentially lend a hand to make critically posts I might state.

This is the first time I frequented your web page and

thus far? I amazed with the research you made to make this

actual put up amazing. Wonderful task!