4293: 「SDOI2017」遗忘的集合
内存限制：512 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
小 Q 在他的个人主页上放出了一个悬赏：征集只含正整数的**非空**集合 $S$，其中的每个元素都不超过 $n$，并且满足一些附加条件。
众所周知，我们可以很轻松地对于任意不超过 $n$ 的正整数 $x$，计算出把 $x$ 表示成 $S$ 中元素之和的方案数 $f(x)$，在这里我们约定，在任意方案中每个数字可以出现多次，但是不考虑数字出现的顺序。
例如，当 $S = \{1,2,3,4,5\}$ 时，我们可以计算出 $f(2) = 2$，$f(3) = 3$，$f(4) = 5$，$f(5) = 7$。
再例如，当 $S = \{1,2,5\}$ 时，我们可以计算出 $f(4) = 3$，$f(5) = 4$，$f(6) = 5$，$f(7) = 6$。
麻烦地是现在小 Q 忘记了 $S$ 里有哪些元素，幸运地是他用存储设备记录下了所有 $f(i) \bmod p$ 的值，小 Q 希望你能利用这些信息帮他恢复出 $S$ 原来的样子。
具体来说，他希望你找到这样一个正整数的**非空**集合 $S$，其中的每个元素都不超过 $n$，并且对于任意的 $i = 1,2,··· ,n$，满足把 $i$ 表示成 $S$ 中元素之和的方案数在模 $p$ 意义下等于 $f(i)$，其中 $p$ 是记录在存储设备中的一个质数。他向你保证：**一定存在**这样的集合 $S$。
然而，小 Q 觉得他存储的信息并不足以恢复出唯一的 $S$，也就是说，可能会存在多个这样的集合 $S$，所以小 Q 希望你能给出所有解中**字典序**最小的解。
对于满足条件的两个不同的集合 $S_1$ 和 $S_2$，我们认为 $S_1$ 的字典序比 $S_2$ 的字典序小，当且仅当存在非负整数 $k$，使得 $S_1$ 的前 $k$ 小元素与 $S_2$ 的前 $k$ 小元素完全相等，并且，要么 $S_1$ 的元素个数为 $k$，且 $S_2$ 的元素个数至少为 $(k+1)$，要么 $S_1$ 和 $S_2$ 都有至少 $(k+1)$ 个元素，且 $S_1$ 的第 $(k+1)$ 小元素比 $S_2$ 的第 $(k+1)$ 小元素小。
输入
第一行包含两个整数 $n$ 和 $p$，满足 $p$ 是质数。
第二行包含 $n$ 个整数 $f(1), f(2), \dots , f(n)$，含义见题目描述。
保证每一行中相邻的整数由恰好一个空格隔开，并且末尾没有多余的空格。
输出
你需要输出两行信息来描述字典序最小的解，其中第一行包含一个整数 $m (m > 0)$，表示 $S$ 的元素个数，第二行包含 $m$ 个正整数 $s_1, s_2, \dots , s_m$，表示将 $S$ 的所有元素按升序排序后得到的序列。
你需要保证输出的每一行中相邻的整数由恰好一个空格隔开，并且每一行的末尾没有多余的空格。
样例输入 复制
5 1000003
1 2 3 5 7样例输出 复制
5
1 2 3 4 5提示
输入样例2
9 1000003 1 2 2 3 4 5 6 7 8
输出样例2
3 1 2 5
数据范围：对于 $100\%$ 的数据，有 $1 \leq n < 2^{18}$，$10^6 \leq p < 2^{30}$，$0 \leq f(i)