CF991E Bus Number

题意翻译

给你一个数字序列A（长度不超过18位），问有多少个序列B满足①A中所有数字都一定要在B中出现过；②B中所有数字也一定要在A中出现过；③序列B不能以0开头

输入 #1

97

输出 #1

2

解题思路

 先统计序列中每一个数字出现的个数，输入的话可以用string类转成int，也可以直接scanf("%1d”，&a）；

然后dfs每种数字的出现情况

直接套公式 ans+=所有数字的个数的阶乘/每一种数字个数的阶乘之积-0在第一位的情况

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[10],temp[10];
ll jc[20],ans=0;
void dfs(int x) {
    if(x==10) {
        int cnt=0;
        for(int i=0; i<10; ++i) cnt += temp[i];
        ll p=jc[cnt];
        for(int i=0; i<10; ++i) p/=jc[temp[i]];
        if(temp[0]>=1) p-=(p*temp[0]/cnt);
        ans+=p;
        return;
    }
    for(int i=1; i<=num[x]; ++i) {
        temp[x]=i;
        dfs(x+1);
    }
    if(num[x]==0) dfs(x+1);
}

int main() {
    int a;
    while(scanf("%1d",&a)!=EOF){
        num[a]++;
    }
    jc[0]=1;
    for(int i=1; i<=19; i++) jc[i]=jc[i-1]*i;
    dfs(0);
    cout<<ans<<endl;
    return 0;
}