D - Choosing Up Sides

D - Choosing Up Sides - blogskol https://t.co/uX0A5alb4s
完全に理解した pic.twitter.com/7pRDFtWSpd
— ゴジラ＠競プロ (@gojira_kyopro) 2021年1月17日

有志が作ったこの記事の解説画像

一人を固定してやると
一回の試合でチームになる人数: $2^{N-1}-1$
自分以外の人数: $2^N-1$
なので試合回数を $A$ とすると $A(2^{N-1}-1)=n(2^N-1)$ が成り立つ必要がある
$GCD(2^{N-1}-1,2^N-1)=1$ っぽい*1ので $A$ が $2^N-1$ の倍数であることが言える
（Aをなるべく小さくしたいので）取り敢えず $A=2^N-1$ が出来ると信じて考える（この時 $n=2^{N-1}-1$ である）

2べきの問題は再帰を使えることが多いので再帰を検討する
つまり、 $N-1$ のケースについては解法を持ってる時を仮定する
$N-1$ のケースは $2^{N-1}$ 人に対して行うものなので、 $2^N$ 人を半分ずつグループX,グループYに分けてあげてグループごとに $N-1$ の解法を適用することを考える

$N-1$ の解法は各ペアに対して同じチームになる回数を $2^{N-2}-1$ にする
今は同じチームになる回数を $2^{N-1}-1$ 回にしたい

二つを見ていると（2べきの形から）取り敢えず各グループ $N-1$ の解法を二回適用してあげたくなる
実際、XとYそれぞれについて $N-1$ の解法を二回適用したのちX vs Yを一回行えばグループ内の各ペアについて同じチームになった回数は
$(2^{N-2}-1)2+1=2^{N-1}-1$
で上手くいく
一方でXY間のペアについてだけど、 $N-1$ の解法を一通り行うのにかかる回数が（同じチームになってほしい回数と等しい） $2^{N-1}-1$ であることに注目すると、 $N-1$ の解法を二周行う時に各XY間のペアについて一周は同じチーム、もう一周は違うチームとなってくれればいいことが分かる
これは実際1周目と2周目でY側だけABを反転させることで達成できることが簡単に分かる

コードでは実際に $i$ 番目の答えを構築してから $i+1$ 番目の答えを作ってる
atcoder.jp

*1:互除法の操作を考えると自明