Hướng dẫn giải của [Beginner Free Contest 01] COLOR
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số cách tô màu ~K~ trong ~N~ ô xếp thành hàng sao cho không có hai ô được tô nằm cạnh nhau, lấy modulo ~10^9+7~.
Sub 1: Quy hoạch động theo từng ô — ~O(N \cdot K)~, dùng khi ~N \cdot K~ nhỏ
Với mỗi ô, giữ hai mảng: số cách khi ô hiện tại được tô và khi không tô, theo số ô đã tô ~j~. Ô không tô lấy từ cả hai trạng thái trước; ô được tô chỉ lấy từ trạng thái ô trước không tô. Nếu chỉ nộp sub này: đúng 10/50 test.
Sub 2: Công thức tổ hợp — ~O(K \log MOD)~
Bỏ ~K-1~ ô trống bắt buộc giữa các ô tô, bài toán trở thành chọn ~K~ vị trí trong ~N-K+1~ vị trí: đáp án là ~\binom{N-K+1}{K}~ (bằng 0 nếu ~N-K+1 < K~). Vì ~N \le 10^9~ nên không lập bảng giai thừa; tính tích ~K~ số liên tiếp ở tử và ~K!~ ở mẫu, rồi nhân nghịch đảo của mẫu bằng lũy thừa nhanh (modulo là số nguyên tố, ~N-K+1 < MOD~ nên mẫu khác 0). Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Main đọc ~N, K~ (máy chấm dùng đọc/ghi chuẩn), nếu ~N \cdot K \le 2 \cdot 10^7~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long n, k;
long long power(long long b, long long e) {
long long r = 1; b %= MOD;
for (; e; e >>= 1, b = b * b % MOD) if (e & 1) r = r * b % MOD;
return r;
}
// Sub 1: quy hoạch động theo từng ô O(n*k), dùng khi n*k <= 2*10^7
// a[j]: số cách khi ô hiện tại được tô (đã tô j ô), b[j]: ô hiện tại không tô
void sub1() {
vector<long long> a(k + 2, 0), b(k + 2, 0), na(k + 2), nb(k + 2);
b[0] = 1; // trước ô đầu tiên coi như "ô trước không tô"
for (long long i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
nb[j] = (a[j] + b[j]) % MOD; // ô i không tô
na[j] = (j > 0) ? b[j - 1] : 0; // ô i tô, ô i-1 phải không tô
}
a = na; b = nb;
}
printf("%lld\n", (a[k] + b[k]) % MOD);
}
// Sub 2: đáp án là tổ hợp C(n-k+1, k) (chọn k vị trí không kề nhau).
// Tính tích k số rồi nhân nghịch đảo k!, O(k log MOD)
void sub2() {
long long top = n - k + 1;
if (top < k) { puts("0"); return; }
long long num = 1, den = 1;
for (long long i = 0; i < k; i++) {
num = num * ((top - i) % MOD) % MOD;
den = den * (i + 1) % MOD;
}
printf("%lld\n", num * power(den, MOD - 2) % MOD);
}
int main() {
scanf("%lld %lld", &n, &k);
if (n * k <= 20000000) sub1();
else sub2();
return 0;
}
Bình luận