Density of subarrays
Contest: Codeforces Round 559 (Div. 1)
Difficulty rating: 3500
Tags: dp, math

Let $$$c$$$ be some positive integer. Let's call an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers $$$c$$$-array, if for all $$$i$$$ condition $$$1 \leq a_i \leq c$$$ is satisfied. Let's call $$$c$$$-array $$$b_1, b_2, \ldots, b_k$$$ a subarray of $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$, if there exists such set of $$$k$$$ indices $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ that $$$b_j = a_{i_j}$$$ for all $$$1 \leq j \leq k$$$. Let's define density of $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$ as maximal non-negative integer $$$p$$$, such that any $$$c$$$-array, that contains $$$p$$$ numbers is a subarray of $$$a_1, a_2, \ldots, a_n$$$.

You are given a number $$$c$$$ and some $$$c$$$-array $$$a_1, a_2, \ldots, a_n$$$. For all $$$0 \leq p \leq n$$$ find the number of sequences of indices $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ for all $$$1 \leq k \leq n$$$, such that density of array $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ is equal to $$$p$$$. Find these numbers by modulo $$$998\,244\,353$$$, because they can be too large.

Input format:
The first line contains two integers $$$n$$$ and $$$c$$$, separated by spaces ($$$1 \leq n, c \leq 3\,000$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, separated by spaces ($$$1 \leq a_i \leq c$$$).

Output format:
Print $$$n + 1$$$ numbers $$$s_0, s_1, \ldots, s_n$$$. $$$s_p$$$ should be equal to the number of sequences of indices $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$ for all $$$1 \leq k \leq n$$$ by modulo $$$998\,244\,353$$$, such that the density of array $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ is equal to $$$p$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
In the first example, it's easy to see that the density of array will always be equal to its length. There exists $$$4$$$ sequences with one index, $$$6$$$ with two indices, $$$4$$$ with three and $$$1$$$ with four.

In the second example, the only sequence of indices, such that the array will have non-zero density is all indices because in other cases there won't be at least one number from $$$1$$$ to $$$3$$$ in the array, so it won't satisfy the condition of density for $$$p \geq 1$$$.

Example input:
4 1
1 1 1 1

Example output:
0 4 6 4 1

Example input:
3 3
1 2 3

Example output:
6 1 0 0

Editorial:
We have some $$$c$$$-array $$$a$$$. Let's find the criterion, that any $$$c$$$-array of length $$$p$$$ is its subsequence. To check that $$$c$$$-array $$$b$$$ is a subsequence of $$$a$$$, we should iterate all elements of $$$b$$$ and take the most left occurrence of this symbol in $$$a$$$, starting from the current moment. Because any $$$c$$$-array should be a subsequence of $$$a$$$ on each step we can take the symbol the most left occurrence of such is the most right. Let's denote the positions, which we have taken on each step $$$l_1, l_2, \ldots, l_p$$$. So if we will look to the array $$$a[l_i+1 \ldots l_{i+1}]$$$, in this arrays each of the $$$c$$$ symbols exists and the symbol $$$a_{l_{i+1}}$$$ occurs exactly $$$1$$$ time. Let's name such array "critical block". So the density of $$$a \geq p$$$, if $$$a$$$ is the concatenation of $$$p$$$ consecutive critical blocks and some other symbols at the end.
Let's note, that the density of any array of length $$$n$$$ won't be more than $$$k = \frac{n}{c}$$$. It is obvious, because in any critical block at least $$$c$$$ symbols.
Let's find $$$dp_{{t},{i}}$$$ as the number of subsequences of the array prefix $$$a[1 \ldots i]$$$ that contain the position $$$i$$$, which are divided into exactly $$$t$$$ critical arrays (and no other characters). We will consider it for all $$$1 \leq t \leq k$$$ and $$$1 \leq i \leq n$$$.
Let's first understand how to get an answer from these values, and then show how to calculate them. If we denote by $$$f_t$$$ the number of subsequences whose density is $$$\geq t$$$, then $$$f_t = \sum\limits_{i=1}^n{dp_ {t},{i}} \cdot 2^{n - i}$$$. Next, note that the number of density subsequences exactly $$$t$$$ is $$$ans_t = f_{t+1} - f_t$$$.
Here are $$$2$$$ different ways to calculate $$$dp_{{t},{i}}$$$:
1) denote by $$$num_{{i},{j}}$$$ the number of subsequences of array $$$a[i \ldots j]$$$ that contain $$$j$$$ and are critical. Then $$$num_{{i},{j}} = \prod\limits_{x=1, x \neq a_j}^{c}{(2^{cnt_{{x},{i},{j}}} - 1)}$$$, where $$$cnt_{{x},{i},{j}}$$$ — is the number of characters $$$x$$$ among $$$a[i \ldots j]$$$. Then we can calculate $$$num$$$ for $$$O(n^2 c)$$$. To speed up this calculation to $$$O(n^2)$$$ we will fix $$$i$$$ and increase $$$j$$$ by $$$1$$$, supporting $$$\prod\limits_{x=1}^{c}{(2^{cnt_{{x},{i},{j}}} - 1)}$$$. Then in such a product $$$1$$$ multiplier will be changed and it can be recalculated by $$$O(1)$$$. To get $$$num_{{i},{j}}$$$, you simply divide the supported product by $$$2^{cnt_{{a_j},{i},{j}}} - 1$$$.
Then note that $$$dp_{{t},{i}} = \sum\limits_{j=0}^{i - 1}{dp_{{t-1},{j}}} \cdot num_{{j+1},{i}}$$$ (iterate over $$$j$$$ — the end of the previous critical block). This allows us to calculate the values of $$$dp$$$ in time $$$O(n^2 k)$$$.
2) We will need an auxiliary dinamical programming values $$$u_{{i},{t},{mask}}$$$ (where $$$mask$$$ is a mask of characters, that is $$$0 \leq mask < 2^c$$$), which means the number of ways to choose a subsequence from the prefix $$$a[1 \ldots i]$$$, in which there will be first $$$t$$$ critical blocks and then several characters that are in $$$mask$$$, but each character from $$$mask$$$ will be at the several symbols at least once. Then $$$dp_{{t},{i}} = u_{{i-1},{t-1},{2^c - 1 - 2^{a_i}}}$$$, which follows from the definition.
Conversion formulas are as follows: $$$u_{{i},{t},{mask}} = u_{{i-1},{t},{mask}}$$$, if $$$a_i$$$ is not contained in $$$mask$$$ and $$$u_{{i},{t},{mask}} = 2 u_{{i-1},{t},{mask}} + u_{{i-1},{t},{mask - 2^{a_i}}}$$$, if $$$a_i$$$ is contained in $$$mask$$$ (if you take $$$a_i$$$ in the subsequence and if not). For $$$mask = 0$$$ it is true, that $$$u_{{i},{t},{0}} = u_{{i-1},{t},{0}} + dp_{{I},{t}}$$$.
These formulas can be used to calculate the values of $$$u$$$ and $$$dp$$$ by iterating $$$i$$$ in increasing order over time $$$O(n k 2^c)$$$. The $$$i$$$ parameter can be omitted from memory because the recalculation is only from the previous layer.
In total, we get $$$2$$$ ways to calculate $$$dp$$$ working for $$$O(n^2 k)$$$ and $$$O(n k 2^c)$$$. Recall that $$$k = \frac{n}{c}$$$. That is, our solutions work at the time $$$O(\frac{n^3}{c})$$$ and $$$O(\frac{n^2 2^c}{c})$$$. If $$$c > \log{n}$$$, then let's run the first solution and it will work for $$$O(\frac{n^3}{\log{n}})$$$, otherwise if $$$c \leq \log{n}$$$ and $$$\frac{2^c}{c} \leq \frac{n}{\log{n}}$$$, so let's run the second solution, which will then work, too, in $$$O(\frac{n^3}{\log{n}})$$$ time.
If we carefully implement these $$$2$$$ solutions and run them depending on $$$c$$$, we get a solution with $$$O(\frac{n^3}{\log{n}})$$$ complexity and it is working fast enough.
Complexity: $$$O(\frac{n^3}{\log{n}})$$$ or $$$O(\frac{n^2}{c} \cdot min(n, 2^c))$$$.