题目链接 \(Click\) \(Here\)
很好很妙的一个题目。
其实可以生成的数字，一定是原数的一个排列，因为\(0\)被放在前面就可以认为不存在了嘛~。也就是说现在求的就是全排列中所有小于该数的排列。对每一位我们考虑两类情况：
- 第一类情况 : 前 \(i\) 位上均相等, 且第 \(i\) 位上当前数是 \(j\) (比 \(arr_i\) 小)
- 这一位已经满足了约束条件小于，那么后面就可以放开了搞。也就是说后\(n-i\)个数形成的全排列中，每一个排列都是可以使用的，即答案加上一个全排列。
- 为了避免高精度计算，这里使用了比较特殊的方法计算可重集的全排列。
- 第二类情况 : 当前位置依然相等。
- 对此我们要在桶里去掉和这一位相等的数字，然后就可以去进行下一位计算啦。
最后让我们来一起复习一下差点把我卡死的可重集排列数公式吧\(QwQ\)：
\[(a[0]+a[1]+...+a[9])!/a[0]!/a[1]!/.../a[9]!
\]
\]
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55;
int C[N][N];
int ch, n, ans, tot[10], arr[100];
int get_ans (int n) {
int res = 1;
for (int i = 0; i <= 9; ++i) {
if (tot[i] != 0) {
res *= C [n][tot[i]];
n -= tot[i];
}
}
return res;
}
signed main () {
C[0][0] = 1;
for (int i = 1; i <= 50; ++i) {
for (int j = 0; j <= 50; ++j) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
while (true) {
if (isdigit (ch = getchar ())) {
arr[++n] = ch - '0';
tot[arr[n]]++;
} else break;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < arr[i]; j++) {
if (tot[j] != 0) {
//第一类情况 : 前 i 位上均相等, 且第 i 位上当前数是 j (比 arr[i] 小)
tot[j] = tot[j] - 1;
ans += get_ans (n - i);
tot[j] = tot[j] + 1;
//选中当前数 j, 对剩下的数求全排列 (可以随便选择了)
}
}
//第二类情况 : 当前位置依然相等, 去掉相等的数字, 进行下一位计算
tot[arr[i]]--;
}
cout << ans << endl;
}