P3784 [SDOI2017] The Forgotten Set

Little Q posted a bounty on his personal homepage: collect a **non-empty** set $S$ containing only positive integers, each not exceeding $n$, and satisfying some additional conditions. As is well known, for any positive integer $x$ not exceeding $n$, we can easily compute the number of ways $f(x)$ to express $x$ as a sum of elements from $S$. Here, in any representation, each number may be used multiple times, and the order of numbers is ignored. For example, when $S=\{1,2,3,4,5\}$, we can compute $f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 7$. Another example: when $S=\{1,2,5\}$, we can compute $f(4) = 3, f(5) = 4, f(6) = 5, f(7) = 6$. The trouble is that Little Q has forgotten which elements are in $S$. Fortunately, he recorded all the values of $f(i) \bmod p$ on a storage device, and he hopes you can use this information to reconstruct the original $S$. Specifically, he wants you to find a **non-empty** set $S$ of positive integers, each at most $n$, such that for every $i = 1, 2, \cdots , n$, the number of ways to represent $i$ as a sum of elements from $S$ is congruent to $f(i)$ modulo $p$, where $p$ is a prime stored on the device. He guarantees that such an $S$ exists. However, Little Q believes the stored information is not enough to recover a unique $S$; that is, there may be multiple such sets $S$. So he wants the lexicographically smallest one among all solutions. For two different sets $S_1$ and $S_2$ that satisfy the conditions, we say $S_1$ is lexicographically smaller than $S_2$ if and only if there exists a non-negative integer $k$ such that the first $k$ smallest elements of $S_1$ are exactly the same as those of $S_2$, and either $S_1$ has exactly $k$ elements and $S_2$ has at least $(k + 1)$ elements, or both $S_1$ and $S_2$ have at least $(k + 1)$ elements and the $(k + 1)$-th smallest element of $S_1$ is smaller than that of $S_2$.

The first line contains two integers $n$ and $p$, where $p$ is prime. The second line contains $n$ integers $f(1), f(2), \cdots , f(n)$, as defined in the statement. It is guaranteed that in each line adjacent integers are separated by exactly one space, and there is no trailing space at the end of any line.

Output two lines describing the lexicographically smallest solution. The first line contains an integer $m\ (m > 0)$, the number of elements in $S$. The second line contains $m$ positive integers $s_1, s_2, \cdots , s_m$, which are the elements of $S$ sorted in ascending order. You must ensure that in each output line, adjacent integers are separated by exactly one space, and there is no trailing space at the end of any line.

For $100\%$ of the testdata, we have $1 \le n < 2^{18}$, $10^6 \le p < 2^{30}$, $0 \le f(i) < p \ (i = 1, 2, \cdots , n)$.  Translated by ChatGPT 5