题面
题目传送门 https://www.lydsy.com/JudgeOnline/problem.php?id=2425
解法
显然可以一位一位确定答案
假设在第 \(i\) 时已经比原数小了, 那么答案就可以加上 \(\frac{(n-i)!}{s_0!s_1!...s_9!}\)
但是因为 \(n50\), 所以可能会爆 long long, 需要高精度
然而我就十分 sb 地写了高精度......
其实并不需要用高精度啊
可以先确定 0 放置的方案, 在剩下的里面 1 的方案,......
然后对这个东西不断乘起来就好了, 就是一个组合数的问题
代码 (sb 的高精度)
- #include <bits/stdc++.h>
- using namespace std;
- bool cmp(string x, string y) {
- if (x.size() != y.size()) return x.size()> y.size();
- return x>= y;
- }
- int sum[10];
- string fac[110];
- string operator - (string x, string y) {
- int l1 = x.size() - 1, l2 = y.size() - 1;
- for (int i = 1; i <= l1 - l2; i++) y = '0' + y;
- string ret = ""; int k = 0;
- for (int i = l1; i>= 0; i--) {
- int t = (x[i] - '0') - (y[i] - '0') - k;
- if (t <0) t += 10, k = 1; else k = 0;
- ret = (char)(t + '0') + ret;
- }
- while (ret.size()> 1 && ret[0] == '0') ret.erase(ret.begin());
- return ret;
- }
- string operator * (string x, int y) {
- int l = x.size(), a[210] = {0};
- for (int i = 0; i <l; i++) a[l - i - 1] = x[i] - '0';
- for (int i = 0; i < l; i++) a[i] *= y;
- for (int i = 0; i <= 3 * l; i++)
- a[i + 1] += a[i] / 10, a[i] %= 10;
- string ret = "";
- for (int i = 0; i <= 3 * l; i++) ret = (char)(a[i] + '0') + ret;
- while (ret.size()> 1 && ret[0] == '0') ret.erase(ret.begin());
- return ret;
- }
- string operator / (string x, string y) {
- string ret = "", tmp ="";
- int len = x.size() - 1;
- for (int i = 0; i <= len; i++) {
- tmp = tmp + x[i]; int s = 0;
- while (tmp.size()> 1 && tmp[0] == '0') tmp.erase(tmp.begin());
- while (cmp(tmp, y)) tmp = tmp - y, s++;
- ret = ret + (char)(s + '0');
- }
- while (ret.size()> 1 && ret[0] == '0') ret.erase(ret.begin());
- return ret;
- }
- long long calc(int len) {
- string ret = fac[len]; int tot = 0;
- for (int i = 0; i <= 9; i++)
- ret = ret / fac[sum[i]], tot += sum[i];
- if (tot> len) return 0;
- ret = ret / fac[len - tot];
- long long s = 0;
- for (int i = 0; i <ret.size(); i++)
- s = s * 10 + ret[i] - '0';
- return s;
- }
- int main() {
- string st; cin>> st;
- int len = st.size();
- for (int i = 0; i <len; i++)
- if (st[i] != '0') sum[st[i] - '0']++;
- fac[0] = "1"; long long ans = 0;
- for (int i = 1; i <= len; i++) fac[i] = fac[i - 1] * i;
- for (int i = 0; i < len; i++) {
- for (int j = 0; j < st[i] - '0'; j++)
- if (sum[j] || j == 0) {
- if (j) sum[j]--;
- ans += calc(len - i - 1);
- if (j) sum[j]++;
- }
- if (st[i] != '0') sum[st[i] - '0']--;
- }
- cout << ans << "\n";
- return 0;
- }
代码 (正常的组合数)
- #include <bits/stdc++.h>
- using namespace std;
- long long sum[10], c[65][65];
- long long calc(int len) {
- long long ret = 1;
- for (int i = 1; i <= 9; i++)
- ret *= c[len][sum[i]], len -= sum[i];
- return ret;
- }
- int main() {
- string st; cin>> st;
- int len = st.size();
- for (int i = 0; i < len; i++)
- if (st[i] != '0') sum[st[i] - '0']++;
- for (int i = 0; i <= 60; i++) {
- c[i][0] = 1;
- for (int j = 1; j <= i; j++)
- c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
- }
- long long ans = 0;
- for (int i = 0; i < len; i++) {
- for (int j = 0; j < st[i] - '0'; j++) {
- if (j) sum[j]--;
- ans += calc(len - i - 1);
- if (j) sum[j]++;
- }
- sum[st[i] - '0']--;
- }
- cout << ans << "\n";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2727903.html