Editorial for Bedao Mini Contest 22 - Đếm đi các bạn ơiiii


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: tungvh04, phucsongdonggia

Subtask 1: ~n \le 1000~.

Duyệt mọi cặp số (~i~, ~j~) sao cho ~1 \le i < j \le n~. Nếu ~j - i > 5~ và ~|a_i - a_j|~ chia hết cho ~23~ thì tăng kết quả lên ~1~ đơn vị.

Subtask 2: ~n \le 2 \cdot 10^5~.

Nhận xét: ~|a_i - a_j|~ chia hết cho ~23~ khi và chỉ khi ~a_i \equiv a_j \pmod{23}~.

Ta lưu mảng ~cnt[x]~ với ý nghĩa là số lượng các số chia ~23~ dư ~x~.

Trong khi duyệt tới vị trí ~j~, mảng ~cnt[]~ cần lưu các số có vị trí ~i~ sao cho ~j - i > 5~. Khi vị trí ~j~ tăng dần, các số mà mảng ~cnt[]~ lưu sẽ tăng dần. Vì vậy, ta lưu một con trỏ là vị trí các phần tử đã được thêm vào mảng đếm ~cnt[]~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.