MEGAMU2 - Editorial

PROBLEM LINK:

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

DIFFICULTY:

MEDIUM-HARD

DRAFT EXPLANATION:

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

There are two possible solutions to the problem. Either one comes up with a precise characterization of N-tuples with \mu equal to 0 or one comes up with a clever way to compute \mu. The characterization is very involved and has many cases, so we will describe the other solution. Let f_y(x):= \sum_{d\le x} \mu(yd). Notice that \mu(y) = f_y(0). It is not hard to show f_y(kx)-f_y((k-1)x) = f_{yk}(x) for any k\ge 1. One can now prove by induction on y that:

  • f_y(x)=0 if x is not special.

  • if x is special, f_y(x) depends only on the first element of x. Therefore, we can write down the values of f_{yk}(x) when x is a nonnegative integer: $$f_{y0}(x) = f_y(x) ,$$ $$f_{y1}(x) = f_y(1) - f_y(x), $$ and if k\ge 2 the values of f_{yk} are $$f_y(k)-f_y(k-1), 0, 0, \dots, 0, -f_y(k-1), f_y(k)-f_y(k-1), f_y(k)-f_y(k-1), \dots,$$ where the zeroes are repeated k-2 times. One can show by induction on y that f_y takes only the values {-1,0,1} and, fixed y, f_y cannot take both -1 and 1. Thus, to compute \mu(y) = f_y(0), one can compute the functions f_{y'}:\N\to\{-1,0,1\} for each prefix y' of y. Notice that the function f_{y'} is encoded by a positive integer in the range [2,M] (denoted with k above) and 4 boolean values. So, we can compute how many N-uples have \mu equal to 0 with a dynamic programming solution which has O(NM) states and O(NM^2) transitions. So, the overall complexity is O(NM^2).