USACO 2020 - Tháng 12 - Hạng Bạch Kim

Farmer John có \(N\) con bò với nhiều kích thước khác nhau (\(1\le N\le 3000\)). Ban đầu ông xây một chuồng riêng phù hợp cho từng con, nhưng giờ một số con đã lớn quá cỡ chuồng. Cụ thể, FJ đã xây \(N\) chuồng có kích thước \(t_1,t_2,\ldots,t_N\), còn kích thước hiện tại của đàn bò là \(s_1,s_2,\ldots,s_N\) (\(1\le s_i,t_i\le 10^9\)).

Mỗi đêm, đàn bò thực hiện nghi thức tìm chuồng để ngủ. Bò \(i\) có thể ngủ trong chuồng \(j\) khi và chỉ khi nó vừa trong chuồng, tức \(s_i\le t_j\). Mỗi chuồng chứa nhiều nhất một con bò.

Ta gọi một cách ghép bò với chuồng là cực đại khi và chỉ khi mọi con bò được gán vào chuồng đều vừa với chuồng đó, đồng thời mọi con bò chưa được gán đều không thể vừa trong bất kỳ chuồng trống nào còn lại.

Hãy tính số cách ghép cực đại, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(s_1,s_2,\ldots,s_N\), cách nhau bởi dấu cách.

