/ Vijos / 题库 /

遗忘的集合

遗忘的集合

描述

小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)~mod~p\) 的值,小Q希望你能利用这些信息帮他恢复出\(S\) 原来的样子。

具体来说,他希望你找到这样一个正整数的非空集合\(S\) ,其中的每个元素都不超过\(n\) ,并且对于任意的\(i = 1,2,\cdots,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),\cdots,f(n)\),含义见题目描述。

保证每一行中相邻的整数由恰好一个空格隔开,并且末尾没有多余的空格。

输出格式

你需要输出两行信息来描述字典序最小的解,其中第一行包含一个整数\(m (m > 0)\) ,表示\(S\) 的元素个数,第二行包含\(m\) 个正整数\(s_1,s_2,\cdots,s_m\),表示将\(S\) 的所有元素按升序排序后得到的序列。你需要保证输出的每一行中相邻的整数由恰好一个空格隔开,并且每一行的末尾没有多余的空格。

样例1

样例输入1

5 1000003
1 2 3 5 7

样例输出1

5
1 2 3 4 5

样例2

样例输入2

9 1000003
1 2 2 3 4 5 6 7 8

样例输出2

3
1 2 5

限制

说明

来源

SDOI 2017 Round2 Day2

信息

ID
2023
难度
8
分类
(无)
标签
递交数
18
已通过
5
通过率
28%
被复制
4
上传者

相关

在下列训练计划中:

RP++分类题库