Bài tập

Chỉ số hấp dẫn của xâu kí tự số \(S\) ứng với số nguyên tố \(p\) là số cặp vị trí khác nhau \(i, j\ (1 \le i \le j \le |S|)\)
thỏa mãn điều kiện: Số được tạo từ các kí tự thứ \(i\) đến kí tự thứ \(j\) của \(S\) chia hết cho \(p\). Chú ý rằng, số tạo được có thể chứa các chữ số \(0\) không có nghĩa ở đầu.

Ví dụ, với xâu \(S = '070070'\) và \(p = 13\) ta có các cặp vị trí: \((1, 1), (1, 5), (1, 6), (2, 5), (2, 6), (3, 3), (3, 4), (4, 4)\) và \((6, 6)\). Như vậy, chỉ số hấp dẫn của \(S\) ứng với \(p = 13\) là \(9\).

Yêu cầu: Cho xâu \(S\) và số nguyên tố \(p\), với mỗi truy vấn trong \(q\) truy vấn có dạng là cặp số \(L, R\), hãy cho biết chỉ số hấp dẫn của xâu được ghép lần lượt các kí tự thứ \(L\) đến kí tự thứ \(R\)
của \(S\).

Input

• Dòng đầu tiên chứa số nguyên tố \(p\ (2 \le p \le 10^9)\).
• Dòng thứ hai chứa xâu \(S\ (|S| \le 10^5)\) chỉ gồm các kí tự \('0'\) đến \('9'\).
• Dòng thứ ba chứa số nguyên \(q\) là số lượng truy vấn \((1 \le q \le 10^5)\).
• Mỗi dòng trong \(q\) dòng sau chứa hai số nguyên \(L\) và \(R\ (1 \le L \le R \le |S|)\).

Output

• Đưa ra thiết bị ra chuẩn \(q\) dòng, mỗi dòng một số nguyên là chỉ số hấp dẫn của xâu tương ứng truy vấn trong dữ liệu vào.

Example

13
070070
3
1 6
2 5
2 2

9
4
0

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|S|, q \le 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(p = 2\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc nào thêm.

Cho một xâu \(s\) độ dài \(n\) chỉ gồm các ký tự Latin in thường (từ a đến z). Có \(q\) truy vấn, mỗi truy vấn cho hai số nguyên \(l\) và \(r\), hãy đếm có bao nhiêu cặp nghịch thế trong xâu con liên tiếp từ \(l\) đến \(r\).

Số cặp nghịch thế là số cặp \(i\), \(j\) sao cho \(i < j\) và ký tự ở vị trí \(i\) nằm sau ký tự ở vị trí \(j\) trong thứ tự từ điển. Ví dụ, xâu beac có \(3\) cặp nghịch thế, đó là \((1, 3)\), \((2, 3)\) và \((2, 4)\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5 \times 10^5)\) là độ dài của xâu.

• Dòng tiếp theo chứa xâu \(s\) có độ dài \(n\) chỉ gồm các ký tự Latin in thường.

• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 5 \times 10^5)\) là số truy vấn.

• Trong \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) \((1 \leq l \leq r \leq n)\) mô tả một truy vấn.

Output

• Gồm \(q\) dòng, mỗi dòng là số cặp nghịch thế của truy vấn tương ứng.

Example

7
adbcedc
4
1 4
3 5
4 7
2 4

2
0
3
2

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^2\).

• Subtask \(2\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^3\).

• Subtask \(3\) (\(25\%\) số điểm): \(n, q \leq 5 \times 10^4\).

• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Cho dãy số nguyên dương gồm \(N\) phần tử \(A_1, A_2, \ldots, A_N\).

Yêu cầu: Đếm số lượng bộ ba số nguyên dương (\(x,y,z\)) thỏa mãn:

• \(0<x<y<z\leq N\);

• \(A_x<A_y\) và \(A_y>A_z\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) (\(N\leq 3*10^5\)).

• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1,A_2,…,A_N\) (\(1\leq a_i\leq 10^{18}\)).

Output

• In ra kết quả bài toán là số lượng bộ ba (\(x,y,z\)) thỏa mãn.

Example

5
0 1 1 0 1

2

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Dãy \(A_i\) không giảm (\(A_i\leq A_j\) với \(i<j\)).

• Subtask \(2\) (\(15\%\) số điểm): \(A_i\in [0,1]\).

• Subtask \(3\) (\(15\%\) số điểm): \(A_i\in [0,100]\).

• Subtask \(4\) (\(15\%\) số điểm): \(N\leq 500\).

• Subtask \(5\) (\(15\%\) số điểm): \(N\leq 10000\).

• Subtask \(6\) (\(15\%\) số điểm): \(A_i\in [0,10^5]\).

• Subtask \(7\) (\(15\%\) số điểm): Không có giới hạn gì thêm.

Là chúa tể của quân đoàn kiến, việc của bạn là sắp xếp quân đoàn của mình phải chiến đấu cùng với nhau. Quân đoàn của bạn có \(N\) chiến binh kiến, chiến binh kiến thứ \(i\) đang ở tọa độ \((X_{i}, Y_{i})\). Muốn quân đoàn kiến sát cánh chiến đấu càng nhau, các chiến binh kiến phải di chuyển sao cho \(N\) chiến binh đứng cùng trên một đường thẳng trên mặt phẳng tọa độ \(Oxy\). Có tối thiểu bao nhiêu chiến binh kiến phải di chuyển để quân đoàn kiến nằm cùng trên một đường thẳng ?

Tất nhiên, do một số lý do cá nhân, bạn không cần thiết phải tìm ra kết quả chính xác, bởi vì số lượng kiến có thể rất lớn. Nếu số lượng tối thiểu các chiến binh kiến phải di chuyển là \(M\), mọi kết quả từ \(M\) đến \(2 \times M\) đều được chấp nhận. Tất nhiên, nếu bạn tìm ra được chính xác \(M\), là một điều rất tốt !

Input

• Dòng đầu tiên là số nguyên \(T\) - số trường hợp cần phải giải quyết.
• \(T\) trường hợp tiếp theo được nhập theo cấu trúc sau đây :
• Dòng đầu tiên là số nguyên dương \(N\) \((1 \leq N \leq 10^6)\) - số lượng chiến binh kiến của quân đoàn.
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(X_{i}, Y_{i}\) \((|X_{i}|, |Y_{i}| \leq 10^9)\).

Tổng \(N\) trong các truy vấn không vượt quá \(10^6\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) là kết quả của trường hợp thứ \(i\).

Example

3
4
1 1
2 2
-3 -3
4 4
4
1 1
-1 1
1 -1
-1 -1
7
4 8
2 4
7 2
6 10
0 1
3 4
4 7

0
2
3

Scoring

• Subtask \(1\) (\(25\%\) số điểm) : tổng \(N\) không vượt quá \(20\).
• Subtask \(2\) (\(25\%\) số điểm) : tổng \(N\) không vượt quá \(300\).
• Subtask \(3\) (\(25\%\) số điểm) : tổng \(N\) không vượt quá \(1000\).
• Subtask \(4\) (\(25\%\) số điểm) : không có ràng buộc gì thêm.