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

$1\le n \le 5000$ .

Consider a subset

b

of array

a

. Assume that the maximum value in

b

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.

|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

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 MiniLongfor the proof part.

Solution to CF1992G Ultra-Meow

文章操作

相关推荐

评论

Solution to CF1992G Ultra-Meow