题目分析
对于一个数，删掉这个数中的任意多个数位0，等价于将这些0移到这个数的前面（即前导0）。
问题就转化成了n的全排列中有多少个是小于n的。
考虑使用数位dp的思想求解。
设状态 dp(pos,limit) 表示:
处理到n从高向低数低 pos 位。
limit=true，表示有数位限制，此时继续dp。
limit=false，表示无数位限制，此时无论后面的数怎么排列，所得的数都不会超过n，可以直接使用有重复元素全排列公式：
\large\frac{(\sum_{i = 1}^{m}cnt_i)!}{\prod_{i = 1}^{m}cnt_i!}
其中，cnt_i 表示数字 i 出现的个数。
具体细节详见代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// s 存储输入的字符串形式的数字，str 用于存储中间计算结果
string s, str;
// num 数组用于记录每个数字（0 - 9）出现的次数
int num[10], sum[16], len, cnt;
// 高精度乘
void ins(int x) {
int carry = 0;
for (int i = str.size() - 1; i >= 0; i--) {
int t = (str[i] - '0') * x + carry;
carry = t / 10;
str[i] = char(t % 10 + '0');
}
while (carry) {
str = char(carry % 10 + '0') + str;
carry /= 10;
}
}
// 高精度除
void del(int x) {
int r = 0;
string nstr = "";
for (int i = 0; i < str.size(); i++) {
r = r * 10 + (str[i] - '0');
nstr += char(r / x + '0');
r %= x;
}
int start = 0;
while (start < nstr.size() - 1 && nstr[start] == '0') start++;
str = nstr.substr(start);
}
ll solve(int len, int sl) {
// 如果剩余长度小于需要的非零数字个数，返回 0
if (len < cnt - sl) return 0;
str = "1";
for (int i = 1; i <= len; i++)
ins(i);
for (int i = 1; i <= 9; len -= num[i++])
for (int j = 1; j <= num[i]; j++)
del(j);
for (int i = 1; i <= len; i++)
del(i);
ll tot = 0;
// 转换
for (int i = 0; i < str.size(); i++)
tot = tot * 10 + str[i] - '0';
return tot;
}
//算满足条件的数字个数
ll dfs(int pos, int sl, int limit) {
ll ans = 0;
// 如果已经遍历完所有数位，判断是否有足够的非零数字
if (pos == len) return sl == cnt;
// 如果没有上限限制，直接计算排列组合数
if (!limit) return solve(len - pos, sl);
// 枚举当前数位可以取的值
for (int i = 0; i <= s[pos] - '0'; i++) {
// 如果该数字的剩余个数为 0，跳过
if (!num[i]) continue;
// 减少该数字的剩余个数
num[i]--;
// 递归计算下一位的结果
ans += dfs(pos + 1, sl + (i > 0), i == s[pos] - '0');
// 回溯，恢复该数字的剩余个数
num[i]++;
}
return ans;
}
int main() {
cin >> s;
len = s.size();
// 统计每个数字的出现次数和非零数字的个数
for (int i = 0; i < s.size(); i++) {
num[s[i] - '0']++;
if (s[i] != '0') cnt++;
}
// 计算结果并减去原数字本身
cout << dfs(0, 0, true) - 1;
return 0;
}
健康查询