Codeforces ECR #079 : E. New Year Permutations

問題文がややこしい。
https://codeforces.com/contest/1279/problem/E

問題

Permutation Pに対し、f(P)を以下のように定義する。
未処理の要素のうち要素番号が最小のものをiとする。
i, P(i), P(P(i)), ...を再びiが登場するまで並べた数列を考える。
その後、その数列を最大要素が先頭に来るようシフトしたものを考える。

この手順を繰り返し、いくつかの数列が得られる。
この数列を辞書順で並べ替えて再び連結した数列をf(P)とする。

NとKが与えられる。
N要素のPermutationのうちP=f(P)となるもので、辞書順K番目のものを求めよ。

解法

N要素のPermutationのうち、先頭要素が最大値で、かつその置換が単一のサイクルを成すものは(N-2)!通りである。
dp(i) := [i,n]のPermutation Pでf(P)=Pを満たすものの数
とすると、dp(i)=sum(dp(j)*(j-i-3)!)である。
ここから、あとは辞書順に小さいものを求める典型として、先頭から要素を決める際、ある値を定めると以降の値の組み合わせが何通りかわかるので、合計がKを超えない範囲で大きな値を前から埋めて行くとよい。

int T;
int N;
ll K;
ll fact[1010],cycle[1010];;
ll dp[52][52];
int tar[52],vis[52];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	for(i=1;i<=1000;i++) {
		if((double)fact[i-1]*i>1e18) fact[i]=5+1e18;
		else fact[i]=fact[i-1]*i;
	}
	FOR(i,51) cycle[i]=(i-2)>=0?fact[i-2]:1;
	
	for(x=1;x<=50;x++) {
		dp[x][x+1]=1;
		for(i=x;i>=1;i--) {
			for(j=i;j<=x;j++) {
				double add=(double)dp[x][j+1]*cycle[j-i+1];
				if(add+dp[x][i]>1e18) {
					dp[x][i]=5+1e18;
				}
				else {
					dp[x][i]+=dp[x][j+1]*cycle[j-i+1];
				}
			}
		}
	}
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		if(dp[N][1]<K) {
			cout<<-1<<endl;
		}
		else {
			K--;
			FOR(i,N+1) tar[i]=i,vis[i]=0;
			i=1;
			vector<int> V;
			
			while(i<=N) {
				for(j=i;j<=N;j++) {
					//cout<<i<<j<<" "<<dp[N][j+1]<<" "<<dp[N][j+1]*cycle[j-i+1]<<" "<<K<<endl;
					if(dp[N][j+1]*cycle[j-i+1]<=K) {
						K-=dp[N][j+1]*cycle[j-i+1];
					}
					else {
						ll num=K/dp[N][j+1];
						K%=dp[N][j+1];
						V.push_back(j);
						swap(tar[j],tar[V.size()]);
						vis[j]=1;
						while(V.size()<j-1) {
							for(x=i;x<=j;x++) if(vis[x]==0 && tar[x]!=(int)V.size()+1) {
								ll cand=fact[max(2,j-(int)V.size())-2];
								//cout<<x<<"!"<<num<<" "<<cand<<endl;
								if(cand<=num) {
									num-=cand;
								}
								else {
									V.push_back(x);
									int a=tar[V.size()];
									int b=tar[x];
									tar[b]=a;
									tar[a]=b;
									vis[x]=1;
									break;
								}
							}
						}
						for(x=i;x<=j;x++) if(vis[x]==0) V.push_back(x);
						i=j+1;
						break;
					}
				}
			}
			FORR(v,V) cout<<v<<" ";
			cout<<endl;
		}
		
	}
}

まとめ

なんか回答ありきの無理やりな問題設定な気がして、余り好きではないな…。