# [SCOI2009] windy数
## problem statement
求十进制数$x$的计数, 满足如下约束
- $a\leq x\leq b$
- 无前导0
- 相邻数位上的数码之差至少为2
## solution
首先, 后两条约束和$a,b$没有关系, 于是, 可以分别求出$1\leq x< a$和$1\leq x\leq b$的范围内的计数, 差分一下.
于是, 现在的约束条件为: $1\leq x\leq n$, $x$无前导$0$, $x$的相邻数位上数码差大于$1$.
### part 1
考虑一个 10-way trie, 表示所有decimal numbers.
它是一个 rooted full 10-ary tree, edges 上面带着 `0,1,2...9` 的weight.
从root到一个leaf的path上的edge weights依次表示最高位到最低位.
我们考虑遍历所有满足$1\leq x\leq n$的叶子的过程中所经过的节点.
某些节点, 其子树被完全遍历, 某些节点, 其子树只被遍历一部分.
> 以4进制下31024为例子
>
> ```plaintext
> 0****
> 1****
> 2****
> 30***
> 3101*
> 31020, 31021, 31022, 31023, 31024
> ```
设$n=\overline{(a_{m-1} a_{m-2} \ldots a_2 a_1 a_0)}_{10}$
我们从最高位开始, 向最低位考虑.
- 对于第$k$位, 若$m-1,m-2\ldots k+1$位上的选择, 分别为$a_{m-1},a_{m-2}\ldots a_{k+1}$,
那么第$k$位只能选择$0,1,2\ldots a_k$
- 若之前至少有一位错开, 那么$k,k-1\ldots 0$位都是可以任意选择的.
### part 2
遍历tire时, 我们需要记录以下信息, 来推断当前数位可以有哪些选择.
1. 是否处于"顶到上界", 即先前的数�
