Codeforces Round 955 Analysis - E | Sojourner’s Stride

type

status

date

slug

summary

1982E - Number of k-good subarrays

Xét dãy số tự nhiên liên tiếp gồm số từ đến , đếm số đoạn con của dãy này mà các số trong đó có số bit 1 . Giải với test. Giới hạn: .

Ý tưởng chính

Nếu ta lấy lớn nhất sao cho , ở vị trí bit , sẽ chỉ gồm 2 đoạn liên tiếp:

Có số đầu tiên có bit thứ .

Có số còn lại có bit thứ .

Gọi với ý nghĩa:

Có số đầu tiên (từ đến ) có bit 1.

Có số cuối cùng (từ đến ) có bit 1.

là đáp án.

Theo như nhận xét trên, việc tính có thể quy về tính và .

Ghép đoạn

Phần này khi luận ra được sẽ thấy khá hiển nhiên. Đặt là số đoạn con của mảng độ dài .

Giả sử kết quả của là và là .

Ta có .

Sau đó, ta tính lại . Ban đầu, ta đặt .

Nếu (tất cả các số trong đoạn đang tính đều thoả có bit 1), thì ta ghép đoạn trước với đầu của đoạn sau, khi đó .

Tương tự, nếu , thì ta ghép đoạn sau với đuôi của đoạn trước, khi đó .

Tối ưu

Thuật toán trên vẫn mất độ phức tạp là . Để tối ưu, ta nhận thấy đối với 2 trường hợp trên:

có thể tính theo và . Biến vẫn là luỹ thừa của 2.

chính là việc bỏ đi bit thứ và tính toán trên các số còn lại với bit, do đó, quá trình đệ quy sẽ dần quay về trường hợp 1.

Từ đó ta thấy rằng, tất cả các tính toán cuối cùng sẽ quy về chỉ cần tính trước các là các trạng thái đặc biệt.

Sau đó với mỗi truy vấn, khi gọi đệ quy, đã được tính trước, trong khi phần còn lại sẽ cũng sẽ giảm 1 nửa theo mỗi bước đệ quy xuống và quy về những phần đã tính trước.

Do đó thời gian cho mỗi test chỉ mất .

Cài đặt: Submission #267482476 - Codeforces

1982E - Number of k-good subarrays

Ý tưởng chính

Ghép đoạn

Tối ưu

⚙️My setup #1 - i use archwsl btw

Hello World!