Solution to CF1992G Ultra-Meow

· · 题解

Let \textrm{MEX}(S, k) be the k-th positive integer in ascending order that is not present in S.

Denote \textrm{MEOW}(a) as the sum of \textrm{MEX}(b, |b| + 1) over all distinct subsets b of array a.

Given an array a of length n, consisting of 1,2,\dots, n. Determine the value of \textrm{MEOW}(a).

Consider a subset b of array a. Assume that the maximum value in b is m, and there are exactly x numbers < m that are not present in b. We have

\begin{gather*} m - x = |b| \\ \textrm{MEX}(b, |b| + 1) = \textrm{MEX}(b, m - x + 1) \end{gather*}

For convenience, let T = \operatorname{MEX}(b, m - x + 1). We now distinguish between two cases.

If |b| + 1 = m - x + 1 > x, i.e. m \ge 2x, then T > m holds, which implies that

\begin{aligned} T = m + |b| + 1 - x = 2m - 2x + 1 \end{aligned}

Thus, for fixed m and x, their contribution to the final answer is

(2m - 2x + 1)\binom{m - 1}{x}

Otherwise, m < 2x, and T < m holds.

Since T is undetermined, we can simply enumerate all possible values of T from 1 to m - 1.

Consider the current T, which is the (m-x+1)-th integer that is not present. Hence, there are m-x integers \in [1, T) and 2x-m-1 integers \in (T, m) which are not present.

Thus, for fixed m and x, their contribution to the final answer is

\begin{aligned} &\sum_{T=1}^{m-1}T\binom{T-1}{m - x}\binom{m - 1 - T}{2x-m-1}\\ = &\sum_{T=1}^{m-1}(m-x+1)\binom{T}{m-x+1}\binom{m-1-T}{2x-m-1}\\ = &(m-x+1)\binom{m}{x + 1} \end{aligned}

where the combinatorial identity

\sum_{k=0}^n\binom{k}{a}\binom{n-k}{b} = \binom{n+1}{a+b+1}

is applied.

Proof.

\begin{aligned} &\sum_{k=0}^n \binom{k}{a}\binom{n-k}{b} \\ =& \sum_{k=0}^n \binom{k}{k-a}\binom{n-k}{b} \\ =& \sum_{k=0}^n (-1)^{k-a}\binom{-a-1}{k-a}(-1)^{n-k-b}\binom{-b-1}{n-k-b} \\ =& (-1)^{n-a-b}\sum_{k=0}^n \binom{-a-1}{k-a}\binom{-b-1}{n-k-b} \\ =& (-1)^{n-a-b}\binom{-a-b-2}{n-a-b} \\ =& \binom{n+1}{n-a-b} \\ =& \binom{n+1}{a+b+1} \\ \blacksquare \end{aligned}

We can obtain the answer by iterating m and x, and combining the contributions from the two cases.

The final answer is

\boxed{\sum_{i=1}^n\left( \sum_{j=0}^{\left\lfloor \frac{i}{2} \right\rfloor} (2i-2j+1)\binom{i-1}{j} + \sum_{j=\left\lfloor \frac{i}{2} \right\rfloor + 1}^{i-1}(i-j+1)\binom{i}{j+1} \right)}

Time complexity: \Theta(n^2) per testcase.

Credit to @MiniLong for the proof part.