# 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).