Số Cách Điền Lưới

Nguồn: Codeforces Group Độ khó: Khó Quy hoạch động Tổ hợp

Đề 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$.

Ví dụ 1 – input

2 2

Ví dụ 1 – output

7

Ví dụ 2 – input

123 456789

Ví dụ 2 – output

689974806

Giả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ộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Nhận xétĐưa về đếm số 1QHĐTrạng thái & công thứcMinh hoạĐiền bảng fCodeC++ / Python

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.

Nhận xét then chốt

Vì mọi số đều $\ge 1$, "số nhỏ nhất bằng 1" chỉ đơn giản nghĩa là có ít nhất một số 1. Vậy ta chỉ cần đếm số cách sao cho mỗi hàng có ít nhất 1 số 1 và mỗi cột có ít nhất 1 số 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

f[i][j] = số cách điền i hàng đầu tiên, sao cho mỗi hàng đều có số 1 và có đúng j cột đã có ít nhất 1 số 1

• 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ó:

1..kđã có 1

1..kđã có 1

1mới có 1

2..kchưa có 1

1mới có 1

Hàng thứ $i+1$ với $N = 5$: $j = 2$ cột đã có số 1 (xanh dương) điền tự do $1..k$; chọn $x = 2$ cột mới (xanh lá) điền số 1; cột còn lại (đỏ) chỉ được điền $2..k$.

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.

f[i+1][j] += f[i][j] × (k^j − (k−1)^j) × (k−1)^N−j

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).

f[i+1][j+x] += f[i][j] × C(N−j, x) × k^j × (k−1)^N−j−x

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:

N = k =

Ví dụ nhanh:

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()

C++▶ Chạy tay từng dòng codeQHĐ f[i][j]: điền từng hàng, chỉ nhớ số cột đã có số 1; dùng tổ hợp C và luỹ thừa k, k−1.

Dữ liệu vào (stdin) – sửa thoải mái2 2

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3const long long mod = 1000000007LL;

4long long f[255][255];

5long long C[255][255];

6long long powk[255], powk1[255];

7int n, k;

8

9int main(){

10 cin >> n >> k;

11 for(int i = 0; i <= n; i++){

12 C[i][0] = 1;

13 C[i][i] = 1;

14 }

15 for(int i = 1; i <= n; i++){

16 for(int j = 1; j < i; j++){

17 C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;

18 }

19 }

20 powk[0] = 1LL;

21 for(int i = 1; i <= n; i++){

22 powk[i] = (powk[i - 1] * (long long)k) % mod;

23 }

24 powk1[0] = 1LL;

25 for(int i = 1; i <= n; i++){

26 powk1[i] = (powk1[i - 1] * (long long)(k - 1)) % mod;

27 }

28 f[0][0] = 1LL;

29 for(int i = 0; i <= n; i++){

30 for(int j = 0; j <= n; j++){

31 if(f[i][j] == 0){

32 continue;

33 }

34 long long value = f[i][j];

35 (value *= powk1[n - j]) %= mod;

36 (value *= (powk[j] - powk1[j] + mod) % mod) %= mod;

37 (f[i + 1][j] += value) %= mod;

38 for(int x = 1; x <= n - j; x++){

39 value = f[i][j];

40 (value *= C[n - j][x]) %= mod;

41 (value *= powk[j]) %= mod;

42 (value *= powk1[n - j - x]) %= mod;

43 (f[i + 1][j + x] += value) %= mod;

44 }

45 }

46 }

47 cout << f[n][n];

48 return 0;

49}

ChậmVừaNhanhRất nhanh

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.

Không gian$O(N^2)$

Thời gian$O(N^3)$

Ghi chú của mình: bản Python là mình viết thêm theo đúng công thức trên, chỉ giữ 2 hàng của bảng 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.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