← 返回题目列表

Codeforces · 1835/E

E. 旧手机

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

在星舰 U.S.S. 的最新任务中编码员扬·比托夫斯基上尉意外传送到了一颗未知星球的表面。

为了找到回去的路,简发现了一件来自地球古代文明的神器——一种由 Byterola 创建的能够进行星际通话的移动设备。不幸的是,还有另一个问题。尽管简作为人类的代表,对手机号码的旧式表示法了如指掌,但设备键盘上的符号已经完全磨损,肉眼看不见。旧键盘恰好有 $$$m + 1$$$ 按钮,每个数字对应基本 $$$m$$$ 数字系统中的每个数字,还有一个退格按钮,允许用户删除最后写入的数字(如果屏幕上没有写入任何内容,则此按钮不会执行任何操作,但仍算作按下)。

Jan 想与他的工作人员沟通。他需要输入某个数字(也来自基本 $$$m$$$ 数字系统,即从 $$$0$$$ 到 $$$m - 1$$$ 的数字)。他想知道联系美国所需的预计按下按钮次数。编码员。 Jan 总是根据他当前的知识选择最优化的按钮。按钮在按下之前是无法区分的。帮助他!

输入

输入的第一行有两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$2 \le m \le 10^3$$$) — 到 U.S.S. 的号码长度编码器和数值系统的基础。

在下一个和最后一个输入行中,$$$0$$$ 和 $$$m - 1$$$ 之间有 $$$n$$$ 整数:在基本 $$$m$$$ 数字系统中输入的数字。

输出

输出以 $$$1\,000\,000\,007$$$ 为模的预期按钮按下次数。

正式地,令 $$$M = 1\,000\,000\,007$$$。可以证明,答案可以表示为不可约分数 $$$\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}$$$。

示例

输入 #1

1 2
0

输出 #1

666666674

输入 #2

2 3
0 0

输出 #2

916666678

输入 #3

2 3
0 1

输出 #3

500000009

注意

在第一个示例中,键盘上有两个数字($$$0$$$ 和 $$$1$$$)和一个退格按钮。 Jan 无法知道哪个是哪个,所以他随机按了一个。

以 $$$\frac{1}{3}$$$ 的概率,他按下 $$$0$$$ 并成功输入了机组人员的号码。

有概率 $$$\frac{1}{3}$$$,他按下退格键,但什么也没有发生。然后,他以 $$$\frac{1}{2}$$$ 的概率成功按下 $$$0$$$ (完成该过程)。否则,他以 $$$\frac{1}{2}$$$ 的概率输入 $$$1$$$,然后需要用退格键将其删除,然后点击最后一个按钮,该按钮必须是 $$$0$$$。在这种情况下,他需要按下 $$$4$$$ 按钮。

最后,他可能会先按下 $$$1$$$ 按钮,概率也是 $$$\frac{1}{3}$$$。然后,如果他以$$$50\%$$$的机会按下退格键,那么他就已经准备好了,只需要按下最后一个按钮(总共按下3次)。在最坏的情况下,他会先按 $$$0$$$ 按钮,然后需要用退格键将两个按钮删除,然后最后输入数字 $$$0$$$(总共按 5 次)。

我们得到 $$$\frac{16}{6}$$$ 的期望值。 $$$6$$$ 模 $$$1\;000\;000\;007$$$ 的模逆为 $$$166666668$$$,因此 $$$16 \cdot 166666668 = 666666674 \mod \; 1\;000\;000\;007$$$