[C++知识库]Problem - 991E - E. Bus Number(排列+暴力)

E. Bus Number

题目大意:给定一串数字$A,$你需要构造出一串数字$B$,满足$A$中的数字$B$中都要出现,$B$中出现的数字必须都在$A$中出现,$B$中出现数字的个数不能大于$A$中对应数字出现的个数,求数字串$B$的个数.

解题思路:因为给定的数字串比较小,所以可以直接$dfs$求各种数字的使用情况,然后就是如何求带重复元素的排列,这个是这个题的一个关键点,正确的求法是$C_n^{a_1}?C_{n?a_1}^{a_2}?C_{n?a_1?a_2}^{a_3}?....C_{n?a_1?...?a_{n?1}}^{a_n}$.我们对于每次枚举出来的求出总排列个数,然后再减去$0$放置在第一位的情况即可得到答案.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int a[20];
int tem[20];
ll ans;
ll fac[20];
ll cal(int n, int m){
    return fac[n]/fac[n-m]/fac[m];
}

ll check(){
    ll tot = 1;
    ll num = 0;
    for (int i = 0; i <= 9; ++i){
        num+=tem[i];
    }
    for (int i = 0; i <= 9; ++i){
        if (tem[i]==0)continue;
        tot*=cal(num, tem[i]);
        num-=tem[i];
    }
    for (int i = 0; i <= 9; ++i){
        num+=tem[i];
    }
    if (tem[0]!=0){
        num--;
        tem[0]--;
        ll now = 1;
        for (int i = 0; i <= 9; ++i){
            if (tem[i]==0)continue;
            now*=cal(num, tem[i]);
            num-=tem[i];
        }
        tem[0]++;
        tot-=now;
    }
    return tot;
}

void dfs(int i){
    if (i==10){ans+=check(); return;}
    for (int j = 0; j <= a[i]; ++j){
        if (a[i]!=0&&j==0)continue;
        tem[i]=j;
        dfs(i+1);
    }
}

int main(){
    syncfalse
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    fac[0]=1;
    for (int i = 1; i <= 19; ++i)fac[i]=fac[i-1]*i;
    ll n;
    cin>>n;
    while(n){
        a[n%10]++;
        n/=10;
    }
    dfs(0);
    cout << ans << "\n";

    return 0;
}