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; }