Codeforces #491 Div2 E. Bus Number

なんか問題文が読みにくい回。
http://codeforces.com/contest/991/problem/E

問題

ある整数Nが与えられる。

• Nに含まれる数字を1個以上Nに含まれる個数以下含む。
• Leading Zeroはない

上記条件を満たす整数はいくつあるか。

解法

DFSなり取り出す桁の総当たりなどすれば、0～9の各数字の登場回数のパターンは列挙できる。
あとは先頭桁の値だけ0以外を取るケースを考え、残りの桁は単純な同じ要素を複数持つ場合の並び方の列挙を考えるだけ。

int N;
string S;
ll fact[20];

set<vector<int>> V;
vector<int> ma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	fact[0]=1;
	for(i=1;i<=19;i++) {
		fact[i]=fact[i-1]*i;
	}
	
	for(int mask=0;mask<1<<N;mask++) {
		vector<int> C(10,0);
		FOR(i,N) if(mask&(1<<i)) C[S[i]-'0']++;
		V.insert(C);
		if(mask+1==(1<<N)) ma=C;
	}
	
	ll ret=0;
	FORR(v,V) {
		vector<int> VV=v;
		int ng=0;;
		FOR(i,10) if((VV[i]==0)!=(ma[i]==0)) ng=1;
		if(ng==1) continue;
		
		for(i=1;i<10;i++) if(VV[i]) {
			VV[i]--;
			int sum=0;
			FORR(vv,VV) sum+=vv;
			ll pat=fact[sum];
			FORR(vv,VV) pat/=fact[vv];
			ret+=pat;
			VV[i]++;
			
		}
	}
	cout<<ret<<endl;
}

まとめ

なんか定番っぽくて面白味は無いなぁ。