PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES
Prefix sums, Dynamic programming
EXPLANATION:
There are two completely different approaches to the problem.
Either one comes up with a characterization of N-tuples with \mu equal to 0 or one comes up with a clever way to compute \mu.
The characterization is involved and has many cases (and the proof is boring), so we will describe the other solution.
First, we begin by developing a bit of theory around the function \mu, then we will go back to the problem.
Some theory about the function \mu.
We will denote with the letters x, y, z some tuples (possibly with different sizes) and with the letters h, k some nonnegative numbers. Given two tuples x, y we denote with \overline{xy} the concatenation of x and y; so if x is an n-uple and y is an m-uple then \overline{xy} is an (n+m)-uple.
A natural number can also be interpreted as a 1-uple, so \overline{xk} denotes the tuple obtained appending k at the end of x.
Given a tuple y, for any tuple x, let
Notice that f_{\emptyset}(x) = [x\text{ is special}] and \mu(y) = f_y(0). Hence, the function f_y is an interpolation between \mu and its Möbius transform.
From the definition, it follows that, for any k\ge 1 and any pair of tuples x, y,
This formula allows us to show, by induction on the size of y, the following properties:
-
If x is not special, f_y(x)=0 for all y.
-
If x is special and its first nonzero element is k, then f_y(x) = f_y(k). In other words, f_y depends only on the first element of x.
Hence, we shall focus on computing f_y(0), f_y(1), f_y(2), \dots, since all other values can be easily obtained from this ones. Thanks to (\ast) and the previous observations, one obtains the following recursive formulas:
- f_{y0}(k) = f_y(k) for any tuple y and any k\ge 0,
- f_{y1}(k) = f_y(1) - f_y(k) for any tuple y and any k\ge 0,
- For any tuple y and any value h\ge 2, let q := f_y(h)-f_y(h-1). The values of f_{yh}(k), for k=0, 1, 2, \dots, are
As a consequence of this recursive formulas, one can show by induction on the size of y that f_y takes only the values {-1,0,1} and, fixed y, f_y cannot take both -1 and 1. In particular, if we know f_y(0), f_y(k-1) (which belong to \{0, 1, -1\}) and k; then the function f_y is uniquely determined.
Back to the problem.
In order to compute \mu(x), one can compute the functions f_{x'}:\N\to\{-1,0,1\} for each prefix x' of y and then conclude thanks to the identity \mu(x) = f_y(0). Thanks to this algorithm for the computation of \mu, one can solve the problem with a dynamic programming approach.
For any tuple x with values in [0, M], f_{x} is encoded by a positive integer in the range [2,M] (that is the last nonzero element of x) and two values in \{0, 1, -1\}. Moreover, the function f_{(x_1, x_2,\dots, x_{n+1})} depends only on x_{n+1} and f_{(x_1, \dots, x_n)}.
For each 0\le n\le N, and for each feasible function g, we compute how many n-uples 0\le x_1, x_2,\dots, x_n\le M are such that f_x \equiv g.
The answer to the problem is the number of N-uples x so that f_x(0)=0.
The number of states is O(NM), the complexity of each transition is O(M), thus the overall complexity is O(NM^2).
SOLUTION
The author’s solution can be found here .