TopCoder SRM 464 Div1 Easy ColorfulStrings

問題

数字からなる文字列の積を、その各桁の積とする。
数字からなる文字列がcolorfulであるとは、
(空でない)連続する部分文字列の積が、全て互いに異なることを言う。


n桁のcolorfulな文字列のうち、k番目に小さいものを求めよ。
n桁のcolorfulな文字列がk個未満の場合は空文字列を出力せよ。

制約条件

n≦50
k≦10^9

方針

同じ数字が2度出てきたらその時点でcolorfulではなくなるため、9桁以上のcolorfulな文字列は存在しない。
8桁以下のcolorfulである文字列は全探索により求められる。
総数はそんなに多くないので愚直に探索して間に合う。


1桁の場合だけ0と1が使えることに注意する。

ソースコード

vector<string> v;

void rec(string s,int n){
	if(s.size()==n){
		v.pb(s);
		return;
	}
	for(char c='2';c<='9';c++){
		string t=s+c;
		set<int> S;
		rep(i,t.size()){
			int p=1;
			for(int j=i;j<t.size();j++){
				p*=t[j]-'0';
				if(S.count(p))goto FAIL;
				S.insert(p);
			}
		}
		rec(t,n); FAIL:;
	}
}

class ColorfulStrings {
	public:
	string getKth(int n, int k) 
	{
		if(n>8)return "";
		if(n==1)return k<11?string(1,'0'+k-1):"";
		v.clear();
		rec("",n);
		return v.size()>=k?v[k-1]:"";
	}
};