CEOI 2020 - Day 1

Balázs có hàng rào đẹp nhất thị trấn. Hàng rào gồm \(N\) đoạn liền kề nhau; mỗi đoạn là một hình chữ nhật dựng đứng trên mặt đất. Đoạn thứ \(i\) có chiều cao nguyên \(h_i\) và chiều rộng nguyên \(w_i\).

Ta cần đếm số hình chữ nhật đẹp nằm trên hàng rào. Một hình chữ nhật được gọi là đẹp nếu:

• Các cạnh nằm ngang hoặc thẳng đứng và có độ dài nguyên.
• Khoảng cách từ hình chữ nhật đến mặt đất là số nguyên.
• Khoảng cách từ hình chữ nhật đến mép trái của đoạn hàng rào đầu tiên là số nguyên.
• Toàn bộ hình chữ nhật nằm trên các đoạn hàng rào.

Hãy tính số hình chữ nhật đẹp. Vì kết quả có thể rất lớn, hãy in phần dư khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu gồm số nguyên \(N\), là số đoạn của hàng rào.

Dòng thứ hai gồm \(N\) số nguyên \(h_i\), lần lượt là chiều cao các đoạn.

Dòng thứ ba gồm \(N\) số nguyên \(w_i\), lần lượt là chiều rộng các đoạn.

Dữ liệu ra

In một số nguyên duy nhất là số hình chữ nhật đẹp modulo \(10^9+7\).

Ví dụ

2
1 2
1 2

12

Giải thích

Hình dạng hàng rào trong ví dụ:

Có \(5\) hình chữ nhật đẹp có hình dạng sau:

Có \(3\) hình chữ nhật đẹp có hình dạng sau:

Có \(1\) hình chữ nhật đẹp có hình dạng sau:

Có \(2\) hình chữ nhật đẹp có hình dạng sau:

Có \(1\) hình chữ nhật đẹp có hình dạng sau:

Ràng buộc

