题解 P2518 【[HAOI2010]计数】

巨型方块 · 2017-02-20 15:58:17 · 题解

https://www.luogu.org/problem/show?pid=2518

对于一个数，把其中的0删掉，相当于把0放到了前面；

所以这个问题就是让我们求一下给我们的数的全排列比当前小的有几个；

我们假设a[i]代表数字i 0~9有几个；

那么用这些来表示全排列

(a[0]+a[1]+...+a[9])!/a[0]!/a[1]!/.../a[9]!;

当然如果a[i]==0那么不参与运算；

但是这样的话，longlong表示存不下；

所以我们要用高精度

所以我们在想想；

假如现在有m个位置；

我们先把0放法放好

C(m,a[0]);

之后就只有m-a[0]个位置；

然后在放1

C(m-a[0],a[1]);

所以答案是

C(m,a[0])xC(m-a[0],a[1])x...xC（m-a[0]-a[1]-..-a[8],a[9]）;

就可以算全排列；

思路和数位dp差不多；

一位一位向前推进；

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define Ll long long
using namespace std;
Ll CC[1001][1001];
Ll C(Ll n,Ll m){
    if(CC[n][m])return CC[n][m];
    if(m==1)return n;
    if(m==0||m==n)return 1;
    if(m>n)return 0;
    CC[n][m]=C(n-1,m)+C(n-1,m-1);
    return CC[n][m];
}
int a[10],v[100];
Ll ans;
int n;
char c;
Ll cfb(){
    Ll ans=1;
    int m=n;
    for(int i=0;i<=9;i++)if(a[i])ans*=C(m,a[i]),m-=a[i];
    return ans;
}
int main()
{
    while(cin>>c)if(isdigit(c))v[++n]=c-48,a[v[n]]++;
    int nn=n;
    for(int i=1;i<=nn;i++){
        n--;
        for(int j=0;j<v[i];j++)
        if(a[j]){a[j]--;ans+=cfb();a[j]++;}
        a[v[i]]--;
    }
    printf("%lld",ans);
}