Giả sử chúng ta có ba số N, M và K. Xét có N khối được xếp thành một hàng. Chúng tôi xem xét sau hai cách để sơn chúng. Các lớp sơn của hai khối khác nhau nếu và chỉ khi các khối được sơn bằng các màu khác nhau theo hai cách sau -
-
Đối với mỗi khối, sử dụng một trong M màu để sơn nó. (không bắt buộc phải sử dụng tất cả các màu)
-
Có thể có nhiều nhất K cặp khối liền kề được sơn cùng màu.
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 =3; M =2; K =1, thì đầu ra sẽ là 6, vì chúng ta có thể vẽ chúng ở các định dạng khác nhau 112, 121, 122, 211, 212 và 221.
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 -
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
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;
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;
} Đầu vào
3, 2, 1
Đầu ra
6