← 返回题目列表

Codeforces · 1575/F

F. 寻找期望值

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

Chanek 先生打开了一封来自他目前在 Singanesia 学习的同事的来信。这是它所说的。

用 $$$n$$$ 整数定义数组 $$$b$$$ ($$$0 \leq b_i < k$$$)。当存在一对 $$$(i, j)$$$ 使得 $$$b_i \ne b_j$$$ 时,执行以下操作:

- 随机选择一个数字 $$$i$$$ 满足 $$$0 \leq i < n$$$。请注意,每个数字 $$$i$$$ 被选中的概率为 $$$\frac{1}{n}$$$。
- 随机选择一个数字 $$$j$$$ 满足 $$$0 \leq j < k$$$。
- 将 $$$b_i$$$ 的值更改为 $$$j$$$。 $$$b_i$$$ 可以更改为相同的值。

将 $$$f(b)$$$ 表示为对 $$$b$$$ 执行的预期操作数,直到 $$$b$$$ 的所有元素都相等。

给定两个整数 $$$n$$$ 和 $$$k$$$,以及一个由 $$$n$$$ 整数组成的数组 $$$a$$$ ($$$-1 \leq a_i < k$$$)。

对于 $$$a_i = -1$$$ 的每个索引 $$$i$$$,将 $$$a_i$$$ 替换为满足 $$$0 \leq j < k$$$ 的随机数 $$$j$$$。令$$$c$$$ 为$$$-1$$$ 在$$$a$$$ 中出现的次数。替换后有 $$$k^c$$$ 种可能性 $$$a$$$,每种可能性都是最终数组。

求 $$$f(a)$$$ 模 $$$10^9 + 7$$$ 的期望值。

正式地,令 $$$M = 10^9 + 7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

读完信后,查内克先生把任务交给了你。为了他们的友谊,解决这个问题!

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 10^9$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i < k$$$)。

输出

输出一个整数,表示 $$$f(a)$$$ 模 $$$10^9 + 7$$$ 的期望值。

示例

输入 #1

2 2
0 1

输出 #1

2

输入 #2

2 2
0 -1

输出 #2

1

输入 #3

3 3
0 1 1

输出 #3

12

输入#4

3 3
-1 -1 -1

输出#4

11

输入 #5

10 9
-1 0 -1 1 1 2 2 3 3 3

输出 #5

652419213