Luogu P2518 [HAOI2010] 计数

佚名 / 2023-05-17 / 原文

发现删除 \(0\) 可以看作把其放在最前面成为前导 \(0\)，那就相当于固定了排列的长度也固定了排列可以用的元素即每个数位，求在排列中在其前面的数的个数
看到在排列中求排名，就联想到康托展开，但是这个题的康托展开是有重复元素的
但其实方法是与无重复元素的康托展开差不多的

设这个数为 \(s\)，其数位个数为 \(n\)，下文请注意区分“数位”和“数”

假设现在是第 \(i\) 位，这个数位上的数为 \(val_i\)，考虑求在 \(1\sim i - 1\) 的数位上的数都是相等的情况下在排列中在 \(s\) 前面的数
可以发现，其实只需要考虑第 \(i\) 个数位上的数比 \(val_i\) 小的可能排列的数量，因为若比 \(val_i\) 大则肯定不产生贡献，相等则会可以后面的 \(i + 1\) 位计算

首先对 \(i\sim n\) 的数位上的数统计一下得到 \(cnt_j\)
若 \(cnt_j > 0\quad (0\le j < 9)\)，则可以在这个位选 \(j\) 这个数，后面 \(i + 1\sim n\) 的数位肯定任意一种排法都满足条件，于是考虑求出后面的数位的排法数量
首先因为选了一个 \(j\)，\(cnt_j\leftarrow cnt_j - 1\)，后面计算完记得对其还原
考虑对于第 \(j\) 个数，则第 \(0\sim j - 1\) 个数肯定都排完了，于是就有了 \(m = n - i - \sum\limits_{k = 0}^{j - 1} cnt_k\) 个位置可以填，方案数即为 \(f_j = C_{m}^{cnt_j}\)，所以总方案数为 \(\prod\limits_{j = 0}^{9} f_j\)

时间复杂度 \(\mathcal{O}(nw^2)\)，\(w\) 为值域，对于此题 \(w = 10\)

// by lhzawa
#include<bits/stdc++.h>
using namespace std;
const int N = 50 + 5;
long long C[N][N];
char s[N]; int cnt[10];
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        cnt[s[i] - '0']++;
    }
    for (int i = 0; i <= n; 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 = 1; i <= n; i++) {
        for (int j = 0; j < s[i] - '0'; j++) {
            if (cnt[j]) {
                cnt[j]--;
                long long tot = 1; int ue = n - i;
                for (int k = 0; k < 9; k++) {
                    tot *= C[ue][cnt[k]], ue -= cnt[k];
                }
                ans += tot;
                cnt[j]++;
            }
        }
        cnt[s[i] -'0']--;
    }
    printf("%lld\n", ans);
    return 0;
}