Bình luận

• 
  

  8

  

  KAKOII  đã bình luận lúc 10, Tháng 11, 2024, 0:46

  Sau 2 năm timeskip thì cuối cùng mình cũng AC bài này!!!

• 
  

  4

  

  KAKOII  đã bình luận lúc 10, Tháng 11, 2024, 15:00

  Lời giải:

  Một điều mà ta nhận thấy khi quan sát giới hạn của giá trị trong bài toán chính là việc ~k \le 10~. Từ đây ta có phương hướng giải quyết bài toán:

  Với mỗi các giá trị (~s~, ~k~, ~p~), ta thêm cặp giá trị (~s~, ~k~) tại danh sách add[s] và sub[s + (p - 1) * k].

  Danh sách add[s] chỉ chuỗi diễn đàn mà Dũng bắt đầu tại vị trí s.

  Danh sách sub[s + (p - 1) * k] lưu vị trí diễn dàn cuối cùng của các chuỗi diễn đàn mà Dũng tham gia.

  Nếu ~s + (p - 1) \times k \gt n~ thì có thể bỏ quả việc thêm (~s~, ~k~) vào sub[s + (p - 1) * k].

  Tiếp theo, ta đi qua các diễn đàn từ ~1~ đến ~n~:

  Với mỗi diễn đàn ~i~:

  Với từng cặp (~s~, ~k~) trong add[i], ta tăng lên 1 các biến cnt[k][s % k] với cnt[k][s % k] là số lượng các chuỗi diễn đàn nơi các diễn đàn liên tiếp nhau cách nhau ~k~ diễn đàn và cùng đồng dư với ~s~ qua ~k~.

  Khi này, số lần Dũng tham gia diễn đàn ~i~ sẽ là:

  $$\sum_{k=2}^{10} cnt[k][i \mod k]$$

  Sau khi tính xong số lần Dũng tham gia diễn đàn ~i~, ta giảm đi 1 các biến cnt[k][s % k] theo từng cặp (~s~, ~k~) trong sub[i].

  Việc còn lại là tìm diễn đàn mà Dũng tham gia nhiều nhất.

  Chúc bạn giải được bài này vui vẻ!