C++ program to find pairs of sequences holding minimum and maximum elements in a sequence

Suppose we have three numbers N, M and K. There are N horizontal rows and M vertical rows. We will write integers between 1 and K in each cell and define the sequences A and B such that −

• for each in the range 1 to N i, A[i] is the minimum value of all elements in the i-th row

• For each j in the range 1 to M, B[j] is the minimum value in the j-th column Maximum value of all elements

We need to find the number of (A, B). If the answer is too large, the result modulo 998244353 is returned.

So if the input is N = 2; M = 2; K = 2, the output will be 7 because (A[1], A[2], B[1], B[2] ) can be (1,1,1,1), (1,1,1,2), (1,1,2,1), (1,1,2,2), (1,2,2, 2), (2,1,2,2) or (2,2,2,2).

Steps

To solve this problem, we will follow the following steps:

p := 998244353
Define a function power(), this will take a, b, and return (a^b) mod p
From the main method, do the following:
if n is same as 1, then:
   return power(K, m)
if m is same as 1, then:
   return power(K, n)
ans := 0
for initialize t := 1, when t <= K, update (increase t by 1), do:
   ans := (ans + (power(t, n) - power(t - 1, n) + p) mod p * power(K - t + 1, m)) mod p
return ans

Example

Let us see the implementation below to get a better Understanding - The Chinese translation of

#include <bits/stdc++.h>
using namespace std;

long p = 998244353;

long power(long a, long b, long ret = 1){
   for (; b; b >>= 1, a = a * a % p)
      if (b & 1)
         ret = ret * a % p;
   return ret;
}
long solve(int n, int m, int K){
   if (n == 1)
      return power(K, m);
   if (m == 1)
      return power(K, n);
   long ans = 0;
   for (long t = 1; t <= K; t++){
      ans = (ans + (power(t, n) - power(t - 1, n) + p) % p * power(K - t + 1, m)) % p;
   }
   return ans;
}
int main(){
   int N = 2;
   int M = 2;
   int K = 2;
   cout << solve(N, M, K) << endl;
}

Input

is:

Input

2, 2, 2

Output

7

The above is the detailed content of C++ program to find pairs of sequences holding minimum and maximum elements in a sequence. For more information, please follow other related articles on the PHP Chinese website!