题目地址：洛谷：【P2518】[HAOI2010]计数 – 洛谷、BZOJ：Problem 2425. — [HAOI2010]计数

题目描述

你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。
现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）.

输入输出格式

输入格式：
只有1行，为1个整数n.

输出格式：
只有整数，表示N之前出现的数的个数。

输入输出样例

输入样例#1：

1020

输出样例#1：

7

说明

n的长度不超过50，答案不超过2^63-1.

题解

参考资料：题解 P2518 【[HAOI2010]计数】 – noob – 洛谷博客
如果我们不删去前导0，其实就是相当于求对给定数的全排列中，比这个数小的排列个数。考虑一个数位DP的思想，如果一个高位上填的数字已经更小了，后面的位置显然是可以瞎邒排的，直接往答案里加一个全排列就好。但是可重集的全排列是有可能爆LL的，这里我们采用一种折中的办法求：如果集合大小为n，每个数码的个数为xi，考虑从n个位置里先取x0个位置放置0，然后从n-x0个位置放置1,，以此类推。也就是说，上面那个可重集的全排列数量是
\prod_{i=0}^9 \mathrm{C}_{n - \sum_{j=0}^{i-1} x_j}^{x_i}
我们枚举若前面的所有数位都与原数相同且现在这一位填某数码的时候计算答案，加进去就可以了。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

typedef long long LL;

const int MAXN = 55;

LL C[MAXN][MAXN];

inline void calc() {
    C[0][0] = 1;
    for(int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
}

char num[MAXN];
int n, cnt[10];

inline LL cal(int n, int *cnt) {
    LL res = 1;
    for(int i = 0; i <= 9; i++) {
        res *= C[n][cnt[i]];
        n -= cnt[i];
    }
    return res;
}

int main() {
    calc();
    scanf("%s", num + 1); n = strlen(num + 1);
    for(int i = 1; i <= n; i++) {
        cnt[num[i] - '0']++;
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < num[i] - '0'; j++) {
            if(cnt[j]) {
                cnt[j]--;
                ans += cal(n - i, cnt);
                cnt[j]++;
            }
        }
        cnt[num[i] - '0']--;
    }
    printf("%lld", ans);
    return 0;
}