Dòng thứ ba chứa \(N\) số nguyên \(t_1,t_2,\ldots,t_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In số cách ghép cực đại, lấy modulo \(10^9+7\).

Phân nhóm

• Trong các test 2-3, \(N\le 8\).
• Trong các test 4-12, \(N\le 50\).
• Trong các test 13-20, không có ràng buộc bổ sung.

Ví dụ

4
1 2 3 4
1 2 2 3

9

(1, 1), (2, 2), (3, 4)
(1, 1), (2, 3), (3, 4)
(1, 1), (2, 4)
(1, 2), (2, 3), (3, 4)
(1, 2), (2, 4)
(1, 3), (2, 2), (3, 4)
(1, 3), (2, 4)
(1, 4), (2, 2)
(1, 4), (2, 3)

Nguồn

USACO 2020 December Contest, Platinum - Sleeping Cows: https://usaco.org/index.php?page=viewproblem2&cpid=1068

Tác giả: Nick Wu.

Bò Bessie bị người ngoài hành tinh bắt cóc và đang mắc kẹt trong một tàu vũ trụ! Tàu có \(N\) phòng được đánh số \(1\ldots N\) (\(1\le N\le 60\)), với các cửa một chiều nối một số cặp phòng. Do công nghệ kỳ lạ của người ngoài hành tinh, một cửa thậm chí có thể dẫn từ một phòng trở lại chính phòng đó. Không có hai cửa nào có cùng phòng đầu và phòng cuối. Bessie còn có một điều khiển từ xa với các nút được đánh số \(1\ldots K\) (\(1\le K\le 60\)).

Người ngoài hành tinh sẽ thả Bessie nếu cô hoàn thành một nhiệm vụ. Đầu tiên, họ chọn hai phòng \(s\) và \(t\) (\(1\le s,t\le N\)), cùng hai số \(b_s\) và \(b_t\) (\(1\le b_s,b_t\le K\)). Họ đặt Bessie vào phòng \(s\) và yêu cầu cô lập tức nhấn nút \(b_s\). Sau đó, Bessie di chuyển trong tàu và nhấn các nút theo những quy tắc sau:

• Trong mỗi phòng, sau khi nhấn đúng một nút, cô phải chọn đi qua một cửa đến một phòng khác, có thể là chính phòng hiện tại, hoặc dừng lại.
• Sau khi Bessie nhấn một nút, cô không được nhấn lại nút đó trừ khi giữa hai lần sử dụng, cô đã nhấn một nút có số lớn hơn. Nói cách khác, nhấn nút số \(x\) làm nút đó không thể sử dụng, đồng thời đặt lại và cho phép sử dụng tất cả các nút có số \(<x\).
• Nếu Bessie nhấn một nút không hợp lệ, cô lập tức thất bại và bị giữ lại.
• Bessie chỉ được thả nếu cô dừng tại phòng \(t\), nút cuối cùng đã nhấn là \(b_t\), và cô chưa từng nhấn nút không hợp lệ.

Bessie lo rằng mình có thể không hoàn thành được nhiệm vụ. Với \(Q\) truy vấn (\(1\le Q\le 60\)), mỗi truy vấn là một lựa chọn có thể xảy ra của \(s\), \(t\), \(b_s\) và \(b_t\), hãy tính số dãy phòng và lần nhấn nút giúp Bessie được thả. Vì đáp án có thể rất lớn, hãy lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(K\) và \(Q\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) bit, mỗi bit là 0 hoặc 1. Phần tử thứ \(j\) của dòng thứ \(i\) bằng 1 nếu có cửa từ phòng \(i\) đến phòng \(j\), và bằng 0 nếu không có.

Tiếp theo là \(Q\) dòng, mỗi dòng chứa bốn số nguyên \(b_s\), \(s\), \(b_t\), \(t\), lần lượt biểu thị nút xuất phát, phòng xuất phát, nút cuối cùng và phòng cuối cùng.

Dữ liệu ra

Với mỗi truy vấn trong \(Q\) truy vấn, in trên một dòng riêng số dãy hợp lệ, lấy modulo \(10^9+7\).

Phân nhóm

• Trong các test 4-7, \(K\le 5\) và \((b_s,s)\) giống nhau trong mọi truy vấn.
• Trong các test 8-11, \(b_s=K-1\) và \(b_t=K\) với mọi truy vấn.
• Trong các test 12-15, \(N,K,Q\le 20\).
• Trong các test 16-23, không có ràng buộc bổ sung.

Ví dụ

6 3 8
010000
001000
000100
000010
000000
000001
1 1 1 1
3 3 1 1
1 1 3 3
1 1 1 5
2 1 1 5
1 1 2 5
3 1 3 5
2 6 2 6

1
0
1
3
2
2
0
5

6 4 6
001100
001110
101101
010111
110111
000111
3 2 4 3
3 1 4 4
3 4 4 1
3 3 4 3
3 6 4 3
3 1 4 2

26
49
29
27
18
22

6 10 5
110101
011001
001111
101111
111010
000001
2 5 2 5
6 1 5 2
3 4 8 3
9 3 3 5
5 1 3 4

713313311
716721076
782223918
335511486
539247783

Nguồn

USACO 2020 December Contest, Platinum - Spaceship: https://usaco.org/index.php?page=viewproblem2&cpid=1069

Tác giả: Benjamin Qi.

Bessie đã trì hoãn bài tập hóa học dành cho bò và giờ cần bạn giúp! Cô cần tạo một hỗn hợp gồm ba hóa chất bò khác nhau. Tuy nhiên, một số hóa chất không thể trộn với nhau vì sẽ gây nổ. Cụ thể, hai hóa chất mang nhãn \(a\) và \(b\) chỉ có thể cùng xuất hiện trong một hỗn hợp nếu \(a\oplus b\le K\) (\(1\le K\le 10^9\)).

Ở đây, \(a\oplus b\) là phép XOR theo bit của hai số nguyên không âm \(a\) và \(b\). Phép toán này tương đương với cộng từng cặp bit tương ứng trong hệ nhị phân rồi bỏ số nhớ. Ví dụ:

Bessie có \(N\) hộp hóa chất (\(1\le N\le 2\cdot10^4\)), và hộp thứ \(i\) chứa các hóa chất mang nhãn từ \(l_i\) đến \(r_i\), kể cả hai đầu (\(0\le l_i\le r_i\le 10^9\)). Không có hai hộp nào chứa chung hóa chất. Cô muốn biết có thể tạo bao nhiêu hỗn hợp khác nhau gồm ba hóa chất phân biệt. Hai hỗn hợp được coi là khác nhau nếu có ít nhất một hóa chất xuất hiện trong hỗn hợp này nhưng không xuất hiện trong hỗn hợp kia. Vì đáp án có thể rất lớn, hãy lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\), cách nhau bởi dấu cách. Các hộp được cho theo thứ tự tăng dần của nội dung; cụ thể, \(r_i<l_{i+1}\) với mọi \(1\le i<N\).

Dữ liệu ra

In số hỗn hợp gồm ba hóa chất phân biệt mà Bessie có thể tạo, lấy modulo \(10^9+7\).

Phân nhóm

• Các test 3-4 thỏa mãn \(\max(K,r_N)\le 10^4\).
• Các test 5-6 thỏa mãn \(K=2^k-1\) với một số nguyên \(k\ge 1\).
• Các test 7-11 thỏa mãn \(\max(K,r_N)\le 10^6\).
• Các test 12-16 thỏa mãn \(N\le 20\).
• Các test 17-21 không có ràng buộc bổ sung.

Ví dụ

1 13
0 199

4280

6 147
1 35
48 103
125 127
154 190
195 235
240 250

267188

Nguồn

USACO 2020 December Contest, Platinum - Cowmistry: https://usaco.org/index.php?page=viewproblem2&cpid=1070

Tác giả: Benjamin Qi.