计数

类似数位dp

#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
char str[10000];
int n;

LL cnt[10000],v[10000];
LL dp[10000][10000]; 
LL C(LL n,LL m){
	if (n<0||m<0||n<m) return 0;
	if (dp[n][m]) return dp[n][m];	
	if (n==m||m==0) return 1;
	dp[n][m]=C(n-1,m)+C(n-1,m-1);
	return dp[n][m];
}

LL cal(int n){
 LL res=1;	
    for (int i=0;i<=9;i++)//玄学代码此处为1或0都能过
       if (cnt[i]){
        res*=C(n,cnt[i]),n-=cnt[i];      
	   } 
	   return res;
}

LL ans=0;
int main(){
	scanf("%s",str);  
	
	for (int i=0;i<strlen(str);i++)
	 {
	    v[i+1]=str[i]-'0';
        cnt[str[i]-'0']++;
	  }
	  
	  int n,len=strlen(str);
	  n=len;
    for(int i=1;i<=len;i++){
        n--;
        for (int j=0;j<v[i];j++)
        {
          if (cnt[j]){
          
          	cnt[j]--;
          	
          	ans+=cal(n);
          //	printf("%d ",cal(n));
			  cnt[j]++;
		  }
		}
		cnt[v[i]]--;
	}	  
	printf("%lld",ans);
	return 0;
}