题目大意

给定一个全数字字符串 $s1$，假设数字 $i$ 出现了 $a_i$ 次。

现在要求构造全数字字符串 $s2$，假设数字 $i$ 出现了 $b_i$ 次。

那么 $b$ 满足一下要求

• 对于 $i\in[0,9]$，$b_i\le a_i$
• $a_i\ne 0$ 时 $b_i\ne 0$
• $s2_{1}\ne 0$

思路

首先需要明确如何求解一个字符串的全排列。

假设字符串 $s$ 长度为 $n$，其全排列个数为 $f(s)$。

如果 $i,j\in[1,n],i\ne j$ 满足 $s_i\ne s_j$，那么 $f(s)=n!$。

因为对于第 $i$ 次选择时，在以前的选择中已经选择了 $i-1$ 个元素，那么对于这次选择就只有 $n-i+1$ 个元素可以选择了。

假设 $g_i$ 表示选择了 $i$ 次的方案数，因为乘法原理，$g_i=g_{i-1}\cdot (n-i+1)$。

所以 $g_n=f(s)=n\times (n-1)\times \cdots \times 2 \times 1$。

对于不满足 $i,j\in[1,n],i\ne j$ 满足 $s_i\ne s_j$ 的情况，那么假设字符 $i$ 出现了 $a_i$ 次。

$f(s)=n!-\sum_{i\in a} a_i!$

因为将任意两个重复的元素交换得到的方案其实是一样的，所以需要将多余的方案减掉。

对于重复的可能性，其实就是对于这些重复的元素自己的看重顺序的全排列数量，所以就是 $a_i!$。

具体的对于这道题目，因为 $n$ 非常的小，可以使用 dfs 暴力枚举出所有字符串使用每一个元素的次数，那么答案就是所有元素的全排列减去以 $0$ 作为开头的排列个数。

$ans=\cfrac{(\sum_{i=0}^{9}a_i)!}{\prod_{i=0}^{9}a_i! }-\cfrac{[(\sum_{i=0}^{9}a_i)-1]!}{(a_0-1)!\cdot\prod_{i=1}^{9}a_i! }$

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int n,s[N],ans,f[N],jc[N];
char a[N];
void init(){
    jc[0]=1;
    for(int i=1;i<N;i++){
        jc[i]=jc[i-1]*i;
    }
}
void dfs(int x){
    if(x==10){
        int tot=0;
        for(int i=0;i<=9;i++){
            tot+=f[i];
        }
        int sum=jc[tot];
		for(int i=0;i<=9;i++){
			sum/=jc[f[i]];
		}
		if(f[0]>0){
			int num=jc[tot-1]/jc[f[0]-1];
			for(int i=1;i<=9;i++){
                num/=jc[f[i]];
            }
			sum-=num;
		}
		ans+=sum;
		return;
    }
    for(int i=1;i<=s[x];i++){
        f[x]=i;
        dfs(x+1);
    }
    if(!s[x]){
        dfs(x+1);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>a+1,n=strlen(a+1);
    init();
    for(int i=1;i<=n;i++){
        s[a[i]-'0']++;
    }
    dfs(0);
    cout<<ans<<'\n';
    return 0;
}