题目重点：用末位是否为6的两状态递推，按照 n=2 得99的示例确认零和较短数字也计入。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 计数范围是整数0≤x<10^n，而非恰好n位正整数；等价于n位补前导零字符串。
- 禁止的是相邻两个十进制6，不是至少出现两次6；606合法。
- n为非负整数，n=0范围仅包含0，返回1；如题面要求n≥1可收紧输入校验。
解题路线
- 状态A表示已构造前缀且末位不是6，B表示末位是6。初始空前缀A=1、B=0，空前缀只作为建数起点，不额外增加整数数量。
- 从任一合法前缀附加0/1/2/3/4/5/7/8/9共9种，得到新A=9(A+B)。附加6只能来自旧A，得到新B=A；来自旧B会生成66，必须排除。
- 一轮递推同时使用旧A和旧B，不能先覆盖A再算B。最后答案A+B，所有长度n补零串和范围内整数一一对应，补零不会凭空产生连续66。
- 也可记总数T_n=9(T_{n−1}+T_{n−2})，n≥2时成立，初值T_0=1、T_1=10；两状态写法更直接解释约束，避免初值或第二项下标写错。
- 若题目改为恰好n位正整数，首位0必须排除。例如n=2仅10..99共90个数，排除66后是89，不能继续答99。任意上界M还需tight状态，不能只按位数返回。
- 一般禁止pattern可把“已经匹配pattern的最长后缀”做有限状态机，再进行digit DP。当前66只需一位记忆，不要为了简单禁串引入指数状态。
手动走一遍
n=1：A=9、B=1，总10。n=2：A=90、B=9，总99。n=3得到981；含66的三位补零串共19个，066..966与660..669各10个，666重叠一次，1000−19=981。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count integers 0 <= x < 10**n without adjacent decimal digits 66.
Use n-digit zero-padded strings, so zero and shorter integers are included.
"""
def count_without_66(n):
if not isinstance(n, int) or isinstance(n, bool) or n < 0:
raise ValueError("nonnegative integer digit length required")
non_six, last_six = 1, 0
for _ in range(n):
non_six, last_six = 9 * (non_six + last_six), non_six
return non_six + last_six
复杂度
执行n次常数个大整数运算；数值位数O(n)，Python任意精度下不能简单把所有运算视为固定机器字成本，总位运算约O(n²)。状态数量O(1)，实际整数存储O(n) bits。只需模答案时可在每次递推取模。
易错点与追问
容易失分的边界
- 把n位正整数与0..10^n−1混淆。
- 先覆盖A导致B引用新状态。
- 禁止两个6而不是相邻66。
- 大答案用32位整数溢出。
继续深挖
- 若禁止666需要几个状态？
- 如何求任意上界M以内的计数？
- 恰好n位正整数如何初始化？
- n极大且取模，怎样用矩阵快速幂？
