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

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

10 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

    Reply
  2. 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!

    Reply
  3. 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!

    Reply
  4. 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!

    Reply
    • 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

      Reply
  5. 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!

    Reply
  6. 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?

    Reply
  7. 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!

    Reply

Leave a Comment