• \(1\le N\le 10^5\).
• \(1\le h_i,w_i\le 10^9\) với mọi \(i\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(12\) điểm: \(N\le50\), \(h_i\le50\) và \(w_i=1\) với mọi \(i\).
3. \(13\) điểm: \(h_i\in\{1,2\}\) với mọi \(i\).
4. \(15\) điểm: Mọi \(h_i\) bằng nhau.
5. \(15\) điểm: \(h_i\le h_{i+1}\) với mọi \(1\le i<N\).
6. \(18\) điểm: \(N\le1000\).
7. \(27\) điểm: Không có ràng buộc nào khác.

Treeland có \(2N\) thành phố. Quy hoạch mạng lưới đường hiện có \(N\) đoạn đường thẳng, mỗi đoạn nối hai thành phố. Không có hai đoạn đường hiện có nào có điểm chung, kể cả đầu mút.

Hãy xây thêm \(N-1\) đoạn đường sao cho thỏa mãn tất cả các điều kiện sau:

1. Mỗi đoạn đường mới là một đoạn thẳng nối hai thành phố.
2. Nếu hai đoạn đường (cũ hoặc mới) có điểm chung, thì điểm chung đó phải là đầu mút của cả hai đoạn.
3. Mạng lưới đường kết nối tất cả các thành phố: giữa mọi cặp thành phố đều có một đường đi gồm các đoạn đường.

Nếu có nhiều cách xây dựng hợp lệ, bạn có thể in ra bất kỳ cách nào.

Dữ liệu vào

Dòng đầu gồm số nguyên \(N\), số đoạn đường hiện có.

Mỗi dòng trong \(N\) dòng tiếp theo gồm bốn số nguyên \(x_1,y_1,x_2,y_2\), mô tả một đoạn đường nối thành phố \((x_1,y_1)\) với thành phố \((x_2,y_2)\).

Dữ liệu ra

In \(N-1\) dòng. Mỗi dòng gồm bốn số nguyên \(x_1,y_1,x_2,y_2\), mô tả một đoạn đường mới nối thành phố \((x_1,y_1)\) với thành phố \((x_2,y_2)\).

Ví dụ

5
1 3 3 6
5 1 5 3
3 3 6 5
2 1 4 1
2 3 4 2

1 3 2 1
2 1 2 3
3 3 2 3
4 1 5 1

Hình dưới minh họa một mạng lưới đường hoàn chỉnh cho ví dụ.

Ràng buộc

• \(2\le N\le10^5\).
• \(-10^7\le x_i,y_i\le10^7\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(15\) điểm: Mọi đoạn đường đầu vào đều thẳng đứng.
3. \(15\) điểm: Mọi cặp đoạn đường đầu vào đều song song.
4. \(15\) điểm: Mỗi đoạn đường đầu vào nằm ngang hoặc thẳng đứng.
5. \(15\) điểm: \(N\le10000\).
6. \(40\) điểm: Không có ràng buộc nào khác.

Liên bang Hành tinh có \(N\) hành tinh được đánh số từ \(1\) đến \(N\). Một số cặp hành tinh được nối bằng đường hầm không gian. Tàu vũ trụ có thể đi qua đường hầm theo cả hai chiều. Có đúng \(N-1\) đường hầm và có thể đi từ bất kỳ hành tinh nào đến bất kỳ hành tinh nào khác bằng các đường hầm.

Ngoài vũ trụ của chúng ta còn có \(D\) vũ trụ song song giống hệt, cũng có cùng các hành tinh và đường hầm. Các vũ trụ song song được đánh số từ \(1\) đến \(D\); vũ trụ của chúng ta được đánh số \(0\). Ký hiệu hành tinh \(x\) trong vũ trụ \(i\) là \(P_x^i\).

Với mỗi \(i\) từ \(0\) đến \(D-1\), ta sẽ đặt đúng một cổng không gian nối từ \(P_{A_i}^i\) đến \(P_{B_i}^{i+1}\), trong đó \(1\le A_i,B_i\le N\).

Sau khi đặt các cổng, con tàu của thuyền trưởng Batthyány bắt đầu hành trình tại \(P_1^0\). Thuyền trưởng Ágnes và trung úy Gábor lần lượt chọn một hành tinh làm điểm đến. Hành tinh được chọn có thể ở cùng vũ trụ nếu có đường hầm nối tới đó, hoặc ở vũ trụ khác nếu có cổng không gian đi tới đó.

Khi một hành tinh \(P_x^i\) đã được ghé thăm thì không được quay lại hành tinh đó, nhưng vẫn có thể ghé thăm hành tinh \(x\) ở một vũ trụ khác. Ágnes đi trước, sau đó đến Gábor, rồi lại đến Ágnes. Nếu đến lượt mà không thể chọn một hành tinh chưa từng được ghé thăm, người chơi đó thua.

Cả Ágnes và Gábor đều biết vị trí của tất cả đường hầm và cổng, và đều chơi tối ưu. Hãy đếm số cách đặt cổng sao cho Ágnes thắng. Hai cách đặt được xem là khác nhau nếu tồn tại một chỉ số \(i\) mà cổng thứ \(i\) nối hai cặp hành tinh khác nhau trong hai cách đặt.

Vì kết quả có thể rất lớn, hãy in phần dư khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N,D\).

Mỗi dòng trong \(N-1\) dòng tiếp theo gồm hai số nguyên \(u,v\), cho biết có một đường hầm nối \(P_u^i\) với \(P_v^i\) trong mọi vũ trụ \(i\) từ \(0\) đến \(D\).

Dữ liệu ra

In số cách đặt cổng để Ágnes thắng modulo \(10^9+7\).

Ví dụ

3 1
1 2
2 3

4

Chỉ có một cổng và có \(3\cdot3=9\) cách đặt cổng. Bốn cách để Ágnes thắng được minh họa dưới đây.

Ràng buộc

• \(2\le N\le10^5\).
• \(1\le D\le10^{18}\).
• \(1\le u,v\le N\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(7\) điểm: \(N=2\).
3. \(8\) điểm: \(N\le100\) và \(D=1\).
4. \(15\) điểm: \(N\le1000\) và \(D=1\).
5. \(15\) điểm: \(D=1\).
6. \(20\) điểm: \(N\le1000\) và \(D\le10^5\).
7. \(20\) điểm: \(D\le10^5\).
8. \(15\) điểm: Không có ràng buộc nào khác.