सी ++ प्रोग्राम अनुक्रमों के जोड़े खोजने के लिए जहां अनुक्रम न्यूनतम और अधिकतम तत्व रखता है

मान लीजिए कि हमारे पास तीन संख्याएँ N, M और K हैं। N क्षैतिज पंक्तियाँ और M लंबवत पंक्तियाँ हैं। हम प्रत्येक सेल पर 1 और K के बीच एक पूर्णांक लिखेंगे, और अनुक्रम A और B को परिभाषित करेंगे, जैसे -

• 1 से N की श्रेणी में प्रत्येक i के लिए, A[i] ith पंक्ति में सभी तत्वों में से न्यूनतम है

• 1 से M की श्रेणी में प्रत्येक j के लिए, B[j] jth कॉलम में सभी तत्वों में से अधिकतम है

हमें युग्मों की संख्या (A, B) ज्ञात करनी है। यदि उत्तर बहुत बड़ा है, तो परिणाम मोड 998244353 लौटाएं।

तो, अगर इनपुट एन =2 की तरह है; एम =2; K =2, तो आउटपुट 7 होगा, क्योंकि (A[1], A[2], B[1], B[2]) हैं (1,1,1,1), (1,1,) 1,2), (1,1,2,1), (1,1,2,2), (1,2,2,2), (2,1,2,2), या (2,2 ,2,2)।

कदम

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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

इनपुट

2, 2, 2

आउटपुट

7