Series ℍ𝔾𝔹ℂ𝕡𝕡_'s - Tìm 𝓒𝓸𝓭𝓮𝓻 Tài năng nhất LQDOJ #01

Một ngày ở trên lớp của algorit của p2o2HuaGiaBao. Anh ta cảm thấy kiệt sức vô cùng sau cả nghìn bài tập về đồ thị phải làm. Bổng nhiên em hàng xóm, hỏi cậu ấy một bài code khó, nhưng anh ta không muốn làm gì thêm nữa nên đành nhờ các bạn hướng dẫn em nó. Đề bài như sau: Cho một xâu \(S\) có độ dài \(|S|\). Hãy cho biết xâu này có phải là xâu chỉ có thể có tối đa một thao tác để biến nó thành xâu đối xứng. Xâu chỉ gồm cái kí tự chữ cái in thường và chữ số (đúng cùng nhau).
Định nghĩa:

• Xâu đối xứng là xâu viết từ trái sang phải và ngược lại đều như nhau. Ví dụ: abcba hay level còn 123 hay meomeo là không phải.
• Một thao tác là khi ta thay đổi chính xác \(1\) kí tự trong xâu

Input

• Gồm một dòng duy nhất là một xâu \(S\)
• \(1\le |S|\le 2\times 10^5\)

Output

• In ra YES nếu phải còn NO nếu không.

Example

abbc

YES

12a45

NO

Sau khi p2o2HuaGiaBao đi xem phim chiếu rạp nhân dịp \(30/4\), anh ta nhớ mãi đến cái tháp ô vuông được đặt trước cửa rạp chiếu phim. Ngoài ra, anh ta đã nhận thấy như sau: Có một tháp các ô vuông bằng nhau có hình dạng giống một tam giác cân. Các hàng tính từ trên xuống dưới có số ô vuông lần lượt là \(1, 3, 5, 7,...\). Một tháp ô vuông có \(n\) hàng gọi là tháp ô vuông bậc \(n\) (\(n \in \mathbb{N}^*\)). Ví dụ ở hình vẽ trên ta có một tháp ô vuông bậc \(3\).

Yêu cầu: Cho trước một tháp ô vuông bậc \(n\). Hãy đếm xem trong tháp ô vuông này có tất cả bao nhiêu hình vuông tạo thành từ các ô vuông đó.

Input:

• Gồm một số tự nhiên \(n\) (\(1\le n \le 10^{7}\)).

Output:

• Ghi số tự nhiên \(m\) là số lượng hình vuông đã đếm theo yêu cầu. Vì kết quả có thể rất lớn nên cần chú ý chia lấy dưa cho \(10^9+7\).

Example

3

11

Scoring

• Subtask 1 (\(50\)% points): \(1 \le n \le 10^3\)
• Subtask 2 (\(50\)% points): Không có ràng buộc gì thêm

Tại Đại Học Công Nghệ nổi tiếng \(Combinatoria\) có giáo sư p2o2HuaGiaBao đang giảng lý thuyết quan trọng về tổ hợp như sau:

• \(C^{n}_k = \frac{n!}{k!\times (n-k)!}\), công thức này áp dụng để tính số lượng hoán vị để chọn \(k\) vật từ \(n\) vật phân biệt. (Chú ý: Mỗi hoán vị chỉ thay đổi thứ tự được coi là giống nhau)
• \(P^{n}_k = \frac{n!}{(n-k)!}\), công thức này áp dụng để tính số lượng hoán vị để chọn \(k\) vật từ \(n\) vật phân biệt. (Chú ý: Mỗi hoán vị chỉ thay đổi thứ tự được coi là khác nhau)

Giáo sư này giao một bài tập cho học sinh rằng:

Đếm bộ \(3\) số khác nhau trong các số liên tiếp từ \(l\) đến \(r\) sao cho tổng của \(3\) số đó chia hết cho \(3\) trong \(Q\) truy vấn.
Vì kết quả có thể rất lớn nên mỗi kết quả phải chia lấy dư cho \(10^9 + 7\).

Vì bài tập tập này quá khó nên cần các bạn giúp đỡ ngay.

Input

• Dòng \(1\) là một số nguyên dương \(Q\) (\(1\le Q\le 10^{6}\))
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(l\) và \(r\) (\(1\le l\le r \le 10^{18}\)) cách nhau bởi một khoảng cách.

Output

• Gồm \(Q\) dòng, mỗi dòng là kết quả cho mỗi truy vấn tương ứng.

Example

1
1 10

42

Scoring

• Subtask 1 (\(25\)% points): \(1 \le l\le r \le 10^2\) và \(1\le Q\le 1\)
• Subtask 2 (\(25\)% points): \(1 \le l\le r \le 10\) và \(1\le Q\le 10^5\)
• Subtask 3 (\(25\)% points): \(1 \le l\le r \le 10^{5}\) và \(1\le Q\le 10^5\)
• Subtask 4 (\(25\)% points): Không có ràng buộc gì thêm.

Một này Chủ Nhật đẹp trời nọ, p2o2HuaGiaBao đang dẫn đội tuyển rubik tham dự một giải đấu Rubik với phong cách "ao làng" như sau: Có \(n\) bàn thi đấu được xếp thành một hàng ngang, bàn thứ \(i\) có \(a_i\) khối Rubik đang chờ được giải. Đội tuyển của p2o2HuaGiaBao có \(m\) tuyển thủ sẵn sàng tham gia để dọn sạch toàn bộ số Rubik này.
Lúc bắt đầu (giây \(0\)), tất cả tuyển thủ đều đứng ở ngoài cùng bên trái bàn số \(1\). Mỗi giây, mỗi tuyển thủ có thể thực hiện một trong hai thao tác sau:

• Nếu chưa ở bàn cuối (\(i \ne n\)), di chuyển từ bàn \(i\) sang bàn \(i+1\).
• Nếu tại bàn hiện tại vẫn còn khối Rubik, giải xong một khối Rubik tại bàn đó.
  Các tuyển thủ có thể hoạt động song song, nhưng mỗi thao tác đều mất đúng \(1\) giây cho mỗi thao tác. p2o2HuaGiaBao muốn biết thời gian tối thiểu \(t\) (tính theo giây) để toàn bộ Rubik ở các bàn được giải xong.
  Vì anh ta đã lớn tuổi nên muốn các bạn tính giúp.

Input

• Dòng đầu tiên chứa hai số nguyên \(n,m\) (\(1\le n,m\le 10^5\)) – lần lượt số bàn thi đấu và số tuyển thủ.
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) với (\(0\le a_i\le 10^9\)) với \(a_i\) là số lượng khối Rubik trên bàn thứ \(i\) (\(1\le i\le n\))

Output

• In ra một số tự nhiên \(t\in \mathbb{N}\) duy nhất – thời gian tối thiểu (tính theo giây) để dọn sạch tất cả các khối Rubik.

Example

5 3
0 3 2 1 8 

10

Scoring

• Subtask 1 (\(25\)% points): \(1 \le n,m,a_i \le 10\)
• Subtask 2 (\(25\)% points): \(1 \le n \le 10^5, m=1, a_i=10^9\)
• Subtask 3 (\(25\)% points): \(1 \le n,m \le 2000, a_i=10^6\)
• Subtask 4 (\(25\)% points): Không có ràng buộc gì thêm