自动搬运

查看原文

来自洛谷，原作者为

	巨型方块 **

搬运于2025-08-24 21:38:35，当前版本为作者最后更新于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);
}