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

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

    Reply
  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.
    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
  3. I don’t even know how I ended up right here, however I believed this submit was once good.
    I don’t know who you’re however certainly you’re going to a famous blogger
    for those who aren’t already. Cheers!

    Reply

Leave a Comment

2 × 1 =