题解 CF1835E Old Mobile
纪念一手不看题解切 *3500。
策略很明显：
- 如果目前不知道哪个键是 backspace：
- 如果屏幕上显示的数字串完全正确（即，是目标串的一个前缀），并且知道哪个键是接下来要输入的字符，则输入该字符。
- 否则从不知道是啥的键里面瞎选一个按。如果按到 backspace，则把当前屏幕上的串删到是目标串的一个前缀为止。
- 如果知道哪个键是 backspace：
- 屏幕上显示的数字串一定是目标串的一个前缀。
- 如果知道知道哪个键是接下来要输入的字符，则输入该字符。
- 否则从不知道是啥的键里面瞎选一个按。如果按错了，立刻按 backspace 删掉。
- 重复执行，直到输入完成为止。
不难发现只有在某一个字符在目标串中第一次出现的位置的时候，我们会遇到不知道按哪个键的情况。也就是说，将字符按照其第一次出现的位置排序，那么我们只会在极长的包含前
设
考虑一个 dp。设
- 已经输入完成了前
i 个字符。 - 有
j 个字符已经知道键位，但是还没有完成输入。 - 第三维分别代表：
- 不知道 backspace 的键位，当前串是目标串的前缀
- 不知道 backspace 的键位，当前串不是目标串的前缀
- 知道 backspace 的键位，不确定知不知道下一个字符的键位
- 知道 backspace 的键位，确定不知道下一个字符的键位
- 从当前状态开始，期望完成输入的步数。
考虑转移：
-
不知道 backspace 的键位，当前串是目标串的前缀
-
此时策略一定是在不知道是啥的里面瞎按一个，因为没有 backspace，所以之前一定没有输错过，也就不知道任何除已经输入的字符之外的字符。（也就是说，第三维是
1 的有效状态第二维一定是0 ） -
有
\dfrac{1}{m-i+1} 的概率输入正确的下一个字符。此时会输入接下来知道输入什么的所有字符，算上当前输入的这个有l_{i+1}-l_i 个。转移f_{i,0,1}\leftarrow \dfrac{1}{m-i+1}(f_{i+1,0,1}+l_{i+1}-l_i) 。 -
有
\dfrac{1}{m-i+1} 的概率按到 backspace。此时如果是空串则只多按一次 backspace，否则还要把删的那个按回来。转移f_{i,0,1}\leftarrow \dfrac{1}{m-i+1}(f_{i,0,3}+1+[i\neq 0]) 。 -
有
\dfrac{m-i-1}{m-i+1} 的概率按错。此时当前字符一定会被删去，于是我们直接在这里算上它被删去的代价（也就是一次 backspace）。转移f_{i,0,1}\leftarrow \dfrac{m-i-1}{m-i+1}(f_{i,1,2}+2) 。
-
-
不知道 backspace 的键位，当前串不是目标串的前缀
-
在不知道是啥的里面瞎按一个。
-
有
\dfrac{m-i-j}{m-i-j+1} 的概率没按到 backspace。同理，这个字符一定被删去，所以也把删它用的 backspace 算上。转移f_{i,j,2}\leftarrow \dfrac{m-i-j}{m-i-j+1}(f_{i,j+1,2}+2) 。 -
有
\dfrac{1}{m-i-j+1} 的概率按到 backspace。然后要删掉所有错误的字符，但是因为我们之前已经提前计算过删除的代价，于是这里删除的贡献为0 。 -
现在我们有
j 种知道但没有完成输入的字符。其中，第一次输入的一种不可能是下一个输入的字符；其余j-1 种，每种都有\dfrac{1}{m-i-1} 的概率是下一个输入的字符；还有\dfrac{m-j}{m-i-1} 的概率不知道下一个字符的键位。 -
转移
f_{i,j,2}\leftarrow \dfrac{1}{m-i-j+1}\cdot \dfrac{j-1}{m-i-1}f_{i+1,j-1,3} ，f_{i,j,2}\leftarrow \dfrac{1}{m-i-j+1}\cdot \dfrac{m-j}{m-i-1}f_{i+1,j,4} 。
-
-
知道 backspace 的键位，不确定知不知道下一个字符的键位
-
和 2 中同理，
j 种字符每种都有\dfrac{1}{m-i} 的概率是下一个输入的字符，还有\dfrac{m-i-j}{m-i} 的概率不知道下一个输入的字符。 -
转移
f_{i,j,3}\leftarrow \dfrac{j}{m-i}(f_{i+1,j-1,3}+l_{i+1}-l_i) ，f_{i,j,3}\leftarrow \dfrac{m-i-j}{m-i}f_{i,j,4} 。
-
-
知道 backspace 的键位，确定不知道下一个字符的键位
-
在不知道的
m-i-j 个键里面瞎按一个。 -
有
\dfrac{1}{m-i-j} 的概率按对。转移f_{i,j,4}\leftarrow \dfrac{1}{m-i-j}(f_{i+1,j,3}+l_{i+1}-l_i) 。 -
有
\dfrac{m-i-j-1}{m-i-j} 的概率按错。此时需要把按错这个删了，并多知道一个键位。转移f_{i,j,4}\leftarrow \dfrac{m-i-j-1}{m-i-j}(f_{i,j+1,4}+2) 。
-
边界为：对所有
const int N = 1000005, M = 1005;
const long long mod = 1000000007;
int n, m, l[M], a[N], vis[M], cnt;
long long f[M][M][5], inv[M];
inline void Read() {
n = qread(); m = qread();
for (int i = 1;i <= n;i++) {
int x = qread();
if (!vis[x]) {
l[cnt] = i - 1;
vis[x] = ++cnt;
}
a[i] = vis[x];
}
l[cnt] = n;
}
inline void Add(long long &x, long long y) {
x = (x + y >= mod ? x + y - mod : x + y);
}
inline void Solve() {
inv[1] = 1;
for (int i = 2;i <= m + 1;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for (int i = cnt - 1;i >= 0;i--) {
for (int j = m - i;j >= 0;j--) {
if (m - i - j) {
Add(f[i][j][4], (f[i + 1][j][3] + l[i + 1] - l[i]) * inv[m - i - j] % mod);
Add(f[i][j][4], (f[i][j + 1][4] + 2) * inv[m - i - j] % mod * (m - i - j - 1) % mod);
}
if (j) Add(f[i][j][3], (f[i + 1][j - 1][3] + l[i + 1] - l[i]) * inv[m - i] % mod * j % mod);
Add(f[i][j][3], f[i][j][4] * (m - i - j) % mod * inv[m - i] % mod);
Add(f[i][j][2], f[i][j][4] * (m - i - j) % mod * inv[m - i - 1] % mod * inv[m - i - j + 1] % mod);
if (j) Add(f[i][j][2], (f[i + 1][j - 1][3] + l[i + 1] - l[i]) * (j - 1) % mod * inv[m - i - 1] % mod * inv[m - i - j + 1] % mod);
Add(f[i][j][2], (f[i][j + 1][2] + 2) * (m - i - j) % mod * inv[m - i - j + 1] % mod);
if (j == 0) {
Add(f[i][0][1], (f[i + 1][0][1] + l[i + 1] - l[i]) * inv[m - i + 1] % mod);
Add(f[i][0][1], (f[i][0][3] + 1 + (i != 0)) * inv[m - i + 1] % mod);
Add(f[i][0][1], (f[i][1][2] + 2) * (m - i - 1) % mod * inv[m - i + 1] % mod);
}
}
}
cout << f[0][0][1] << endl;
}