Phân rã cấu hình

Gọi \(N\) là kích thước lưới và \(K\) là số lều của gia đình ba người. Ta có thể phân rã việc đếm cấu hình với \(N,K\) như sau: trước hết chọn \(K\) hàng và \(K\) cột chứa các lều ba người; \(N-K\) hàng và \(N-K\) cột còn lại sẽ chứa các lều hai người và một người. Số cấu hình là tích của bốn đại lượng sau.

• Số cách chọn các tập hàng và cột. Có \(\binom NK^2\) cách chọn \(K\) hàng và \(K\) cột.
• Số cách ghép các lều ba người với các cặp (hàng, cột). Lấy một hoán vị của các cột rồi ghép cột thứ \(i\) trong hoán vị với hàng thứ \(i\) trong tập hàng đã chọn. Có \(K!\) hoán vị.
• Số cách ghép các lều hai người với các cặp (hàng, cột). Tương tự, có \((N-K)!\) cách.
• Số cách ghép các lều một người với các cặp (hàng, cột). Không thể dùng mọi hoán vị trong \((N-K)!\) hoán vị, vì không được chọn ô đã có lều hai người. Với mỗi hàng \(X\) trong \(N-K\) hàng còn lại, chọn duy nhất một hàng \(Y\) trong cùng tập, tìm cột \(C\) chứa lều hai người tại \((Y,C)\), rồi đặt lều một người tại \((X,C)\). Ô này chắc chắn chưa có lều khi và chỉ khi \(Y\ne X\). Do đó ta cần một hoán vị của \(N-K\) hàng không giữ nguyên hàng nào, tức một hoán vị không điểm cố định (derangement). Số cách là \(!(N-K)\).

Tích của các đại lượng trên là

Đáp án là tổng giá trị này, modulo \(10^9+7\), với mọi \(K\) từ \(X\) đến \(N\).

Ta tính hiệu quả bằng cách tiền xử lý \(K!\), \(1/K!\) và \(!K\) modulo \(10^9+7\) cho mọi \(K\le N\). Giai thừa dùng truy hồi hiển nhiên. Nghịch đảo \(1/K!\) có thể tính từ \(K!\) bằng thuật toán Euclid mở rộng hoặc định lý nhỏ Fermat. Số derangement dùng

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - World Finals - Campinatorics, kho Google Coding Competitions (Apache-2.0).