Chương trình C ++ để tìm các cặp dãy trong đó dãy chứa các phần tử tối thiểu và tối đa

Giả sử chúng ta có ba số N, M và K. Có N hàng ngang và M hàng dọc. Chúng tôi sẽ viết một số nguyên trong khoảng từ 1 đến K trên mỗi ô và xác định chuỗi A và B, sao cho -

• đối với mỗi i trong phạm vi từ 1 đến N, A [i] là tối thiểu của tất cả các phần tử trong hàng thứ i

• đối với mỗi j trong phạm vi từ 1 đến M, B [j] là tối đa của tất cả các phần tử trong cột thứ j

Chúng ta phải tìm số cặp (A, B). Nếu câu trả lời quá lớn, hãy trả về kết quả mod 998244353.

Vì vậy, nếu đầu vào giống như N =2; M =2; K =2, thì đầu ra sẽ là 7, vì (A [1], A [2], B [1], B [2]) là (1,1,1,1), (1,1, 1,2), (1,1,2,1), (1,1,2,2), (1,2,2,2), (2,1,2,2) hoặc (2,2 , 2,2).

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

2, 2, 2

Đầu ra

7