Bedao Mini Contest 09 - FIRE

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bản đồ của ~1~ khu rừng được chia thành các ô vuông bằng nhau và biểu diễn dưới dạng mặt phẳng ~Oxy~ (mỗi ô ứng với ~1~ điểm có tọa độ nguyên). Một đám cháy rừng sẽ diễn ra như sau :

  • Ban đầu chỉ có ~1~ ô bị cháy.
  • Sau ~1~ đơn vị thời gian, đám cháy sẽ lan sang các ô có chung đỉnh hoặc chung cạnh với các ô đang cháy.

Cho ~2~ điểm ~A(0, a)~ và ~B(b, 0)~ trên mặt phẳng, bạn cần phải đi từ ~A~ đến ~B~ sao cho mỗi bước chỉ được đi xuống hoặc sang phải. Ngoài ra bạn cần trả lời các truy vấn sau:

  • Mỗi truy vấn cho ~1~ cặp số ~x, t~. Hỏi nếu có ~1~ đám cháy ở ô ~(x, x)~ và đã kéo dài ~t~ đơn vị thời gian thì có bao nhiêu cách đi từ ~A~ tới ~B~ mà không đi qua các ô bị cháy ?

Ví dụ khi có điểm ~A(0, 4)~ và ~B(4, 0)~:

Input

  • Gồm ~2~ dòng chứa ~2~ số nguyên ~a~ , ~b~ (thể hiện tọa độ điểm ~A~ và ~B~ như đề bài) và số nguyên ~Q~ là số lượng truy vấn. ~(1 \le a, b \le 10^{6})~ ~(1 \le q \le 3 \times 10^{5})~
  • ~Q~ dòng tiếp theo , mỗi dòng chứa ~2~ số nguyên ~x~ , ~t~ là câu hỏi cho mỗi truy vấn. ~(0 \le |x|, t \le 10^{9})~

Output

  • In ra ~Q~ dòng, mỗi dòng là phần dư của kết quả truy vấn đó sau khi chia cho ~10^9+7~.

Sample Input

4 4 2
2 1
2 0

Sample Output

2 
34

Subtask

  • ~20\%~ số test có ~a \times b \le 1000000~ , ~q = 1~
  • ~20\%~ số test tiếp theo có ~q = 1~ và ~x \le 0~
  • ~60\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.