107 C Arrangement

ようやく解けた。

問題

座席に1〜nの番号のn人が、以下の条件を満たすように座る。
m組の自然数a[i],b[i]が与えられる。
a[i]番目に座っている人の番号はb[i]番目に座っている人の番号より小さい。


このような座り方のうち、辞書順でy番目のものを求めよ。

制約条件

n≦16
m≦100
y≦10^18

方針

頭から当てはめ+ビットDP.
まずは、最初の座席に1番の人を座らせる。
残りのn-1個の座席の埋め方の場合の数をビットDPで求める。
この場合の数がy以下だったら、最初の座席の人は1番の人で確定。
そうでなかったら最初の座席に2番の人を座らせて〜、と繰り返す。
次の座席も同様に、順番に座らせた後で場合の数を計算していけばいい。


場合の数を求めるビットDPは、
dp[c][mask]に、c人が現在座った人の数で、maskが各座席が埋まっているか
の場合の数を持たせるメモ化再帰を行う。


ビットDP部分では、番号の小さい人から、それぞれの場所に座らせていく。

int n,m,k; ll y;
vector<vi> smallers,greaters;
int seat[20];
ll dp[20][1<<16];

vi nums;
ll rec(int prev,int c,int mask){
	if(dp[c][mask]>=0)return dp[c][mask];
	if(c==n)return 1;
	ll &ret=dp[c][mask]; ret=0;
	for(int i=prev;i<n;i++)if(!(1<<i&mask)){
		fr(j,smallers[i])if(*j<prev&&seat[*j]>nums[c-prev]||*j>=prev&&!(1<<*j&mask))goto FAIL;
		fr(j,greaters[i])if(*j<prev&&seat[*j]<nums[c-prev]||*j>=prev&&(1<<*j&mask))goto FAIL;
		ret+=rec(prev,c+1,mask^1<<i);
		FAIL:;
	}
	return ret;
}
ll solve(int c){
	if(c==n)return 1;
	nums.clear();
	rep(i,n)if(find(seat,seat+c,i)==seat+c)nums.pb(i);
	memset(dp,-1,sizeof(dp));
	return rec(c,c,0);
}
void run()
{
	cin>>n>>y>>m;
	smallers.clear(); smallers.resize(n);
	greaters.clear(); greaters.resize(n);
	rep(i,m){
		int a,b; cin>>a>>b; a--; b--;
		smallers[b].pb(a);
		greaters[a].pb(b);
	}
	y-=2001;
	rep(i,n)seat[i]=inf;
	if(solve(0)<=y){
		cout<<"The times have changed"<<endl; return;
	}
	rep(i,n){
		rep(j,n)if(find(seat,seat+i,j)==seat+i){
			seat[i]=j;
			fr(k,smallers[i])if(*k<i&&seat[*k]>j)goto FAIL;
			if(y<solve(i+1))break;
			else y-=solve(i+1);
			FAIL:;
		}
	}
	rep(i,n)cout<<seat[i]+1<<" "; cout<<endl;
}