Sơ đồ Định Tuyến

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một mạng gồm $N$ nút đánh số từ $1$ đến $N$ , kết nối bởi các cạnh có hướng. Mỗi nút được gán nhãn: S (nguồn), R (đích), hoặc . (trung gian). Số lượng nút nguồn bằng số lượng nút đích.

Một sơ đồ định tuyến là tập hợp các đường đi có hướng từ các nút nguồn đến các nút đích sao cho:

Mỗi cạnh trong đồ thị được đi qua đúng một lần (bởi đúng một đường đi).
Không có hai đường đi nào chia sẻ cùng nút đầu hoặc nút cuối.
Không có đường đi nào tạo thành vòng lặp (chu trình).

Đồ thị được mô tả bởi ma trận kề $N \times N$ (ký tự 0/1). Mọi cạnh $i \to j$ đều thỏa mãn $i < j$ , ngoại trừ đúng $K$ cạnh có $i > j$ (gọi là cạnh ngược).

Đếm số sơ đồ định tuyến hợp lệ, theo modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên chứa $T$ — số lượng test case.

Với mỗi test case:

Dòng đầu: hai số nguyên $N$ và $K$ .
Dòng tiếp theo: xâu độ dài $N$ gồm các ký tự S, R, . mô tả loại mỗi nút.
$N$ dòng tiếp theo: mỗi dòng là xâu nhị phân độ dài $N$ , dòng $i$ mô tả các cạnh xuất phát từ nút $i$ (ký tự $j$ là 1 nếu có cạnh $i \to j$ ).

Dữ liệu ra

Với mỗi test case, in ra một số nguyên — số sơ đồ định tuyến hợp lệ modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq T \leq 20$
$2 \leq N \leq 100$
$0 \leq K \leq 2$ — số cạnh $i \to j$ với $i > j$
$\sum N^{2} \leq 2 \times 10^{4}$
Luôn tồn tại ít nhất một sơ đồ định tuyến hợp lệ
Tại mỗi nút $v$ : $in\_deg (v) + [v là nguồn] = out\_deg (v) + [v là đích]$

Subtask:

Test 4–5: $N \leq 6$
Test 6–7: $K = 0$
Test 8–12: $K = 1$
Test 13–24: $K = 2$

Ví dụ

Input	Output	Giải thích
2 8 0 SS....RR 00100000 00100000 00011000 00000100 00000100 00000011 00000000 00000000 13 0 SSS.RRRSS.RR. 0001000000000 0001000000000 0001000000000 0000111000000 0000000000000 0000000000000 0000000000000 0000000001000 0000000001000 0000000000110 0000000000000 0000000000000 0000000000000	4 12	Test 1 (N=8, K=0): Đồ thị là 1→3, 2→3, 3→{4,5}, 4→6, 5→6, 6→{7,8}. Tại nút 3: 2 đường vào có thể ghép với 2 đường ra theo 2! = 2 cách. Tại nút 6: tương tự 2! = 2 cách. Tổng = 2×2 = 4. Test 2 (N=13, K=0): Tích các bậc ra: 1!×1!×1!×3!×1!×1!×2! = 6×2 = 12.
2 5 1 SS.RR 00101 00100 10010 00000 00000 6 2 S....R 001000 000100 010001 000010 001000 000000	3 1	Test 1 (N=5, K=1): Cạnh ngược: 3→1. Không có sơ đồ nào tạo chu trình qua cạnh này. Tổng = 2!×1!×2! × (1 - P[chu trình]) = 4 × 3/4 = 3. Test 2 (N=6, K=2): Hai cạnh ngược: 3→2 và 5→3. Chỉ có 1 sơ đồ hợp lệ: nguồn 1 đi thẳng 1→3→6 (đích), tránh tạo chu trình 3→2→4→5→3.

Ghi chú

Cạnh ngược là cạnh $i \to j$ với $i > j$ (chỉ số nút lớn hơn đến nhỏ hơn).
Do tất cả cạnh xuôi ( $i < j$ ) không thể tạo chu trình trong thứ tự tô-pô, chỉ cạnh ngược mới có thể gây ra vòng lặp.

Bình luận

Không có bình luận tại thời điểm này.