AtCoder ARC #047 : C - N!÷K番目の単語

今年から記事作成の問題レベルのボーダーを少し上げるので、今後ARCはC,Dのみここに書くようにします。
http://arc047.contest.atcoder.jp/tasks/arc047_c

問題

1～NのPermutationのうち、辞書順でN!/K番目のものを求めよ。

解法

factorial number systemにおいてN!/K-1番目のものを求め、Permutationに戻せばよい。
そのためにはN!/Kをfactorial number systemで計算する必要がある。

これは筆算の要領で行うことができる。
例えばN=8,K=3の時、先頭の桁はN/K=2+2/3より、(0-originで)2である。
この時、残り7桁においては、7!通りの数値のうち2/3を選びたい。
そこで7*2/3=4+2/3とり、2つめの桁は4である。

あとは同様にこの処理を繰り返せばよい。
まとめると以下のようになる。
初期状態でp=1とする。
N*p/Kの商と剰余を求める。商はその桁の値であり、剰余は再度pに代入し、順次次の桁を求めていけば良い。

factorial number systemからPermutationに戻すには、「上の桁で未使用の数値のうち下からn番目」を求める必要があるが、これはBITを二分探索すればよい。

ll N,K;
int fac[101010];
template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};

BIT<int,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll p=1;
	FOR(i,N) bt.add(i+1,1);
	FOR(i,N) {
		ll cand=N-i;
		fac[i]=cand*p/K;
		p=cand*p%K;
	}
	for(i=N-1;i>=0;i--) {
		if(fac[i]!=0) {
			fac[i]--;
			break;
		}
		fac[i]=N-i-1;
	}
	
	FOR(i,N) {
		x=bt.lower_bound(fac[i]);
		_P("%d\n",x+1);
		bt.add(x,-1);
	}
}

まとめ

lower_bound付のBITを作ってあったのでfactorial number systemからPermutationへの復元は容易だった。