题目大意
给定一个整数 \(n\)，通过删除任意多个 \(0\)，然后重新排列剩余数字，求能产生多少个比原数小的不同数。
分析
- 只能删除数字 \(0\)，其他数字必须保留。
- 可以重新排列数字顺序。
- 生成的数不能有前导 \(0\)。
- 要计算所有不同的比原数小的数。
我们可以从高位到低位逐位确定数字，使用组合数学计算方案数。
Solution
标签：数位DP
具体步骤
1. 统计数字出现次数
- 记录原数中 \(0-9\) 每个数字出现的次数。
- 用 \(a[i]\) 表示数字i出现的次数。
2. 逐位比较
设原数 \(b[1..n]\) 有 \(n\) 位，从第 \(1\) 位到第 \(n\) 位：
- 对于当前位 \(b[i]\)，考虑所有比它小的数字 \(j\)。
- 如果数字 \(j\) 还有剩余（\(a[j]\) > \(0\)），则可以放在这一位。
- 放置j后，剩下的数字可以任意排列，计算排列数加到答案中。
- 然后考虑这一位与原数相同的情况，继续处理下一位。
3. 计算排列数
- 在某一位确定了一个数字后，剩下的数字可以自由排列。
- 计算这些数字的全排列数，但要考虑重复数字。
- 公式：\(m!\) / (\(a[0]!\) * \(a[1]!\) * ... * \(a[9]!\))，其中 \(m\) 是剩余数字总数。
- 使用组合数 \(C(m, a[0])\) * \(C(m-a[0], a[1])\) * ...来计算。
时间复杂度
- 组合数计算：杨辉三角递推法，使用记忆化，时间复杂度 \(O(n²)\)。
- 主循环：遍历每一位，最坏 \(O(n×10)\)。
- 总时间复杂度：\(O(n²)\)，\(n≤50\)，可以接受。
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;ll c[521][521], a[520], b[1314], n;
string s;// 计算组合数C(x, y)
ll C(ll x, ll y) {if (c[x][y]) return c[x][y];if (y > x || y < 0 || x < 0) return 0;if (y == 1) return x;if (y == 0 || x == y) return 1;c[x][y] = C(x - 1, y - 1) + C(x - 1, y);return c[x][y];
}// 计算当前剩余数字的排列数
ll cnt() {ll m = n, ccnt = 1;for (ll i = 0; i <= 9; i++) {if (a[i]) {ccnt *= C(m, a[i]); // 选择a[i]个位置放数字im -= a[i]; // 从剩余位置中减去已用位置}}return ccnt;
}int main() {cin >> s;// 统计每个数字出现次数，并保存原数每一位for (char ch : s) {ll num = ch - '0';a[num]++; // 0到9的个数b[++n] = num; // 第i位是num}ll t = n, ans = 0;for (ll i = 1; i <= t; i++) { // 逐位递推--n; // 当前位已确定，减少总位数for (ll j = 0; j < b[i]; j++) { // 枚举比b[i]小的数字if (a[j]) { // 如果该数字还有剩余a[j]--; // 使用一个jans += cnt(); // 计算排列数a[j]++; // 回溯，恢复状态}}a[b[i]]--; // 确定这一位与原数相同，继续处理下一位}cout << ans;return 0;
}