记录编号	240208	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]计数	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-03-22 10:22:57	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 55;
typedef long long LL;
int cnt[10];
char a[maxn];
LL calc(int len) {//多重集合排列数 
	int tmp[10] = {0}; 
	LL ans = 1;
	int num = 0;
	for(int i = 0; i <= 9; i++) {//枚举每一个数 
		for(int j = 1; j <= cnt[i]; j++) {//阶乘cnt[i] 
			ans *= (++num);//最后一定为总位数 
			ans /= j;
		}
	}
	return ans;
}
void read() {
	scanf("%s", a+1);
	a[0] = 1;
	a[0] = strlen(a)-1;
	for(int i = 1; i <= a[0]; i++) {//顺便get一下位数 
		cnt[a[i]-'0']++;
	}
} 
void solve() {
	int num;
	LL ans = 0;
	for(int i = 1; i <= a[0]; i++) {//枚举每一位然后固定 
		num = a[i]-'0';
		for(int j = 0; j < num; j++) {//为了使所有数都比这一位小，所以这里要求枚举当前位的值都比当前位小 
									//这里不是小于等于，因为之后需要将这一位固定为当前值 
			if(!cnt[j]) continue;//如果比它小的这一位 
			cnt[j]--;
			ans += calc(i+1);//计算在当前位为j的情况下后面的数的排列数 
			cnt[j]++;
		}
		cnt[num]--;//固定当前值
					//这里之所以成立是因为每次计算的都是比当前位小的
					//而之后计算的也是比下一位小的
					//所以当前位不变的时候下一位确定的值一定比总值要小
					//反之如果和上面一样对当前位处理，则可能后面的值比当前位大 
	}
	printf("%lld\n", ans); 
}
int main() {
	freopen("perm.in", "r", stdin);
	freopen("perm.out", "w", stdout);
	read();
	solve();
	return 0;
}