小于n的不同数码数的个数

template<typename R, typename T>
R sstream_cast(const T& o) {
    stringstream ss;
    ss << o;
    R result;
    ss >> result;
    return result;
}

// 排列数 n!/(n-k)!
int P(int n,int k)
{
        if(k>n)return 0;
        int res = 1;
        for(int i=n-k+1; i<=n; i++){
            res *= i;
        }
        return res;
}

// 返回小于n的各个数位不同的整数的个数
int countDistinctDigitsNumbers(int n) {
    string s = sstream_cast<string>(n);
    int len = s.size();
    // 分类考虑：
    // 1. 所有位数不足len的数满足条件
    // 2. 首位为 1 ~ s[0]-1 的情况，s[1:len]任意都满足条件
    // 3. 首位为 s[0]，二位为 0 ~ s[1]-1 的情况(但前缀用掉的digit不能再用)，s[2:len]任意都满足条件
    //    ...
    //    前缀为 s[0:i]，第i位为 0 ~ s[i]-1 的情况(但前缀用掉的digit不能再用)，s[i+1:len]任意都满足条件
    //    ...
    //    前缀为 s[0:len-1]，第len-1位为 0 ~s[len-1]-1 的情况(但前缀用掉的digit不能再用)，空后缀

    int result = 0;
    // 第1类：统计任意i位数的个数
    for(int i=1;i<len;i++) {
        result += 9 * P(9, i-1);
    }
    // 第2类
    result += (s[0]-'0'-1) * P(9, len-1);
    // 第3类
    bool used[10] = {0};
    used[s[0]-'0'] = true;
    for(int i=1;i<len;i++) {
        int cnt = 0;
        // 对于cnt的循环计数可以优化，但无必要
        for(int k=0;k<s[i]-'0';k++) {
            if(!used[k]) {
                cnt++;
            }
        }
        result += cnt * P(9-i, len-1-i);

        // 如果s前缀本身用到了重复数字，直接跳出，终止第3类的计算
        if(used[s[i]-'0']) break;
        else used[s[i]-'0'] = true;
    }
    return result;
}