题解 P2518 【[HAOI2010]计数】

· · 题解

本题截止目前最高效的解法！

可以出一个加强版，加个模数，数据范围开到 10^{1000000} 。

设 m 为 n 的位数， p 为出现的数字个数（此题中 p=10 ） ，时间复杂度 O(m\log p) 。

前置知识：可重复排列个数公式： \frac{m!}{\sum a_i} ，其中 a_i 表示排列中出现过的数中第 i 个出现的次数， m 表示排列中元素个数。

首先，把删掉的 0 补到最前面，问题转化为可重复元素的康托展开。

不重复元素的康托展开有 O(m\log p) 的解法，相信大家都会，不会请移步模板题。

其实可重复元素的康托展开也有 O(m\log p) 的解法，也是用了树状数组。

例如，考虑 n=2011023 。

接下来我们从后往前计算。

设 s 为当前答案， t 为当前已处理的几位的排列总数。初始 s=0 ，t=1 。

最后一位为 3 ，只有 3 这一个排列，因此 3 前面的排列有 0 个， s=0 ， t=1 。

后两位为 23 ，有 23 和 32 两个排列，因此 23 前面的排列有 0 个， s=0 ， t=2 。

后三位为 023 ，有 6 个排列， s=0 ， t=6 。

后四位为 1023 ，有 24 个排列，此时 1 不再是最小的数， s 要加上倒数第四位为 0 的排列个数 6 个， s=6 ， t=24 。

后五位为 11023 ，运用可重排列公式可知有 60 个排列，此时 s 要加上倒数第五位为 0 的排列个数 12 个， s=18 ， t=60 。

后六位为 011023 ，有 180 个排列，此时 0 为最小的数，因此 s 不变， s=18 ， t=180 。

后七位为 2011023 ，有 630 个排列，此时比 2 小的数有 0 和 1 ，此时 s 要加上倒数第七位为 0 和 1 的排列共 360 个， s=378 ， t=630 。

最后的答案即为 378 。

看似上面的计算过程没什么规律，不过还是可以找到规律的。就是如果当前位为 a ，截止当前 a 出现了 b 次，比 a 小的数有 c 个，那么当前位给 s 的贡献即为 \frac{t\times c}{b} 。

为什么这个规律是正确的？考虑一个比 a 小的数 x ，如果之前 x 出现了 y 次，那么将 x 放到这一位，再把 a 放到后面，根据可重排列公式， t 的值就要变成 \frac{t\times y}{b} 。所有比 a 小的数共出现了 c 次，将 y 替换成 c 就是 \frac{t\times c}{b} 。

此时我们只需模拟上述过程，就能得到一个 O(mp) 的做法。

如果 n 是一个 10^6 进制数，也就是 p=10^6 ，这个复杂度我们也无法接受。我们需要支持两种操作：向一个序列中插入一个数，求序列中小于一个数的数的个数。显然可以用树状数组优化一下，就成了 O(m\log p) 。

代码如下：

#include<cstdio>
#include<cstring>
char str[55];
int p[11],q[11];//p为每个数出现次数，q为树状数组
int add(int x){
    for(;x<11;x+=x&-x)++q[x];
}
int sum(int x){
    int r=0;
    for(;x;x-=x&-x)r+=q[x];
    return r;
}
int main(){
    int n,i,c,a;
    __float128 s=0,t=1;//用整型中间变量会溢出！
    scanf("%s",str),n=strlen(str);
    for(i=n-1;i>=0;--i){
        a=str[i]-'0'+1;
        c=sum(a-1);//a为当前数，c为比a小的数个数
        if(!c)t=t*(n-i)/(++p[a]);
        else{
            t/=(++p[a]);
            s+=t*c;
            t*=(n-i);
        }
        add(a);
    }
    printf("%lld",(long long)(s+0.5));
    return 0;
}