CF1835E Old Mobile 题解

纪念一手不看题解切 *3500。

策略很明显:

  • 如果目前不知道哪个键是 backspace:
    • 如果屏幕上显示的数字串完全正确(即,是目标串的一个前缀),并且知道哪个键是接下来要输入的字符,则输入该字符。
    • 否则从不知道是啥的键里面瞎选一个按。如果按到 backspace,则把当前屏幕上的串删到是目标串的一个前缀为止。
  • 如果知道哪个键是 backspace:
    • 屏幕上显示的数字串一定是目标串的一个前缀。
    • 如果知道知道哪个键是接下来要输入的字符,则输入该字符。
    • 否则从不知道是啥的键里面瞎选一个按。如果按错了,立刻按 backspace 删掉。
  • 重复执行,直到输入完成为止。

不难发现只有在某一个字符在目标串中第一次出现的位置的时候,我们会遇到不知道按哪个键的情况。也就是说,将字符按照其第一次出现的位置排序,那么我们只会在极长的包含前 kk 个字符的地方卡住。

cc 为目标串中包含的字符数量,l1,l2,,lcl_1,l_2,\cdots,l_c 为极长的只包含 1,2,,c1,2,\cdots,c 个字符的前缀的长度。

考虑一个 dp。设 fi,j,1/2/3/4f_{i,j,1/2/3/4} 为:

  • 已经输入完成了前 ii 个字符。
  • jj 个字符已经知道键位,但是还没有完成输入。
  • 第三维分别代表:
    1. 不知道 backspace 的键位,当前串是目标串的前缀
    2. 不知道 backspace 的键位,当前串不是目标串的前缀
    3. 知道 backspace 的键位,不确定知不知道下一个字符的键位
    4. 知道 backspace 的键位,确定不知道下一个字符的键位
  • 从当前状态开始,期望完成输入的步数。

考虑转移:

  1. 不知道 backspace 的键位,当前串是目标串的前缀

    • 此时策略一定是在不知道是啥的里面瞎按一个,因为没有 backspace,所以之前一定没有输错过,也就不知道任何除已经输入的字符之外的字符。(也就是说,第三维是 11 的有效状态第二维一定是 00

    • 1mi+1\dfrac{1}{m-i+1} 的概率输入正确的下一个字符。此时会输入接下来知道输入什么的所有字符,算上当前输入的这个有 li+1lil_{i+1}-l_i 个。转移 fi,0,11mi+1(fi+1,0,1+li+1li)f_{i,0,1}\leftarrow \dfrac{1}{m-i+1}(f_{i+1,0,1}+l_{i+1}-l_i)

    • 1mi+1\dfrac{1}{m-i+1} 的概率按到 backspace。此时如果是空串则只多按一次 backspace,否则还要把删的那个按回来。转移 fi,0,11mi+1(fi,0,3+1+[i0])f_{i,0,1}\leftarrow \dfrac{1}{m-i+1}(f_{i,0,3}+1+[i\neq 0])

    • mi1mi+1\dfrac{m-i-1}{m-i+1} 的概率按错。此时当前字符一定会被删去,于是我们直接在这里算上它被删去的代价(也就是一次 backspace)。转移 fi,0,1mi1mi+1(fi,1,2+2)f_{i,0,1}\leftarrow \dfrac{m-i-1}{m-i+1}(f_{i,1,2}+2)

  2. 不知道 backspace 的键位,当前串不是目标串的前缀

    • 在不知道是啥的里面瞎按一个。

    • mijmij+1\dfrac{m-i-j}{m-i-j+1} 的概率没按到 backspace。同理,这个字符一定被删去,所以也把删它用的 backspace 算上。转移 fi,j,2mijmij+1(fi,j+1,2+2)f_{i,j,2}\leftarrow \dfrac{m-i-j}{m-i-j+1}(f_{i,j+1,2}+2)

    • 1mij+1\dfrac{1}{m-i-j+1} 的概率按到 backspace。然后要删掉所有错误的字符,但是因为我们之前已经提前计算过删除的代价,于是这里删除的贡献为 00

    • 现在我们有 jj 种知道但没有完成输入的字符。其中,第一次输入的一种不可能是下一个输入的字符;其余 j1j-1 种,每种都有 1mi1\dfrac{1}{m-i-1} 的概率是下一个输入的字符;还有 mjmi1\dfrac{m-j}{m-i-1} 的概率不知道下一个字符的键位。

    • 转移 fi,j,21mij+1j1mi1fi+1,j1,3f_{i,j,2}\leftarrow \dfrac{1}{m-i-j+1}\cdot \dfrac{j-1}{m-i-1}f_{i+1,j-1,3}fi,j,21mij+1mjmi1fi+1,j,4f_{i,j,2}\leftarrow \dfrac{1}{m-i-j+1}\cdot \dfrac{m-j}{m-i-1}f_{i+1,j,4}

  3. 知道 backspace 的键位,不确定知不知道下一个字符的键位

    • 和 2 中同理,jj 种字符每种都有 1mi\dfrac{1}{m-i} 的概率是下一个输入的字符,还有 mijmi\dfrac{m-i-j}{m-i} 的概率不知道下一个输入的字符。

    • 转移 fi,j,3jmi(fi+1,j1,3+li+1li)f_{i,j,3}\leftarrow \dfrac{j}{m-i}(f_{i+1,j-1,3}+l_{i+1}-l_i)fi,j,3mijmifi,j,4f_{i,j,3}\leftarrow \dfrac{m-i-j}{m-i}f_{i,j,4}

  4. 知道 backspace 的键位,确定不知道下一个字符的键位

    • 在不知道的 mijm-i-j 个键里面瞎按一个。

    • 1mij\dfrac{1}{m-i-j} 的概率按对。转移 fi,j,41mij(fi+1,j,3+li+1li)f_{i,j,4}\leftarrow \dfrac{1}{m-i-j}(f_{i+1,j,3}+l_{i+1}-l_i)

    • mij1mij\dfrac{m-i-j-1}{m-i-j} 的概率按错。此时需要把按错这个删了,并多知道一个键位。转移 fi,j,4mij1mij(fi,j+1,4+2)f_{i,j,4}\leftarrow \dfrac{m-i-j-1}{m-i-j}(f_{i,j+1,4}+2)

边界为:对所有 j,kj,kfc,j,k=0f_{c,j,k}=0。答案为 f0,0,1f_{0,0,1}。总时空复杂度 O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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;
}