USACO 2023 - Tháng 2 - Hạng Bạch Kim

Bessie là một con bò đói. Mỗi ngày, vào bữa tối, nếu trong chuồng có cỏ khô thì nó sẽ ăn một đống cỏ khô. Nông dân John không muốn Bessie chết đói, vì vậy vào một số ngày, ông ta gửi cỏ khô đến vào buổi sáng (trước bữa tối). Cụ thể, vào ngày \(d_i\), John sẽ gửi đến \(b_i\) đống cỏ khô (\(1 \leq d_i \leq 10^{14}\), \(0 \leq b_i \leq 10^{9}\) ).
Lần cập nhật \(U\) \((1 \leq U \leq 10^5)\) diễn ra như sau: Cho một cặp \((d,b)\), cho biết số lượng cỏ khô đến vào ngày \(d\) chuyển thành \(b\). Sau mỗi lần cập nhật, in ra tổng tất cả các ngày mà Bessie có ăn cỏ khô \(modulo\) \(10^9+7\).

Input

\(U\), theo sau là \(U\) dòng miêu tả các cập nhật.

Output

Tổng sau mỗi lần cập nhật \(modulo\) \(10^9+7\).

Scoring

• Subtask \(1\): \(U<=5000\)
• Subtask \(2\): Các lần cập nhật chỉ làm tăng số lượng cỏ khô tại ngày \(d\).
• Subtask \(3\): Không có điều kiện gì thêm.

Example

3
4 3
1 5
1 2 

15
36
18

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

4005
4656
7607
3482
3507
3753
4058
1107
24531

Nông dân John đã tạo ra \(N(1 \leq N \leq 10^5)\) bài toán. Sau đó, ông thuê \(M(1 \leq M \leq 20)\) người giải bài, mỗi người sẽ đánh giá các bài toán là "dễ" hoặc "khó".
Mục tiêu của John bây giờ là tạo ra một bộ bài toán được sắp xếp theo thứ tự độ khó tăng dần, bao gồm một số bài của \(N%\) bài toán trên được sắp xếp theo thứ tự nào đó. Không được tồn tại hai bài toán nào mà một số người giải bài cho rằng bài toán ở sau là dễ nhưng bài toán ở trước là khó.
Đếm số tập bài toán khác rỗng khác nhau thỏa mãn, \(modulo\) \(10^9+7\) .

Input

• Dòng đầu tiên gồm 2 số \(N\) và \(M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa một xâu có độ dài \(N\). Ký tự thứ \(i\) của xâu này là E nếu người giải bài cho rằng bài toán \(i\) là dễ, hoặc H nếu ngược lại.

Output

Số lượng bộ bài toán có thể tạo ra, \(modulo\) \(10^9+7\).

Scoring

• Subtask \(1\): \(M=1\)
• Subtask \(2\): \(M \leq 16\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

3 1
EHE

9

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

33

Bessie thích xem Cowflix, và nó xem ở nhiều nơi. Nông trại của nông dân John có thể được biểu diễn như một cây \(N(1 \leq N \leq 2*10^5)\) đỉnh, và với mỗi đỉnh, Bessie sẽ xem Cowflix ở đây hoặc không. Đầu vào đảm bảo Bessie sẽ xem Cowflix ở ít nhất một đỉnh.

Thật không may, Cowflix đang giới thiệu một mô hình đăng ký mới để tránh việc chia sẻ mật khẩu. Trong mô hình mới của họ, bạn có thể chọn một vùng liên thông kích thước \(d\) trong trang trại và cần trả \(d+k\) đồng cho một tài khoản có thể sử dụng trong vùng đó. Bạn cần chọn một tập hợp các vùng liên thông phân biệt \(c_1,c_2,...,c_C\) sao cho mọi đỉnh mà Bessie xem Cowflix phải có trong một vùng nào đó. Chi phí của tập hợp trên là là \(\sum_{i=1}^{C} (|c_i|+k)\) , trong đó |\(c_i\)| là đỉnh của vùng \(c_i\). Các đỉnh mà Bessie không xem Cowflix không cần phải nằm trong các vùng trên.

Bessie lo lắng rằng mô hình đăng ký mới có thể quá đắt đối với nó và định chuyển sang Mooloo. Để giúp nó đưa ra quyết định, hãy tính số tiền tối thiểu nó cần trả cho Cowflix để duy trì việc xem phim. Vì Cowflix chưa cho biết \(k\), hãy tính kết quả cho tất cả giá trị nguyên của \(k\) từ \(1\) đến \(N\) .

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai chứa xâu nhị phân \(s_1 s_2 s_3 … s_N\), trong đó \(s_i=1\) nếu Bessie xem Cowflix tại đỉnh \(i\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq N)\) biểu diễn cạnh giữa \(a\) và \(b\) trong cây.

Output

Câu trả lời cho mỗi \(k\) từ \(1\) đến \(N\) trên \(N\) dòng riêng biệt.

Scoring

• Subtask \(1\): \(N \leq 5000\)
• Subtask \(2\): Có cạnh nối giữa \(2\) đỉnh \(i\) và \(i+1\)
• Subtask \(3\): \(N \leq 10^5\)
• Subtask \(4\): Không có điều kiện gì thêm.

Example

5
10001
1 2
2 3
3 4
4 5

4
6
8
9
10

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5

4
6
8
9
10
11
12