AtCoder ARC #093 : F - Dark Horse

1000pt台前半、実装は軽くても考察は重かったりして結構しんどいんだよな。
https://beta.atcoder.jp/contests/arc093/tasks/arc093_d

問題

2^N人が参加するN回戦まである勝ち抜き型のトーナメントを考える。
選手番号を1~2^Nとしたとき、勝敗は以下のように決まる。

• 1番以外の選手同士の試合は、番号の小さい方が勝ち。
• 1番の試合は、M人の集合Aに含まれる番号の選手が相手の場合、そちらの勝ち。含まれない場合、1番の勝ち。

トーナメントの組み方(2^N)!通り中、1番の選手が優勝するのは何通りか。

解法

1番の選手の位置は固定して考えることにする。その分最後に2^Nを掛ければよい。
1番の選手とi回戦目で当たるのは、2^(i-1)人の選手たちのうち最も小さい番号である。
i回戦目で1番の選手と当たる可能性のある位置の集合をS(i)とする。
N個のS(i)において、その中で最も小さい番号が集合Aに含まれるものではないようにしたい。

ここで、2番の選手から順にN個の集合S(i)に順に割り振っていくことを考える。
すでに１名以上が割当たっているS(i)には、それ以降の番号の人が追加されても1番の選手の勝敗に影響しない。
よってすでに1名以上が割当たっているかどうかをN bitのbitmaskで管理していこう。
S(i)に1名以上割当たっているなら、下からi bit目が立つとする。
その時、あるbitmaskの状態に対し、そのように人を割り振れる上限の人数はそのbitmaskの値に等しい。

さて、1名ずつS(i)に人を割り振りたいところだが、bitmaskが2^N通りあるのに2^N人を順に処理するとO(4^N)かかりTLEする。
あいにくAに含まれない人が大半なので、それらはまとめて処理しよう。

あとはEditorialと同じだが、以下のDPを考える。

• dp1(i,mask) := 2～A[i]までの人の割り振りが決まったとき、bitmaskの状態がmaskに一致する状態数
• dp2(i,mask) := 2～A[i]までの人の割り振りが決まったとき、bitmaskの状態がmaskの部分集合に一致する状態数
• dp3(i,mask) := 2～(A[i]-1)までの人の割り振りが決まったとき、bitmaskの状態がmaskの部分集合に一致する状態数
• dp4(i,mask) := 2～(A[i]-1)までの人の割り振りが決まったとき、bitmaskの状態がmaskに一致する状態数

入力のAは1-originの昇順列とし、A[0]=1とする。
dp1(0,0)=1から始め、以下のように順にDPを埋めていく。

• dp1(i,mask)→dp2(i,mask) : 高速ゼータ変換の要領で計算する。
• dp2(i,mask)→dp3(i+1,mask) : (A[i]+1)～A[i+1-1]の間の人を、(mask-A[i])個の空きスロットに埋めることを考える。これは階乗とその逆数の積を使い書ける。
• dp3(i+1,mask)→dp4(i+1,mask) : 高速メビウス変換の要領で計算する。
• dp4(i,mask)→dp1(i+1,mask) : A[i+1]番の人を既存のbitmaskの集合のどこかに加えることを考える。これはA[i+1]番の人が勝ち上がり1番と当たらないようにすることに等しい。

こうするとA[M]番までの人の割り当てが決まるので、あとはdp1(M,*)に対し(A[M]+1)～(2^N)番の人の割り当てを決めればよい。

int N,M;
int A[20];
ll dp1[17][1<<16];
ll dp3[17][1<<16];
ll mo=1000000007;
const int NUM_=1<<17;
ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>M;
	
	
	A[0]=1;
	dp1[0][0]=1;
	int mask,U;
	for(i=1;i<=M;i++) {
		cin>>A[i];
		FOR(j,N) FOR(mask,1<<N) if((mask&(1<<j))) (dp1[i-1][mask]+=dp1[i-1][mask^(1<<j)])%=mo;
		FOR(U,1<<N) {
			int t=U-(A[i-1]-1);
			int d=A[i]-A[i-1]-1;
			if(t>=d) dp3[i][U]=fact[t]*factr[t-d]%mo*dp1[i-1][U]%mo;
		}
		
		FOR(j,N) FOR(mask,1<<N) if((mask&(1<<j))) (dp3[i][mask]+=mo-dp3[i][mask^(1<<j)])%=mo;
		FOR(U,1<<N) if(U>=(A[i]-2)) dp1[i][U]=(U-(A[i]-2))*dp3[i][U]%mo;
		
	}
	
	ll ret=0;
	FOR(mask,1<<N) ret+=dp1[M][mask];
	ret=ret%mo*fact[(1<<N)-A[M]]%mo*(1LL<<N)%mo;
	cout<<ret<<endl;
	
}

まとめ

高速ゼータ変換は慣れてきたけど高速メビウス変換はいつも混乱する。