1. Google Code Jam 2022 - Intranets
Apricot Rules LLC đang phát triển một giao thức mạng đơn giản mới và muốn trình diễn thuật toán định tuyến của mình. Theo thiết kế, một mạng gồm \(\mathbf{M}\) máy được đánh số từ \(1\) đến \(\mathbf{M}\), và mỗi cặp máy được nối bằng một liên kết trực tiếp. Mỗi liên kết được gán một độ ưu tiên nguyên duy nhất trong đoạn từ \(1\) đến \(\mathbf{M}(\mathbf{M}-1)/2\), và mỗi máy định tuyến lưu lượng theo các độ ưu tiên ấy.
Không may, thuật toán định tuyến quá hung hăng: nó chuyển toàn bộ lưu lượng từ một máy qua liên kết có độ ưu tiên cao nhất nối với máy đó. Điều này có thể khiến một số nhóm máy bị cô lập khỏi các nhóm khác.
Chính xác hơn, ta nói máy \(m\) sử dụng liên kết \(\ell\) khi và chỉ khi \(\ell\) là liên kết có độ ưu tiên cao nhất nối với \(m\). Một liên kết được gọi là hoạt động nếu nó được ít nhất một trong hai máy ở hai đầu sử dụng. Với các độ ưu tiên đã cho, mạng ban đầu bị chia thành những intranet rời nhau. Hai máy thuộc cùng một intranet khi và chỉ khi tồn tại một đường đi giữa chúng chỉ dùng các liên kết hoạt động.
Trong hình bên trái ở trên, chỉ các liên kết có độ ưu tiên \(6\) và \(5\) hoạt động, tạo ra hai intranet rời nhau. Trong ví dụ bên phải, ba liên kết hoạt động, tạo thành một intranet duy nhất chứa cả \(4\) máy.
Là thành viên nhóm bảo đảm chất lượng của Apricot Rules LLC, bạn đang điều tra mức độ nghiêm trọng của vấn đề. Hãy tính xác suất có đúng \(\mathbf{K}\) intranet nếu các độ ưu tiên được gán đều ngẫu nhiên trong số \(\bigl(\mathbf{M}(\mathbf{M}-1)/2\bigr)!\) cách gán.
Dữ liệu vào
Dòng đầu chứa số lượng bộ test \(\mathbf{T}\). Tiếp theo là \(\mathbf{T}\) bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên \(\mathbf{M}\) và \(\mathbf{K}\): số máy và số intranet mục tiêu.
Dữ liệu ra
Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là xác suất cần tìm, tính theo modulo số nguyên tố \(10^9+7=1000000007\), được định nghĩa chính xác như sau.
Biểu diễn xác suất thành phân số tối giản \(p/q\), trong đó \(p,q\) là các số nguyên không âm làm \(p+q\) nhỏ nhất. Khi đó
với \(q^{-1}\) là nghịch đảo nhân modulo của \(q\) theo modulo \(10^9+7\). Có thể chứng minh rằng trong các ràng buộc của bài, \(y\) luôn tồn tại và là duy nhất.
Ràng buộc
- \(1\le\mathbf{T}\le50\).
- \(1\le\mathbf{K}\le\mathbf{M}/2\).
Phân nhóm
- Test Set 1 (phán quyết hiển thị): \(2\le\mathbf{M}\le50\).
- Test Set 2 (phán quyết ẩn): \(2\le\mathbf{M}\le5\times10^5\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 17/44 | 38,64% |
| Test Set 2 | 27/44 | 61,36% |
Ví dụ
Ví dụ 1
Input
3
5 2
5 1
6 3Output
Case #1: 428571432
Case #2: 571428576
Case #3: 47619048Giải thích
Trong bộ test mẫu số 1, gọi năm máy \(\mathbf{M}=5\) là \(1,2,3,4,5\) và ký hiệu liên kết nối máy \(a\) với máy \(b\) là \((a,b)\). Giả sử độ ưu tiên của các liên kết \((1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)\) lần lượt là \(9,8,7,6,5,4,3,2,1,10\).
Khi đó máy \(1\) và \(2\) dùng liên kết \((1,2)\), máy \(3\) dùng liên kết \((1,3)\), còn máy \(4\) và \(5\) dùng liên kết \((4,5)\). Do đó ba liên kết \((1,2),(1,3),(4,5)\) hoạt động và có hai intranet \(\{1,2,3\}\) cùng \(\{4,5\}\). Vì \(\mathbf{K}=2\), cách gán này được tính vào đáp án.
Trong \(10!=3628800\) cách gán độ ưu tiên, có \(1555200\) cách tạo đúng \(2\) intranet, nên xác suất là \(3/7\).
Trong bộ test mẫu số 2, xác suất là \(4/7\).
Trong bộ test mẫu số 3, xác suất là \(1/21\).
Nguồn
Google Code Jam 2022, Vòng 1C, bài Intranets.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
