Code Festival Team Relay 2018 : H - 最悪のバス停決定戦

これも教育的な問題。
https://beta.atcoder.jp/contests/cf18-relay-open/tasks/relay2018_h

問題

2^N人で勝ち抜き戦のトーナメントを行うことを考える。
各人の番号は1～2^Nであり、両者が対戦すると基本的には番号の小さい側が勝つ。

ここで、M番の人について考える。
M番の人は、自身より小さい番号の相手に対しても、特別にK回まで勝利できるとする。
トーナメントの組み合わせ(2^N)!通りに対し、M番の人が優勝するケースは何通りか。

解法

自分より小さい番号の人A(=M-1)人はどんな番号でも自分より強いので同一視してよく、自分より大きな番号の人B(=2^N-M)人はどんな番号でも自分より弱いので同一視してよい。
また、M番の人はトーナメントの左端にいることにしよう。

その分は、あとで解を求める際にA!*B!*(2^N)倍して調整すればよい。
(A!はA人の並び順、B!はB人の並び順で、2^NはM番の人の初期位置の組み合わせ)

M番の人は、1～N回戦を戦い抜いていくわけだが、その際i回戦では2^(i-1)人の勝者と戦うことになる。
その際、2^(i-1)人の中に1人でも自分より強いA人が混ざっていたら、その人には勝てないか、特別に勝利できるK回のうちの1回を消費する。

dp(mask) := M番以外の人の(A+B)=(2^N-1)人の初期位置を考えたとき、maskの下からi bit目が1のとき、i回戦の対戦相手がA人のうちの誰かであるような組み合わせ
上記値を求めれば、bitcount(mask)≦Kである範囲でdp(mask)の総和を求めればよい。
dp(mask)の求め方だが、包除原理を用いてO(3^N)または高速ゼータ変換の要領でO(N*2^N)で処理できる。
前者だとおそらく間に合わないので後者を考える。

まずdp(mask)となる条件として、(幸いにも)maskを2進数の値をみなすと、A人がこれらの回戦の勝者となりうるケースはComb(mask, A)である。
そこから、mask中A人を配置してみたけど、実際にはA人が配置されない回戦もあるケースを高速ゼータ変換で引いていくとよい。

int N,M,K;
int A,B;
const int NUM_=1400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
ll mo=1000000007;
ll dp[1<<21];

ll comb(ll N_, ll C_) {
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	A=M-1;
	B=(1<<N)-M;
	
	comb(1,1);
	
	ll ret=0;
	int mask;
	FOR(mask,1<<N) dp[mask]=comb(mask,A);
	FOR(i,N) FOR(mask,1<<N) if(mask&(1<<i)) dp[mask]+=mo-dp[mask^(1<<i)];
	FOR(mask,1<<N) if(__builtin_popcount(mask)<=K) ret+=dp[mask]%mo;
	ret%=mo;
	(ret*=fact[A]*fact[B]%mo)%=mo;
	cout<<(ret<<N)%mo<<endl;
	
}

まとめ

シンプルな設定でいいね。
N=16ぐらいだとO(3^N)でどうにかなるけど、N=20だとO(N*2^N)が要りそうなのでこのテクは覚えておこう。