### andylizf's blog

By andylizf, history, 17 months ago, 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$.  Comments (0)