LC 6151. 统计特殊整数

https://leetcode.cn/problems/count-special-integers/

其实我觉得这题可以枚举所有数字的可能性，但是好像这题时间卡的比较紧，所以需要一些优化实现

如果是位数如果不够的话，那么可以使用组合计数的方式计算出来可能性

假设有X位
第一位可能性是[1-9]9种可能性
之后位数可能性则是A(9, X-1)

然后考虑位数相同的情况，这个就需要做些搜索了，假设这个数字表示是 x0,x1,x2..xi,..xn-1

对于第一位如果值是[1,x0-1]的话，那么之后位数肯定是满足的，就有 x0 * A(9, n-1) 种可能
如果第一位是x0的话，那么同理考虑第二位。但是考虑第二位的时候需要将x0排除，以此类推。
如果所有位数都符合的话，那么就是相等的情况，就需要返回1

class Solution:
    def countSpecialNumbers(self, n: int) -> int:

        def A(n, m):
            r = 1
            for x in range(n - m + 1, n + 1):
                r *= x
            return r

        digit = 1
        ans = 0
        while 10 ** digit <= n:
            ans += 9 * A(9, digit - 1)
            digit += 1

        seq = []
        x = n
        while x:
            seq.append(x % 10)
            x = x // 10
        seq = seq[::-1]
        mask = [0] * 10

        def search(i, seq, mask):
            if i == len(seq): return 1
            r = 0
            start = 1 if i == 0 else 0
            for x in range(start, seq[i]):
                if mask[x] == 1: continue
                r += A(9 - i, len(seq) - i - 1)

            if mask[seq[i]] == 0:
                mask[seq[i]] = 1
                r += search(i + 1, seq, mask)
            return r

        ans += search(0, seq, mask)

        return ans