Olympic Chuyên KHTN 2020 - Ngày 2 - Bài 3 - GIFT

Điểm: 1,00 (OI)

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

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

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

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

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bạn Thế là một người rất ham học. Bạn ấy rất thích các dãy số, vì vậy bạn luôn muốn được ~a_i~ đó tặng một dãy số nhân dịp sinh nhật.

Đến 290520xx, cậu được chú gà Combi tặng hẳn ~2~ dãy số kèm thiệp chúc mừng trong đó ghi dòng chữ thân thương "Đoán xem". Combi đã tặng Thế ~2~ dãy số ~L~, ~R~ có độ dài ~N \leq 300~ sao cho ~−300 \leq L_i \leq R_i \leq 300~. Thế muốn tạo ra một dãy ~A~ độ dài ~N~ sao cho ~L_i \leq A~ ~i \leq R_i~.

Thế sẽ gửi dạy số đó cho một nhân vật bí ẩn tên là HA. Vì HA rất thích số ~K (|K| \leq 90000)~ nên Thế muốn biết có bao nhiêu cách để làm cho dãy cậu gửi cho HA có tổng dãy con liên tiếp có giá trị lớn nhất đúng bằng ~K~

Input

Dòng đầu ghi ~2~ số ~N~ và ~K~. ~N~ dòng sau, mỗi dòng ghi ~2~ số ~L_i~ và ~R_i~.

Output

Số lượng cách, theo mod ~10^9 + 7~

Subtask

~10\%~ số test: ~N \leq 5~, ~|L|, |R| \leq 5~
~30\%~ số test: ~N \leq 30~, ~|L|, |R| \leq 30~
~60\%~ số test: ~N \leq 300~, ~|L|, |R| \leq 300~

Sample Input

4 2
-3 -3
0 1
-3 3
-4 -3

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

17

marvinthang đã bình luận lúc 20, Tháng 3, 2022, 20:31 ← sửa 2 →

My solution:

Đưa bài toán cận tuyệt đối về cận tương đối (đây là 1 kỹ thuật khá đơn giản thường được dùng trong các bài toán đếm, có 1 kỹ thuật tương tự là đưa bài toán 2 cận về 1 cận).

Đưa về bài toán đếm số dãy có tổng dãy con lớn nhất ~\leq x~, tạm gọi là ~calc(x)~, đáp án sẽ là ~calc(x) - calc(x - 1)~.

Đếm bằng QHĐ:

Để mọi dãy con đều có tổng ~\leq x~ thì dãy con lớn nhất kết thúc tại mọi vị trí ~i~ đều phải ~\leq x~.

~\Rightarrow F_{i, j}~: xét đến vị trí ~i~, tổng dãy con lớn nhất kết thúc tại ~i~ là ~j~.

Chuyển trạng thái: ~F_{i, j} \rightarrow F_{i + 1, max(k, j + k)}~ ~(L_{i + 1} \leq k \leq R_{i + 1})~.

Lưu ý: ở mọi trạng thái thì ~j \leq x~.

ĐPT: ~O(N^2 * (max_R - min_L)^2)~.

Cải tiến:

Tối ưu vòng for cuối để chọn ~k~, để ý khi ~j < 0~ thì ~k~ là ~max(k, j + k)~, ngược lại thì ~j + k~ là ~max~

~\Rightarrow if~ ~(j < 0)~ ~F_{i, j} \rightarrow F_{i + 1, k};~ ~ else~ ~F_{i, j} \rightarrow F_{i + 1, j + k};~

Sử dụng ~Prefix~ ~Sum~.

ĐPT: ~O(N^2 * (max_R - min_L))~.

Code mẫu: Ideone.