ARC093 F : Dark Horse(1100)
作成日：2018.08.18
最終更新日：2018.08.18
問題概要
$2^N$人の選手がトーナメントを行う。
各試合では原則番号が小さい選手が勝つが、選手$A_i$は選手$1$に勝つ。
トーナメントは選手が一列に並び、先頭から2人ずつ試合を行い、勝った方のみが順番を保ったまま残り新しい列を作ることを、選手が1人になるまで繰り返すことで行われる。
この時、選手$1$が優勝するような選手の並び方の個数を$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq N,M \leq 16$
$2 \leq A_1 \lt A_2 \lt ... \lt A_M \leq 2^N$
考え方
このトーナメントでは優勝するまでに$N$戦勝つ必要がある。
選手$1$が優勝するには、戦う(それまでに負けている可能性もあるが、選手$1$が順当に勝ち上がった場合に試合を行うという意味でこの語を用いる、以下でも同様)$N$人の中に選手$A_i$が入っていなければ良い。
$i$戦目に選手$j$と戦う時、それまでに選手$j$と直接戦った選手の番号は$j$より大きい。
同様に考えると、選手$j$と直接戦った選手と直接戦った選手......の番号はいずれも$j$より大きい。
すなわち、$j$より番号の大きい選手がすでに$(2^{i-1}-1)$人敗退していることが分かる。
仮に選手$1$が$i$戦目に選手$j$と戦うとだけ決めたとすると、それがあり得る場合の列の並び方は選手$j$の位置$2^{i-1}$通りに$j$より大きい番号の選手$(2^N-j)$人から$(2^{i-1}-1)$人選んで並べる並べ方である$\frac{(2^N-j)!}{(2^N-j-(2^{i-1}-1))!}$通りをかけたものだけある。
選手$1$が優勝するような選手の並び方の個数を包除原理で求めることを考える。
先の考察から、ある選手と戦う時の並び方に必要なのはその選手より番号の大きい選手が何人残っているかと何戦目に戦うかの情報であることが分かる。
そこで大きい順に$A_i$を見て、何戦目に戦うかもしくは戦わないかを決めていくことにする。
この時、すでに選ばれた対戦位置が分かれば今見ている選手より番号が大きい選手が何人並び終えているか分かるから、$i$戦目が残っていたら$(i-1)$桁目を立てておくbitmaskを持っておく。
するとまだ選ばれていない対戦位置$k$に今見ている選手$A_i$を置くことを確定させるために必要な選手の並べ方は、それが可能であればこれまでの並べ方に$2^k \times$$\frac{(mask + 1 - A_i)!}{(mask + 1 - A_i - (2^k - 1))!}$をかけただけある。
また選手$1$と選手$A_i$が戦わない時には決まる枠がないので、これまでの並べ方をそのまま伝播させる。
このようにしてbitmaskと$A_i$のうち戦う選手の数をもってDPをすれば、状態$O(2^N M^2)$、遷移$O(N)$となる。
これでもギリギリ間に合うと思うが、包除原理の性質を使って状態を$O(2^N M)$にできるのでそうする。
すなわち包除原理では選んだ数の偶奇さえわかれば良いということである。
加えて偶数、奇数個選んだ時にはそれぞれ正、負で加えられるので、遷移の時に加える数を$-1$倍することでDPで持つ状態を$1$つなくすことができる(参考：DEGwer氏の数え上げテクニック集の15.2)。
以上により階乗とその逆数を前計算しておけば、DPを$O(2^N NM)$で行える。
答えは各bitmask(=残っている枠の数)において、DPで求めた値に$mask!$をかけたものの総和に、選手$1$の位置$2^N$通りをかけたものになる。
ソースコード
マクロ等はこちら
const LL mod = 1e9 + 7;
const int MC = 16;
int N,M;
int A[MC];
LL dp[MC+1][1<<MC];
LL f[(1<<MC)+1] , fi[(1<<MC)+1]; //f[x] = x! , fi[x] = 1/x!
void build(){
f[0] = 1;
repp(i,0,1<<N) f[i+1] = f[i] * (i+1) % mod;
fi[1<<N] = 1;
for(LL x = mod - 2 , y = f[1<<N] ; x > 0 ; x /= 2 , y = y * y % mod) if(x&1) (fi[1<<N] *= y) %= mod;
repm(i,1<<N,0) fi[i-1] = fi[i] * i % mod;
}
int main(){
cin >> N >> M;
repp(i,0,M) cin >> A[M-1-i];
build();
dp[0][(1<<N)-1] = 1;
repp(i,0,M) repp(mask,0,1<<N){
repp(k,0,N) if((mask&(1<<k)) && mask - (1<<k) >= A[i] - 2)
(dp[i+1][mask-(1<<k)] -= dp[i][mask] * (1<<k) % mod * f[mask-A[i]+1] % mod * fi[mask-A[i]+2-(1<<k)]) %= mod;
(dp[i+1][mask] += dp[i][mask]) %= mod;
}
LL ans = 0;
repp(mask,0,1<<N) (ans += dp[M][mask] * f[mask]) %= mod;
if(ans < 0) ans += mod;
cout << ans * (1<<N) % mod << endl;
return 0;
}解法まとめ
$A_i$を降順に見ていき、そのうちどこまで見たかと選んだ対戦位置をもつbitmask(=まだ選ばれていない人数)を状態($\langle i,mask \rangle$と表わす)に持つDPを行う。
初期化は$\langle 0,2^N-1 \rangle$のみ$1$、残りは$0$である。
$\langle i,mask \rangle$からの遷移は$\langle i+1,mask \rangle$へ$1$、$mask$の$k$桁目が立っていて遷移の分母の階乗の中身が非負になるような$k$に対して$\langle i+1,mask-2^k \rangle$へ$-2^k \times$$\frac{(mask+1-A_i)!}{(mask+1-A_i-(2^k-1))!}$の係数で足しこむことで行う。(18,20-25行)
答えは$2^N \sum_{mask}{mask! \langle M,mask \rangle}$である。(26-29行)