← 返回题目列表

Codeforces · 1371/E1

E1. 星辰(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于 $$$n$$$ 和 $$$a_i$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

首先,葵针对竞争性编程问题提出了以下想法:

柚子是一个收集糖果的女孩。原来,她有$$$x$$$糖果。还有 $$$n$$$ 敌人,编号为从 $$$1$$$ 到 $$$n$$$ 的整数。敌人 $$$i$$$ 有 $$$a_i$$$ 糖果。

柚子将确定一个排列$$$P$$$。排列是由从 $$$1$$$ 到 $$$n$$$ 的任意顺序的 $$$n$$$ 不同整数组成的数组。例如,$$$\{2,3,1,5,4\}$$$ 是一个排列,但 $$$\{1,2,2\}$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$\{1,3,4\}$$$ 也不是排列(因为 $$$n=3$$$ 但数组中有数字 $$$4$$$)。

之后,她将与敌人进行 $$$n$$$ 决斗,规则如下:

- 如果 Yuzu 的糖果数量与敌人 $$$P_i$$$ 相同或更多,她将赢得决斗并获得 $$$1$$$ 糖果。否则,她就输掉了决斗,什么也得不到。
- 柚子得到的糖果将在接下来的决斗中使用。

柚子想赢得所有决斗。存在多少种有效排列$$$P$$$?

这个问题很简单,对于 Aoi 的朋友 Akari 来说并不有趣。 Akari 根据上述想法提出了以下问题:

让我们将 $$$f(x)$$$ 定义为整数 $$$x$$$ 的有效排列数。

给你 $$$n$$$、$$$a$$$ 和一个素数 $$$p \le n$$$。如果值 $$$f(x)$$$ 不能被 $$$p$$$ 整除,我们称正整数 $$$x$$$ 为好。找到所有好的整数$$$x$$$。

你的任务是解决 Akari 提出的这个问题。

输入

第一行包含两个整数 $$$n$$$、$$$p$$$ $$$(2 \le p \le n \le 2000)$$$。可以保证数字 $$$p$$$ 是素数(它恰好有两个约数 $$$1$$$ 和 $$$p$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 2000)$$$。

输出

在第一行中,打印好整数 $$$x$$$ 的数量。

在第二行中,按升序输出所有好的整数$$$x$$$。

保证好整数$$$x$$$的数量不超过$$$10^5$$$。

示例

输入 #1

3 2
3 4 5

输出 #1

1
3

输入 #2

4 3
2 3 5 6

输出 #2

2
3 4

输入 #3

4 3
9 1 1 1

输出 #3

0

注意

在第一个测试中,$$$p=2$$$。

- 如果 $$$x \le 2$$$,则柚子没有有效的排列。所以$$$f(x)=0$$$ 对于所有$$$x \le 2$$$。数字 $$$0$$$ 可以被 $$$2$$$ 整除,因此所有整数 $$$x \leq 2$$$ 都不好。
- 如果 $$$x = 3$$$,则 $$$\{1,2,3\}$$$ 是 Yuzu 的唯一有效排列。所以$$$f(3)=1$$$,所以数字$$$3$$$ 是好的。
- 如果 $$$x = 4$$$,则 $$$\{1,2,3\} 、 \{1,3,2\} 、 \{2,1,3\} 、 \{2,3,1\}$$$ 都是 Yuzu 的有效排列。所以$$$f(4)=4$$$,所以$$$4$$$这个数字不好。
- 如果 $$$x \ge 5$$$,则所有 $$$6$$$ 排列对柚子都有效。所以 $$$f(x)=6$$$ 对于所有 $$$x \ge 5$$$ 来说,所以所有整数 $$$x \ge 5$$$ 都不好。

所以,唯一好的数字是 $$$3$$$。

在第三个测试中,对于所有正整数 $$$x$$$,值 $$$f(x)$$$ 可以被 $$$p = 3$$$ 整除。