TLE-oj Cup Round 11 - Bộ ba khắc hệ
Xem PDF
Nộp bài
Điểm:
2100 (thành phần)
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
TRIHATER.inp
Output:
TRIHATER.out
Tác giả:
Dạng bài
Bạn được cho 6 giá trị l_1,r_1,l_2,r_2,l_3,r_3. Nhiệm vụ của bạn là đếm số bộ ba a_1,a_2,a_3 thỏa mãn:
- l_i\le a_i\le r_i
- a_i&a_j=0 với mọi i\ne j
Trong đó, phép toán & chính là phép toán bit AND. Các bạn có thể xem về các phép thao tác bit tại đây.
Input, Output và Subtasks
Input: (TRIHATER.inp)
- Dòng đầu tiên chứa số t chỉ số testcase (t\le 10^5)
- Sau đó là t dòng, mỗi dòng chứa 6 số l_1,r_1,l_2,r_2,l_3,r_3 (0\le l_i\le r_i\le 10^{18})
Output: (TRIHATER.out)
- Với mỗi testcase, xuất ra kết quả tương ứng. Vì kết quả có thể rất lớn nên hãy xuất kết quả sau khi mod\ 10^9+7
Subtasks
- Subtask 1 (10\%): l_1=r_1=l_2=r_2=0.
- Subtask 2 (10\%): r_i-l_i\le 500,t=1.
- Subtask 3 (10\%): l_1=r_1=0.
- Subtask 4 (15\%): t=1.
- Subtask 5 (15\%): t\le 50.
- Subtask 6 (15\%): t\le 3000.
- Subtask 7 (25\%): Không có giới hạn gì thêm.
Sample
Input (TRIHATER.inp)
2
1 3 0 2 1 4
1 2 0 3 2 4
Output (TRIHATER.out)
7
5
Note
- Testcase 1: Các bộ ba thỏa mãn: (1,0,2);(1,0,4);(1,2,4);(2,0,1);(2,0,4);(2,1,4);(3,0,4)
- Testcase 2: Các bộ ba thỏa mãn: (1,0,2);(1,0,4);(1,2,4);(2,0,4);(2,1,4)
Bình luận