CF1835E Old Mobile

在星舰 U.S.S. Coder 的最新任务中，舰长 Jan Bitovsky 不小心被传送到了一个未知星球的表面。 为了寻找回去的路，Jan 发现了地球古代文明的遗物——一部由 Byterola 制造、能够进行星际通话的移动设备。不幸的是，还有另一个问题。尽管 Jan 作为人类代表，完全掌握了旧式手机号码的记法，但设备键盘上的符号已经完全磨损，肉眼无法辨认。旧式键盘恰好有 $m+1$ 个按键，分别对应 $m$ 进制数的每一个数字（从 $0$ 到 $m-1$），以及一个退格键（backspace），允许删除最后输入的一个数字（如果屏幕上没有内容，则该键无效，但按下次数仍然计入）。 Jan 想要与船员取得联系。他需要输入一个特定的数字（同样是 $m$ 进制，即每位数字在 $0$ 到 $m-1$ 之间）。他想知道，为了联系 U.S.S. Coder，期望需要按多少次按键。Jan 总是根据当前已知信息选择最优的按键。所有按键在按下之前无法区分。请帮助他！

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$2 \le m \le 10^3$），分别表示要输入的号码长度和数字系统的进制。 接下来一行包含 $n$ 个整数，范围在 $0$ 到 $m-1$ 之间，表示需要输入的号码（以 $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}$。

在第一个样例中，键盘上有两个数字（$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 \bmod 1\,000\,000\,007$。 由 ChatGPT 4.1 翻译