#pvhung: CẶP GHÉP ĐỒ THỊ
Xem PDFCho một số nguyên dương \(m\), chúng ta xác định một đồ thị hai phía không trọng số \(G(m)\) với (\(2m-2\)) đỉnh như sau:
Đồ thị \(G(m)\) là một đồ thị vô hướng có thể được tô màu đen và trắng, với \((m-1)\) đỉnh đen và \((m-1)\) đỉnh trắng. Gọi \(X\) là tập hợp của tất cả các đỉnh đen và \(Y\) là tập hợp của tất cả các đỉnh trắng.
Đặt \(i_X\) đại diện cho điểm với số \(i\) trong tập \(X\), và \(i_Y\) đại diện cho điểm với số \(i\) trong tập \(Y\), với \(1 ≤ i ≤ m-1\). Có một cạnh giữa \(i_X\) và \(j_Y\) khi và chỉ khi ít nhất một trong các điều kiện sau đây thỏa mãn:
- \(i = j\)
- \(i \times j \equiv 1\) \(\pmod {m}\).
Đặt \(f[G(m)]\) là số lượng các cặp ghép tối đa khác nhau cơ bản trong \(G(m)\). Hai cặp ghép được coi là khác nhau cơ bản nếu và chỉ nếu tồn tại \(i_X\) sao cho nó được ghép với \(j_Y\) trong một cách này và không được ghép với \(j_Y\) trong một cách khác.
Cho \(q\) nhóm truy vấn, mỗi nhóm chứa hai số nguyên dương \(l\) và \(r\).
Yêu cầu: với mỗi truy vấn, tìm \(\sum_{i=l}^r f[G(i)]\) modulo \(998244353\).
Input, Output and Scoring
Input (bàn phím)
- Dòng đầu tiên gồm số nguyên \(q\) (\(q\le 10^5\)).
- \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(l\) và \(r\) (\(1\le l\le r\le 10^7\)).
Output (màn hình)
- Với mỗi truy vấn, in ra \(\sum_{i=l}^r f[G(i)]\) modulo \(998244353\).
Scoring
- Subtask \(1\) \((9\%)\): \(q\le 10, l,r\le 100\).
- Subtask \(2\) \((10\%)\): \(l,r\le 1000\).
- Subtask \(3\) \((12\%)\): \(l,r\le 5000\).
- Subtask \(4\) \((13\%)\): \(l,r\le 2\times 10^4\).
- Subtask \(5\) \((15\%)\): \(l,r \le 5\times 10^5\).
- Subtask \(6\) \((18\%)\): \(l,r\le 2\times 10^6\).
- Subtask \(7\) \((23\%)\): không có giới hạn gì thêm.
Test
Input (bàn phím)
5
1 10
5 5
3 4
6 9
10 20
Output (màn hình)
18
2
2
10
455
Bình luận