TLEOJ Contest #15 - Số miền

View as PDF

Submit solution

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

Author:
Problem type

Cho n đường thẳng nằm trong cùng 1 mặt phẳng sao cho không có 2 đường thẳng nào song song và không có 3 đường thẳng nào giao nhau.
Yêu cầu: Đếm số miền mà các mặt phẳng đã chia (theo điều kiện của đề bài thì đáp án luôn chỉ có 1).

Input, Output và Subtasks

Input: (bàn phím)
  • Dòng đầu tiên chứa số nguyên dương t (1\le t\le 10^5) - số lượng truy vấn
  • i dòng tiếp theo, dòng thứ i gồm 1 số nguyên dương n(1\le n\le 10^9).
Output: (màn hình)
  • Với mỗi truy vấn in ra đáp án cần tìm. Vì kết quả có thể rất lớn nên ta lấy phần dư của kết quả khi chia cho 10^9+7.
Subtasks
  • Subtask 1 (10\%) n\le 10.
  • Subtask 2 (30\%) n\le 10^3
  • Subtask 3 (20\%) n\le 10^6
  • Subtask 4 (40\%) không có ràng buộc gì thêm.

Sample

Input (bàn phím)
1
3
Output (màn hình)
7
Notes

  • Như các bạn có thể thấy ở hình dưới đây, nếu thỏa mãn các điều kiện trên thì sẽ luôn có 7 miền được chia ra.

Comments

There are no comments at the moment.