记录编号	54481	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]计数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2013-03-10 18:13:23	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
unsigned long long C[51][51]={0};
void Pascal(unsigned long long n){//递推组合数,使得C中包含到n的组合数
	unsigned long long i,j;
	for(i=0;i<=n;i++){
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
		}
	}
}
string s;//就是s
unsigned long long len;//长度
unsigned long long p[38]={0};//p[i]是数字i出现的个数
unsigned long long ans=0;
unsigned long long calc(int lm){//lm位,算"任意的"序列个数
	unsigned long long x=1;
	unsigned long long now=0,i;
	for(i=0;i<=9;i++){
		x*=C[lm-now][p[i]];
		now+=p[i];
	}
	return x;
}
void deal(int k){//大致意思是,固定下标k,算后面小于它的个数
	int now=s[k];
	int i;
	for(i=0;i<now;i++){
		if(!p[i]) continue;
		p[i]--;
		ans+=calc(len-k-1);
		p[i]++;
	}
	p[now]--;
}
void read(void){
	cin>>s;
	len=s.size();
	for(int i=0;i<=9;i++) p[i]=0;
	for(int i=0;i<len;i++){
		s[i]-='0';
		p[s[i]]++;
	}
}
void work(void){
	int i;
	for(i=0;i<len;i++) deal(i);
}
int main(){
	freopen("perm.in","r",stdin);
	freopen("perm.out","w",stdout);
	read();
	Pascal(len);
	work();
	cout<<ans<<endl;
	return 0;
}