Số Cách Điền Lưới
Đề bài
Bạn có một bảng lưới vuông $n \times n$ và một số nguyên $k$. Bạn cần điền một số nguyên vào mỗi ô của bảng sao cho thoả mãn cả ba điều kiện sau:
- Tất cả các số trong bảng phải nằm trong khoảng từ 1 đến $k$ (bao gồm cả 1 và $k$).
- Giá trị nhỏ nhất của các số ở hàng thứ $i$ phải bằng 1 $(1 \le i \le n)$.
- Giá trị nhỏ nhất của các số ở cột thứ $j$ phải bằng 1 $(1 \le j \le n)$.
Hãy tìm số cách điền số vào bảng thoả mãn các yêu cầu trên. Vì đáp án có thể rất lớn, bạn chỉ cần in ra kết quả theo modulo $10^9 + 7$.
Đây là các ví dụ về lưới hợp lệ và không hợp lệ khi $n = k = 2$.
Input: một dòng duy nhất chứa 2 số nguyên $n$ và $k$ $(1 \le n \le 250$, $1 \le k \le 10^9)$.
Output: in ra một số nguyên duy nhất là số cách điền thoả mãn, lấy theo modulo $10^9 + 7$.
2 27123 456789689974806Giải thích ví dụ: với $n = k = 2$, có đúng 7 cách điền thoả mãn tất cả các điều kiện:
Trong ví dụ thứ 2, hãy đảm bảo bạn in ra kết quả theo modulo $10^9 + 7$.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm phần hướng dẫn để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Chúc các bạn học tốt và gặt hái nhiều thành công.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Nhận xétTóm tắt và đưa về bài toán đếm số 1
Tóm tắt: cho $N$ và $k$, đếm số cách điền bảng vuông $N$ hàng $N$ cột bằng các số trong đoạn $[1, k]$ sao cho số nhỏ nhất trên mỗi hàng là 1 và số nhỏ nhất trên mỗi cột là 1.
Phương pháp giải: Quy hoạch động, điền lần lượt từng hàng từ trên xuống, và chỉ cần nhớ đã có bao nhiêu cột có số 1 (không cần nhớ cụ thể là cột nào, vì các cột có vai trò như nhau).
QHĐĐịnh nghĩa trạng thái và công thức
- Bài toán cơ sở: $f[0][0] = 1$ (chưa điền hàng nào, chưa cột nào có số 1).
- Đáp án: $f[N][N]$ (điền đủ $N$ hàng và cả $N$ cột đều có số 1).
Xét $f[i][j] > 0$, ta điền hàng thứ $i + 1$. Hiện có $j$ cột đã có số 1 và $N - j$ cột chưa có:
Trường hợp 1: không có cột mới nào có số 1
$N - j$ cột chưa có số 1 vẫn không được có số 1, nên chỉ điền các số từ 2 đến $k$: có $(k-1)^{N-j}$ cách. Với $j$ cột đã có số 1, điền tự do từ 1 đến $k$ là $k^j$ cách, nhưng hàng này cũng phải có ít nhất một số 1, mà số 1 chỉ được nằm trong $j$ cột này, nên phải trừ đi số cách chỉ điền từ 2 đến $k$: còn $k^j - (k-1)^j$ cách.
Trường hợp 2: thêm x cột mới có số 1 (x từ 1 đến N − j)
Chọn ra $x$ cột trong $N - j$ cột còn lại để điền số 1: có $C(N-j, x)$ cách. Những cột còn lại trong $N - j$ cột đó không được có số 1: $(k-1)^{N-j-x}$ cách. Còn $j$ cột đã có số 1 thì điền tự do: $k^j$ cách (hàng này chắc chắn đã có số 1 ở các cột mới rồi).
Mọi phép tính đều lấy modulo $10^9 + 7$. Ta tính sẵn bảng tổ hợp $C$ bằng công thức Pascal $C[i][j]$ $= C[i-1][j]$ $+ C[i-1][j-1]$, và các luỹ thừa $k^i$, $(k-1)^i$ với $i$ từ 0 đến $N$.
Minh hoạĐiền bảng f từng bước
Em nhập $N$ và $k$ nhỏ (tối đa 4) rồi bấm Tiếp. Ô vàng là $f[i][j]$ đang xét, các ô xanh ở hàng dưới là những ô được cộng thêm (số nhỏ +… là lượng được cộng). Ở đây hiển thị số thật, chưa lấy modulo:
CodeSource code
Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:
#include <iostream>
using namespace std;
const long long mod = 1000000007LL;
long long f[255][255];
long long C[255][255];
long long powk[255], powk1[255];
int n, k;
int main(){
cin >> n >> k;
for(int i = 0; i <= n; i++){
C[i][0] = 1;
C[i][i] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j < i; j++){
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
powk[0] = 1LL;
for(int i = 1; i <= n; i++){
powk[i] = (powk[i - 1] * (long long)k) % mod;
}
powk1[0] = 1LL;
for(int i = 1; i <= n; i++){
powk1[i] = (powk1[i - 1] * (long long)(k - 1)) % mod;
}
f[0][0] = 1LL;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
if(f[i][j] == 0){
continue;
}
long long value = f[i][j];
(value *= powk1[n - j]) %= mod;
(value *= (powk[j] - powk1[j] + mod) % mod) %= mod;
(f[i + 1][j] += value) %= mod;
for(int x = 1; x <= n - j; x++){
value = f[i][j];
(value *= C[n - j][x]) %= mod;
(value *= powk[j]) %= mod;
(value *= powk1[n - j - x]) %= mod;
(f[i + 1][j + x] += value) %= mod;
}
}
}
cout << f[n][n];
return 0;
}import sys
def main():
MOD = 10**9 + 7
n, k = map(int, sys.stdin.readline().split())
# tổ hợp C[m][x]
C = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
C[i][0] = C[i][i] = 1
for j in range(1, i):
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD
powk = [1] * (n + 1)
powk1 = [1] * (n + 1)
for i in range(1, n + 1):
powk[i] = powk[i - 1] * k % MOD
powk1[i] = powk1[i - 1] * (k - 1) % MOD
# g[m][x] = C(m, x) * (k-1)^(m-x): chọn x cột mới có số 1, m-x cột còn lại không có số 1
g = [[C[m][x] * powk1[m - x] % MOD for x in range(m + 1)] for m in range(n + 1)]
f = [0] * (n + 1) # f[j] của hàng hiện tại (chỉ giữ 2 tầng cho nhẹ)
f[0] = 1
for _ in range(n):
nf = [0] * (n + 1)
for j in range(n + 1):
v = f[j]
if v == 0:
continue
# không thêm cột mới có số 1
nf[j] = (nf[j] + v * powk1[n - j] % MOD * ((powk[j] - powk1[j]) % MOD)) % MOD
# thêm x >= 1 cột mới có số 1
w = v * powk[j] % MOD
gm = g[n - j]
for x in range(1, n - j + 1):
nf[j + x] = (nf[j + x] + w * gm[x]) % MOD
f = nf
print(f[n])
main()Chú ý biểu thức (powk[j] - powk1[j] + mod) % mod: cộng thêm mod trước khi lấy dư để kết quả phép trừ không bị âm.
f để tiết kiệm bộ nhớ và tính sẵn g[m][x] = C(m, x)·(k−1)^(m−x) cho vòng lặp trong gọn hơn. Cả 2 bản đã được kiểm tra với vét cạn mọi cách điền cho các bảng nhỏ ($n \le 3$, $k \le 4$); với $n = 250$, bản C++ chạy khoảng 0.04 giây, bản Python khoảng 0.7 giây.