मान लीजिए कि हमारे पास तीन नंबर एन, एम और के हैं। विचार करें कि एन ब्लॉक हैं जिन्हें वे एक पंक्ति में व्यवस्थित करते हैं। हम उन्हें पेंट करने के दो तरीकों पर विचार करते हैं। दो ब्लॉक के पेंट अलग-अलग होते हैं यदि और केवल अगर ब्लॉक को अलग-अलग रंगों में निम्नलिखित दो तरीकों से चित्रित किया जाता है -
-
प्रत्येक ब्लॉक के लिए, इसे पेंट करने के लिए एम रंगों में से एक का उपयोग करें। (सभी रंगों का उपयोग करना अनिवार्य नहीं है)
-
निकटवर्ती ब्लॉकों के अधिकतम K जोड़े एक ही रंग में रंगे हुए हो सकते हैं।
यदि उत्तर बहुत बड़ा है, तो परिणाम मोड 998244353 लौटाएं।
तो, अगर इनपुट एन =3 की तरह है; एम =2; K =1, तो आउटपुट 6 होगा, क्योंकि हम उन्हें इन विभिन्न स्वरूपों 112, 121, 122, 211, 212, और 221 में पेंट कर सकते हैं।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
maxm := 2^6 + 5 p := 998244353 Define two large arrays fac and inv or size maxm Define a function ppow(), this will take a, b, p, ans := 1 mod p a := a mod p while b is non-zero, do: if b is odd, then: ans := ans * a mod p a := a * a mod p b := b/2 return ans Define a function C(), this will take n, m, if m < 0 or m > n, then: return 0 return fac[n] * inv[m] mod p * inv[n - m] mod p From the main method, do the following fac[0] := 1 for initialize i := 1, when i < maxm, update (increase i by 1), do: fac[i] := fac[i - 1] * i mod p inv[maxm - 1] := ppow(fac[maxm - 1], p - 2, p) for initialize i := maxm - 2, when i >= 0, update (decrease i by 1), do: inv[i] := (i + 1) * inv[i + 1] mod p ans := 0 for initialize i := 0, when i <= k, update (increase i by 1), do: t := C(n - 1, i) tt := m * ppow(m - 1, n - i - 1, p) ans := (ans + t * tt mod p) mod p return 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
आउटपुट
6