P2518 [HAOI2010] 计数 题解

· · 题解

原题链接：计数

初看题：“嗯？什么意思？”

翻译一下，每次给出一个整数 n，把 n 中的任意多个 0 删掉并把删掉 0 后的每一位数重新排序，求所有可能得到的数中有多少数小于 n （应该挺清楚了吧）

我们思考这样一件事情：把0删掉其实就等价于把0移动到最前面

所以接下来问题就简化成了“把所有数重新排序，求得到的数的大小小于 n 的方案数有多少种”。

我们考虑到对于两个数 a, b,如果 a,b 的前几位都相同且 a 的第 i 位大于 b 的第 i 位，则无论 a,b 的后几位如何，都有 b \le a 。

从这一点出发，我们尝试确定每一位的数。

假设有这么一组数据

[5,2,0,1,3,1,4]

我们现在开始确定第一位的数，因为 n 中第一位为 5，若想要组合出来的小于 n，则第一位必须小于等于 5，所以第一位可以是 0,1,2,3,4,5，根据上面的定理，若第一位为 0,1,2,3,4，则后面的数无论怎么填写，得到的数都一定小于 n，此时对答案的贡献为分别确定这5位数后剩下的数的全排列之和。

此时第一位还能为 5，那我们就确定第一位的数为 5，尝试确定第二位的数，第二位可以是 0,1,2，同理当第二位为 0,1 时，组合出来的数一定小于 n，则答案再加上分别确定这两位数后剩下数的全排列之和，确定第二位为 2，继续向下遍历求解即可。

Wait a minute，数据之中有两个 1 ，此时构成的全排列虽然编号不同，但是得到的数可能是相同的，也就是说，直接用阶乘计算可能会导致计算重复。

问题就转变成为了：如何求可重集的全排列。

设总元素个数为 Len，tot_i 表示其中第i种数的数量（其实就是桶）

如果第 j 种数的数量不为空，则先确定第 j 位数的位置，此时方案数为 C_{Len}^{tot_j}，表示总共有 Len 个空格，向其中插入 tot_j 个 j 的方案数，此时还剩下 Len-tot_j个空格，再向其中插入 tot_{j+1} 个 j+1，此时的总方案数为 C_{Len}^{tot_i} \times C_{Len-tot_i}^{tot_{i+1}}

同理，得总共的方案数为

C_{Len}^{tot_1} \times C_{Len-tot_1}^{tot_2} \times C_{Len-tot_1-tot_2}^{tot_3} \times...\times C_{Len - \sum_{1}^{9}tot_i}^{tot_{10}}

事实上就只是每种数的数量与剩余空位数量的组合数的乘积而已。

考虑到定义域很小，我们可以先用一个二维数组预处理出各个组合数的答案。

可以用以下式子快速预处理出组合数

C_{n}^{r}= C_{n}^{r-1} \times \frac{n-r+1}{r} \quad

证明就不给出啦，感兴趣的可以尝试着自己证明看看

Talk is cheap,show me the code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=100;
int tot[Max],num[Max],n=0;
int C[Max][Max];// r n
int ans=0;
int solve(int len)
{
    int fin=1;
    for(int i=0;i<=9;i++)
    {
        fin*=C[tot[i]][len];
        len-=tot[i];
    }
    return fin;
}
signed main()
{
    C[0][0]=1;
    for(int N=1;N<=60;N++)
    {
        C[0][N]=1;
        C[N][N]=1;
        for(int R=1;R<N;R++)
        {
            C[R][N]=C[R-1][N]*(N-R+1)/R;
        }
    }
    char c;
    c=getchar();
    while('0'<=c and c<='9')
    {
        num[++n]=c-'0';
        tot[c-'0']++;
        c=getchar();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<num[i];j++)
        {
            if(tot[j])
            {
                tot[j]--;
                ans+=solve(n-i);
                tot[j]++;
            }
        }
        tot[num[i]]--;
    }
    printf("%lld",ans);
}