Contest ôn HSG 9-10 #11

Cho hai số nguyên dương \(n\) và \(k\). Hãy tính tổng các số tự nhiên chia hết cho \(k\) nằm trong đoạn từ \(1\) đến \(n\).

Input

• Dòng duy nhất chứa hai số nguyên dương \(n\) và \(k\).

Output

• Một số nguyên duy nhất là kết quả bài toán.

Example

10 3

18

Scoring

• Subtask 1 (\(70\%\) số điểm): \(n, k \le 10^6\).
• Subtask 2 (\(30\%\) số điểm): \(n, k \le 10^9\).

Quang đang tham gia một trò chơi giải đố mang tên "Mò kim đáy bể". Trong trò chơi, Quang được cung cấp một văn bản rất dài (xâu \(S\)) và một từ khóa bí mật (xâu mẫu \(P\)). Nhiệm vụ của cậu là phải đếm xem từ khóa bí mật đó xuất hiện bao nhiêu lần trong đoạn văn bản đã cho.

Yêu cầu: Cho xâu mẫu \(P\) và xâu văn bản \(S\). Hãy đếm số lần xuất hiện của xâu \(P\) trong xâu \(S\).

Input

Đọc từ tệp văn bản MATCH.INP:

• Dòng đầu tiên chứa xâu mẫu \(P\).
• Dòng thứ hai chứa xâu văn bản \(S\).

(Dữ liệu đảm bảo các xâu chỉ chứa các chữ cái in thường và không có khoảng trắng).

Output

Ghi ra tệp văn bản MATCH.OUT:

• Một số nguyên duy nhất là số lần xâu mẫu \(P\) xuất hiện trong xâu văn bản \(S\).

Example

aba
ababa

2

Scoring

• Subtask 1 (\(40\%\) số điểm): \(|S|, |P| \le 300\).
• Subtask 2 (\(40\%\) số điểm): \(|S|, |P| \le 3000\).
• Subtask 3 (\(20\%\) số điểm): \(|S|, |P| \le 3 \cdot 10^5\).

Quỳnh đang cày hạng Kim cương trong trò chơi Angry Cats. Đội hình mèo của Quỳnh gồm \(n\) con mèo xếp thành một hàng ngang, chú mèo thứ \(i\) có chỉ số dễ thương là \(a_i\). Để vượt qua một ải đặc biệt, hệ thống yêu cầu người chơi phải chọn ra một đội hình gồm đúng ba con mèo nằm ở các vị trí \(i, j, k\) (\(i < j < k\)) sao cho độ dễ thương tổng hợp của chúng cân bằng với một mức \(X\) cho trước, theo công thức: \(a_i - a_j + a_k = X\).

Yêu cầu: Cho mảng \(A\) và số nguyên \(X\). Hãy đếm số lượng bộ ba chỉ số \((i, j, k)\) thỏa mãn \(i < j < k\) và \(a_i - a_j + a_k = X\).

Input

Đọc từ tệp văn bản THREE.INP:

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(X\) (\(1 \le X \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6\)).

Output

Ghi ra tệp văn bản THREE.OUT:

• Một số nguyên duy nhất là số lượng bộ ba thỏa mãn yêu cầu.

Example

4 3
2 3 5 4

1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n \le 500\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 2000\).
• Subtask 3 (\(40\%\) số điểm): \(n \le 7000\).

Nghỉ trưa sau ca trực trên thiên đình, Quan Văn và Quan Vũ cùng nhau chơi cờ. Đang trong thế bí, bất chợt Văn đánh đố Vũ: "Tại hạ có một câu đố cổ như sau. Trên một bàn cờ khổng lồ chia thành lưới ô vuông gồm \(n\) hàng và \(m\) cột. Nếu ta đặt 1 hạt thóc vào ô đầu tiên của hàng thứ nhất, 2 hạt vào ô thứ hai, 4 hạt vào ô thứ ba. Tiếp tục điền hết hàng 1 thì sang hàng 2, hết hàng 2 sang hàng 3... và tới cuối cùng là hàng thứ \(n\); sao cho ô tiếp theo luôn có số hạt thóc gấp đôi số lượng đặt vào ô trước đó. Dưới hạ giới nghiên cứu bài toán này 200 năm qua nên đã tính được tổng số hạt thóc trên bàn cờ này rồi, khà khà! Nhưng, Quan Vũ ngươi có tính được tổng số hạt thóc nằm trên cột thứ \(c\) là bao nhiêu không?". Vũ rơi vào trầm tư, trong thoáng chốc đã hết buổi chiều. Hắn buồn bực, hất đổ bàn cờ. "Cho ta 3 ngày, ta sẽ quay lại với đáp án chính xác". Thế là hắn đạp mây xé gió, bay xuống hạ giới, tới kỳ thi chọn HSG 9 của thành phố Đà Nẵng, nơi có rất nhiều tài năng toán học và lập trình để cầu cứu.

Yêu cầu: Cho \(n, m\) và \(c\). Hãy tính tổng số hạt thóc nằm trên toàn bộ cột thứ \(c\) của bàn cờ. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho \(10^9+7\).

Input

Đọc từ tệp văn bản CHESS.INP:

• Một dòng duy nhất chứa ba số nguyên dương \(n, m\) và \(c\) (\(1 \le c \le m\)).

Output

Đọc ra tệp văn bản CHESS.OUT:

• Một số nguyên duy nhất là kết quả của bài toán chia lấy dư cho \(10^9+7\).

Example

3 3 2

146

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n, m \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^5, m \le 10^{18}\).
• Subtask 3 (\(40\%\) số điểm): \(n \le 10^{18}, m \le 10^{18}\).