andylizf's blog

By andylizf, history, 4 years ago, In English

This is an $$$O(n \log p)$$$ solution to 1312E - Array Shrinking. Here's the code 72870029.

Starting from the most basic case, consider the number of an array with the maximum value $$$v$$$ with location $$$k$$$:

Considering the left side of $$$k$$$, you need to ensure that it monotonically increases before $$$k$$$, so you can choose the number of $$$k-1$$$ from $$$v-1$$$ and arrange them in a row from small to large, which is $$$\tbinom{v-1}{k-1}$$$.

Then consider the right side of $$$k$$$, pick a number, which is the same as one of the left elements, and the number of schemes is $$$k-1$$$; next only need to select the number of $$$n-k-1$$$, which cannot be the same as any of the left elements, so select $$$n-k-1$$$ from $$$v-1- (k-1)$$$, the number of schemes $$$\tbinom{v-1-(k-1)}{n-k-1}$$$. These $$$n-k$$$ numbers can be arranged in a row from large to small, which is $$$(k-1) \times \tbinom{v-1-(k-1)}{n-k-1}$$$.

According to the principle of multiplication, the number of such counts:

$$$ \dbinom{v - 1}{k - 1} \times (k - 1)\times \dbinom{v - 1 - (k - 1)}{n - k - 1} = \frac{(v - 1)!}{(k - 2)! \times (n - k - 1)! \times(v - n + 1)!} = \frac{\prod_{i = v - n + 2} ^ {v - 1} i}{(k - 2)! \times (n - k - 1)!} $$$

Note that the numerator is only related to $$$v$$$. The overall answer can be simplified:

$$$ \sum_{k = 2}^{n} \sum_{v = n - 1}^{m} \frac{\prod_{i = v - n + 2} ^ {v - 1} i}{(k - 2)! \times (n - k - 1)!} = \sum_{k = 2}^{n} \frac{\sum_{v = n - 1}^{m}\prod_{i = v - n + 2} ^ {v - 1} i}{(k - 2)! \times (n - k - 1)!} $$$

After preprocessing the factorial,

Enumerate $$$v$$$ to calculate the numerator $$$\sum_{v = n-1} ^ {m} \prod_ {i = v-n + 2} ^ {v-1} i$$$;

Then enumerate $$$k$$$ and calculate the denominator $$$(k-2)! \times(n-k-1)!$$$.

Complexity $$$O (n \ log P)$$$, where $$$P = 998244353$$$.

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it