# MEGAMU1 - Editorial

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