题目分析

Bessie 使用九键手机，可以一次按下：

• 单个键
• 两个相邻键（12种）
• 四个键形成正方形（4种）

同时按下的键会以任意顺序输入。给定最终输入的序列，求可能的原始电话号码数量。

---

核心思路

1. 状态压缩表示

使用位掩码表示按键组合：

value[i] = (1 << i);  // 数字 i 对应位掩码

例如：数字1=1<<1=2, 数字2=1<<2=4, 数字3=1<<3=8, 等等。

2. 合法按键预处理

预先计算所有合法按键的位掩码：

双键（12种）：

two[6] = 1;      // 1|2 = 2|4 = 6
two[12] = 2;     // 2|3 = 4|8 = 12
// ... 其他10种

四方键（4种）：

do_four(2,4,16,32,1);    // 1245
do_four(4,8,32,64,2);    // 2356  
do_four(16,32,128,256,3);// 4578
do_four(32,64,256,512,4);// 5689

---

算法实现详解

1. 动态规划状态设计

使用 map<array<int,4>, int> 作为DP状态：

• arr[0]：最近4个数字的位掩码（可能形成四方键）
• arr[1]：最近2个数字的位掩码（可能形成双键）
• arr[2]：最近1个数字的位掩码（单键）
• arr[3]：是否完成当前按键（0=完成，-1=未完成）

状态值表示达到该状态的方案数。

2. 状态转移

对于每个位置 i 和每个状态，尝试添加数字 1-9：

for (int j = 1; j <= 9; j++) {
    array<int, 4> tmp;
    tmp[0] = arr[1] | (1 << j);  // 更新最近4位
    tmp[1] = arr[2] | (1 << j);  // 更新最近2位
    tmp[2] = arr[3] | (1 << j);  // 更新最近1位
    tmp[3] = -1;
    
    // 检查是否可以完成按键
    if (可以形成四方键) tmp[3] = 0;
    else if (可以形成双键) tmp[3] = 0;  
    else if (可以形成单键) tmp[3] = 0;
    
    // 验证未来可行性
    if (!OK(tmp[0], 3, pre4(i+1))) tmp[0] = -1;
    if (!OK(tmp[1], 2, pre4(i+2))) tmp[1] = -1;
}

3. 可行性检查函数

inline bool OK(int u, int v, int w) {
    if (__builtin_popcount(u) != v) return 0;  // 位数检查
    if ((u & w) != u) return 0;                // 子集检查  
    if (!four[w]) return 0;                    // 合法性检查
    return 1;
}

4. 前缀计算函数

inline int pre2(int u) {  // 计算前2位的位掩码
    return (1<<(ch[u]-'0')) | (1<<(ch[u-1]-'0'));
}

inline int pre4(int u) {  // 计算前4位的位掩码  
    return (1<<(ch[u]-'0')) | ... | (1<<(ch[u-3]-'0'));
}

---

复杂度分析

• 状态数：由于有效的位掩码组合有限，实际状态数可控
• 转移代价：每个状态尝试9种数字
• 总复杂度：$O(\text{状态数} \times 9 \times n)$，对于 $n \leq 10^5$ 可接受

---

算法标签

主要算法：

• 动态规划
• 状态压缩
• 位运算

相关技术：

• 映射优化（map代替数组）
• 可行性剪枝
• 预处理

---

代码亮点

1. 状态压缩：用位掩码高效表示数字集合
2. 映射DP：使用 map 自动处理稀疏状态
3. 前瞻性验证：检查状态对未来序列的兼容性
4. 预处理优化：预先计算所有合法按键模式

---

总结

这道题通过状态压缩DP巧妙解决了复杂的排列组合问题。核心在于：

• 用位掩码表示数字集合
• 动态维护最近1、2、4个数字的状态
• 及时完成按键并验证未来可行性

算法充分利用了九键键盘的特殊结构，通过精细的状态设计和剪枝优化，高效解决了大规模输入情况下的计数问题。