CF991E Bus Number 题解

Textbook_blasphemy · 2021-07-22 15:21:00 · 题解

题意简述

给一个数字序列，问有多少个序列 B 满足:

① A 中所有数字都一定要在 B 中出现过。

② B 中所有数字也一定要在 A 中出现过。

③ 序列 B 不能以 0 开头。

分析

进一步简化题意:求在 n 个可能有重复的数字中求开头不为 0 的排列总数。

假设开头可以为 0 ，那么答案就是：

解释：sum 为数字总数，num 数组表示 i 数字有 num_i 个。

接下来考虑开头不能为 0 的情况。

直接算开头不能为 0 的情况比较棘手，考虑容斥原理（即总方案数减去开头为 0 的方案数）。

先把不为0的数按照开头可以为 0 的情况处理，把一个 0 放在开头，剩下的 0 往后放置，统计数量，得出的结果便是开头为 0 的情况。

最后将总方案的数量减去开头为 0 的数量即为答案。

Code

注: 19!=121645100408832000 ，不炸long long ，不用写高精。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;//输入的数当作字符串,方便处理 
int num[10];//每个数字出现的次数 
int slen;//n的位数 
int num_t[10];//因为num数组会改变,设置另一个num数组 
ll Fac[20]={1};//阶乘(Factorial),f[0]=1; 
ll ans=0;
void work(int x){
    if(x>9){//如果0~9统计完了 
        int cnt=0;//现在的总位数 
        for(int i=0;i<=9;i++){
            cnt=cnt+num_t[i];
        }
        ll tmp=Fac[cnt];//求总情况 
        for(int i=0;i<=9;i++){
            tmp=tmp/Fac[num_t[i]]; 
        }
        if(num_t[0]>=1)tmp=tmp-(tmp*num_t[0]/cnt);//最后,统计开头为0的情况 
        ans=ans+tmp;//相加 
        return;
    } 
    for(int i=1;i<=num[x];i++) {//当前数字出现过 
        num_t[x]=i;//设置成当前数字 
        work(x+1);
    }
    if(num[x]==0)work(x+1);
} 
int main(){
    cin>>s; 
    slen=s.size(); 
    for(int i=0;i<slen;i++){//字符串便于处理 
        num[s[i]-'0']++;
    }
    for(int i=1;i<=19;i++){//统计阶乘,方便算组合数 
        Fac[i]=Fac[i-1]*i;
    }
    work(0);
    printf("%lld",ans);
    return 0;
}