| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2020 - Sprinklers 2: Return of the Alfalfa | 100 (p) | 4.0s | 512M |
| 2 | USACO 2020 - Exercise | 100 (p) | 4.0s | 512M |
| 3 | USACO 2020 - Circus | 100 (p) | 4.0s | 512M |
Nông dân John có một cánh đồng nhỏ dạng lưới \(N\) hàng và \(N\) cột (\(1 \leq N \leq 2000\)), trong đó ô thứ \(j\) từ bên trái của hàng thứ \(i\) tính từ trên xuống được ký hiệu là \((i,j)\) với mọi \(1 \leq i,j \leq N\). Ông muốn trồng ngô ngọt và cỏ linh lăng trên cánh đồng. Để làm vậy, ông cần lắp đặt một số vòi phun nước đặc biệt.
Một vòi phun ngô ngọt tại ô \((I,J)\) sẽ tưới tất cả các ô ở phía dưới bên trái, tức là các ô \((i,j)\) thỏa mãn \(I \leq i\) và \(j \leq J\).
Một vòi phun cỏ linh lăng tại ô \((I,J)\) sẽ tưới tất cả các ô ở phía trên bên phải, tức là các ô \((i,j)\) thỏa mãn \(i \leq I\) và \(J \leq j\).
Một ô được một hoặc nhiều vòi phun ngô ngọt tưới có thể trồng ngô ngọt; một ô được một hoặc nhiều vòi phun cỏ linh lăng tưới có thể trồng cỏ linh lăng. Tuy nhiên, một ô được cả hai loại vòi phun tưới (hoặc không được loại nào tưới) thì không thể trồng được gì.
Hãy giúp FJ xác định số cách lắp đặt vòi phun trên cánh đồng, mỗi ô nhiều nhất một vòi, sao cho mọi ô đều màu mỡ (tức là được đúng một loại vòi phun tưới). Hãy tính số cách theo modulo \(10^9+7\).
Một số ô đã có những con bò lông xù chiếm chỗ; điều này không ngăn các ô đó trở nên màu mỡ, nhưng không thể lắp vòi phun tại những ô này.
Tệp sprinklers2.in:
Dòng đầu tiên chứa một số nguyên \(N\).
Với mỗi \(1 \leq i \leq N\), dòng thứ \(i+1\) chứa một xâu độ dài \(N\) mô tả hàng thứ \(i\) của lưới. Mỗi ký tự trong xâu là W (biểu thị một ô có bò lông xù chiếm chỗ) hoặc . (biểu thị ô trống).
Tệp sprinklers2.out:
In ra phần dư của số cách lắp đặt vòi phun khi chia cho \(10^9+7\).
Ví dụ 1
2
..
..28Dưới đây là tất cả mười bốn khả năng khi ngô ngọt có thể mọc tại ô \((1,1)\).
CC .C CA CC .C CA CA C. CA C. CC .C CC .C
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..
Ví dụ 2
4
..W.
..WW
WW..
...W2304Ví dụ này thỏa mãn các ràng buộc của phân nhóm đầu tiên.
USACO 2020 US Open Contest, Platinum — Sprinklers 2: Return of the Alfalfa
Tác giả bài: Benjamin Qi.
Nông dân John lại nghĩ ra một bài tập thể dục buổi sáng mới cho những con bò!
Như trước đây, \(N\) con bò của Nông dân John (\(1 \leq N \leq 7500\)) đang đứng thành một hàng. Con bò thứ \(i\) từ bên trái mang nhãn \(i\) với mỗi \(1 \leq i \leq N\). Ông yêu cầu chúng lặp lại bước sau cho đến khi những con bò trở về đúng thứ tự ban đầu:
Ví dụ, nếu \(A=(1,2,3,4,5)\) thì những con bò thực hiện một bước và lập tức trở về cùng thứ tự. Nếu \(A=(2,3,1,5,4)\) thì những con bò thực hiện sáu bước trước khi trở về thứ tự ban đầu. Thứ tự của những con bò từ trái sang phải sau mỗi bước như sau:
Tính tích của số bước cần thiết ứng với tất cả \(N!\) hoán vị \(A\) độ dài \(N\) có thể có.
Vì số này có thể rất lớn, hãy in đáp án theo modulo \(M\) (\(10^8 \leq M \leq 10^9+7\), \(M\) là số nguyên tố).
Thí sinh sử dụng C++ có thể thấy đoạn mã sau từ KACTL hữu ích. Kỹ thuật này được gọi là phép giảm Barrett, cho phép bạn tính \(a \% b\) nhiều lần nhanh hơn thông thường, trong đó \(b>1\) là một hằng số nhưng không được biết tại thời điểm biên dịch. (Đáng tiếc là chúng tôi không biết một cách tối ưu tương tự dành cho Java.)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod F(2);
int main() {
int M = 1000000007; F = FastMod(M);
ull x = 10ULL*M+3;
cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}
Tệp exercise.in:
Dòng đầu tiên chứa \(N\) và \(M\).
Tệp exercise.out:
In một số nguyên duy nhất.
Lưu ý: Bài này có giới hạn bộ nhớ được mở rộng lên 512 MB.
Ví dụ 1
5 1000000007369329541Với mỗi \(1 \leq i \leq N\), phần tử thứ \(i\) của mảng sau là số hoán vị khiến những con bò thực hiện \(i\) bước: \([1,25,20,30,24,20]\). Đáp án là \(1^1\cdot 2^{25}\cdot 3^{20}\cdot 4^{30}\cdot 5^{24}\cdot 6^{20}\equiv 369329541\pmod{10^9+7}\).
USACO 2020 US Open Contest, Platinum — Exercise
Tác giả bài: Benjamin Qi.
\(N\) con bò của Đoàn xiếc Nông dân John (\(1 \leq N \leq 10^5\)) đang chuẩn bị cho những tiết mục sắp tới. Tất cả các tiết mục diễn ra trên một cây có các đỉnh được đánh số \(1 \ldots N\). "Trạng thái bắt đầu" của một tiết mục được xác định bởi một số \(1 \leq K \leq N\) và một cách gán các con bò \(1 \ldots K\) vào các đỉnh của cây sao cho không có hai con bò nào ở cùng một đỉnh.
Trong một tiết mục, những con bò thực hiện một số lượng "nước đi" lớn tùy ý. Trong một nước đi, một con bò di chuyển từ đỉnh hiện tại của nó sang một đỉnh kề chưa có con bò nào chiếm giữ. Hai trạng thái bắt đầu được gọi là tương đương nếu có thể đi từ trạng thái này đến trạng thái kia bằng một chuỗi nước đi nào đó.
Với mỗi \(1 \leq K \leq N\), hãy giúp những con bò xác định số lớp tương đương của các trạng thái bắt đầu; nói cách khác, đó là số trạng thái bắt đầu tối đa mà chúng có thể chọn sao cho không có hai trạng thái nào tương đương. Vì những số này có thể rất lớn, hãy in phần dư của chúng theo modulo \(10^9+7\).
Tệp circus.in:
Dòng \(1\) chứa \(N\).
Mỗi dòng \(2 \leq i \leq N\) chứa hai số nguyên \(a_i\) và \(b_i\), biểu thị một cạnh nối \(a_i\) và \(b_i\) trên cây.
Tệp circus.out:
Với mỗi \(1 \leq i \leq N\), dòng thứ \(i\) của dữ liệu ra chứa đáp án cho \(K=i\) theo modulo \(10^9+7\).
Ví dụ 1
5
1 2
2 3
3 4
3 51
1
3
24
120Với \(K=1\) và \(K=2\), hai trạng thái bất kỳ đều có thể biến đổi qua lại.
Bây giờ xét \(K=3\) và gọi \(c_i\) là vị trí của bò \(i\). Trạng thái \((c_1,c_2,c_3)=(1,2,3)\) tương đương với các trạng thái \((1,2,5)\) và \((1,3,2)\). Tuy nhiên, nó không tương đương với trạng thái \((2,1,3)\).
Ví dụ 2
8
1 3
2 3
3 4
4 5
5 6
6 7
6 81
1
1
6
30
180
5040
40320USACO 2020 US Open Contest, Platinum — Circus
Tác giả bài: Dhruv Rohatgi.