MEGAMU1 - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

MEDIUM

DRAFT EXPLANATION:

Note: The editorial is underway. To not keep you waiting however, the draft editorial of the author is attached below.

Let f(x) := [x \text{ is special}]. We have the following formula for \mu (it can be proven by induction): $$\mu(x) = \sum_{0\le b_i\le 1} (-1)^{\sum b_i} f(x-b) . $$ The sum contains 2^N terms, so it is unfeasible to compute all contributions. But it is not hard to compute such sum with a dynamic programming approach. The overall complexity is O(n).

@infinitepro, could you please add more details to the editorial?