TopCoder SRM 817 : Div1 Medium IntrospectiveNumbers

解法は割と自明で面倒な問題。
https://community.topcoder.com/stat?c=problem_statement&pm=17248&rd=18897

問題

正整数xがIntrospectiveであるとは、xの10進表記中にdという数字がある場合、その登場回数がちょうどdであるものをいう。
Introspectiveな整数のうち、小さい順からN番目のものを求めよ。

解法

まず、整数のうち1～9のどれを含むかを(2^9)-1通り総当たりすると、組み合わせ計算で各桁の整数が何通り該当するか求められる。
この時点で、解の値の桁数が求められる。

あとは、頭から順に1～9を埋めて行こう。
ある桁の値を1～9まで仮埋めしたとき、以降の桁が何通りあり得るかを計算して、Nを超えるかどうか判定していく。
辞書順最小値を決める定番のテクニック。

vector<pair<int,ll>> patterns[100];
static const int N_=1020;
static __int128 C_[N_][N_];


class IntrospectiveNumbers {
	public:
	string nth(long long N) {
		int mask;
		int i,j;
		FOR(i,100) patterns[i].clear();
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=min(C_[i-1][j-1]+C_[i-1][j],(__int128)1LL<<60);
		FOR(mask,1<<9) if(mask) {
			int sum=0;
			__int128 pat=1;
			FOR(i,9) if(mask&(1<<i)) {
				sum+=(i+1);
				pat=min(pat*C_[sum][i+1],(__int128)1LL<<60);
			}
			patterns[sum].push_back({mask,(ll)pat});
		}
		
		FOR(i,55) {
			ll sum=0;
			FORR(v,patterns[i]) {
				sum+=v.second;
				if(sum>=1LL<<60) break;
			}
			if(sum-1>=N) break;
			N-=sum;
		}
		int cur=i,x;
		N++;
		string R;

		int D[111]={};
		FOR(i,cur) {
			for(j=1;j<=9;j++) {
				if(D[j]==j) continue;
				D[j]++;
				__int128 sum=0;
				FORR(v,patterns[cur]) {
					int a=v.first;
					int lef=cur-i-1;
					__int128 p=1;
					FOR(x,9) {
						if((a&(1<<x))==0) {
							if(D[x+1]) {
								p=0;
								break;
							}
						}
					}
					if(p==0) continue;
					FOR(x,9) if((a&(1<<x))) {
						p=min(p*C_[lef][x+1-D[x+1]],(__int128)1LL<<60);
						lef-=x+1-D[x+1];
					}
					if(p) assert(lef==0);
					sum+=p;
				}
				if(sum>=N) break;
				N-=sum;
				
				D[j]--;
			}
			assert(j<=9);
			R.push_back('0'+j);
		}
		
		
		
		return R;
		
	}
}

まとめ

変なバグを入れ込んで時間を食ったのがもったいない。