这sb的硬币机制，此处省略114514句脏话

核心思路

​状态定义​： a[i]：i位数中包含偶数个3的数的个数。 b[i]：i位数中包含奇数个3的数的个数。

​递推关系​： ​非最高位​：每位可选0-9，分两种情况： 当前位非3：

a[i] += a[i-1] * 9

b[i] += b[i-1] * 9 当前位是3：

a[i] += b[i-1] * 1

b[i] += a[i-1] * 1 ​最高位​：不能为0，需特殊处理： 非3时可选1-9中除3的8种：

a[n] += a[n-1] * 8

是3时仅1种：

a[n] += b[n-1] * 1

​边界条件​： a[1] = 9（0-9中除3的9个数）

b[1] = 1（仅数字3）

详细的递推公式： $a[i] = (a_{i-1}*x+b_{i-1}*1)$

$b[i] = (b_{i-1}*x+a_{i-1}*1)$

注：x在不为最高位时为9，最高位为8

阿米诺斯