दो शर्तों के साथ ब्लॉकों को पेंट करने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम

मान लीजिए हमारे पास तीन संख्याएं N, M और K हैं। मान लें N ब्लॉक हैं जो एक पंक्ति में व्यवस्थित हैं। हम उन्हें पेंट करने के निम्नलिखित दो तरीकों पर विचार करते हैं। दो ब्लॉकों के पेंट तभी अलग माने जाते हैं जब ब्लॉकों को निम्नलिखित दो तरीकों से अलग-अलग रंगों से रंगा जाता है:

प्रत्येक ब्लॉक के लिए, इसे पेंट करने के लिए M रंगों में से एक का उपयोग करें। (सभी रंगों का उपयोग करना अनिवार्य नहीं है)
आसन्न ब्लॉकों के अधिकतम K युग्म हो सकते हैं जिन्हें समान रंग से रंगा गया है।

यदि उत्तर बहुत बड़ा है, तो परिणाम को 998244353 मॉड्यूलो वापस करें।

उदाहरण के लिए, यदि इनपुट N = 3; M = 2; K = 1 है, तो आउटपुट 6 होगा, क्योंकि हम उन्हें इन विभिन्न प्रारूपों में पेंट कर सकते हैं: 112, 121, 122, 211, 212, और 221।

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

maxm := 2^6 + 5 p := 998244353 आकार maxm के दो बड़े ऐरे fac और inv परिभाषित करें एक फ़ंक्शन ppow() परिभाषित करें, जो a, b, p लेता है, ans := 1 mod p a := a mod p जब तक b शून्येतर है, करें: यदि b विषम है, तो: ans := ans * a mod p a := a * a mod p b := b/2 ans वापस करें एक फ़ंक्शन C() परिभाषित करें, जो n, m लेता है, यदि m < 0 या m > n, तो: 0 वापस करें fac[n] * inv[m] mod p * inv[n - m] mod p वापस करें मुख्य विधि से, निम्नलिखित करें fac[0] := 1 i := 1 से maxm-1 तक, करें: fac[i] := fac[i - 1] * i mod p inv[maxm - 1] := ppow(fac[maxm - 1], p - 2, p) i := maxm - 2 से 0 तक, करें: inv[i] := (i + 1) * inv[i + 1] mod p ans := 0 i := 0 से k तक, करें: t := C(n - 1, i) tt := m * ppow(m - 1, n - i - 1, p) ans := (ans + t * tt mod p) mod p ans वापस करें

उदाहरण

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

#include <bits/stdc++.h> using namespace std; const long maxm = 2e6 + 5; const long p = 998244353; long fac[maxm], inv[maxm]; long ppow(long a, long b, long p){    long ans = 1 % p;    a %= p;    while (b){       if (b & 1)          ans = ans * a % p;       a = a * a % p;       b >>= 1;    }    return ans; } long C(long n, long m){    if (m < 0 || m > n)       return 0;    return fac[n] * inv[m] % p * inv[n - m] % p; } long solve(long n, long m, long k){    fac[0] = 1;    for (long i = 1; i < maxm; i++)       fac[i] = fac[i - 1] * i % p;    inv[maxm - 1] = ppow(fac[maxm - 1], p - 2, p);    for (long i = maxm - 2; i >= 0; i--)       inv[i] = (i + 1) * inv[i + 1] % p;    long ans = 0;    for (long i = 0; i <= k; i++){       long t = C(n - 1, i);       long tt = m * ppow(m - 1, n - i - 1, p) % p;       ans = (ans + t * tt % p) % p;    }    return ans; } int main(){    int N = 3;    int M = 2;    int K = 1;    cout << solve(N, M, K) << endl; }

इनपुट

3, 2, 1