मान लीजिए हमारे पास तीन संख्याएं N, M और K हैं। N क्षैतिज पंक्तियां और M लंबवत पंक्तियां हैं। हम प्रत्येक सेल पर 1 और K के बीच एक पूर्णांक लिखेंगे, और अनुक्रम A और B को परिभाषित करेंगे, जैसे कि:
- रेंज 1 से N में प्रत्येक i के लिए, A[i] iवीं पंक्ति के सभी तत्वों का न्यूनतम है
- रेंज 1 से M में प्रत्येक j के लिए, B[j] jवें कॉलम के सभी तत्वों का अधिकतम है
हमें युग्म (A, B) की संख्या ढूंढनी है। यदि उत्तर बहुत बड़ा है, तो परिणाम को 998244353 मॉड्यूलो वापस करें।
उदाहरण के लिए, यदि इनपुट N = 2; M = 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 एक फ़ंक्शन power() परिभाषित करें, जो a, b लेता है, और (a^b) mod p वापस करता है मुख्य विधि से, निम्नलिखित करें: यदि n, 1 के बराबर है, तो: power(K, m) वापस करें यदि m, 1 के बराबर है, तो: power(K, n) वापस करें ans := 0 t := 1 से K तक, करें: ans := (ans + (power(t, n) - power(t - 1, n) + p) mod p * power(K - t + 1, m)) mod p 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
