問題
パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）F – Coprime Present
問題リンク：https://atcoder.jp/contests/abc195/tasks/abc195_f
解説
注意：一部で僕の思考過程を再現しながら解説します。最短ルートとは限りません。
利用する典型テクニック
- 半分全列挙 → bit DP
前置き
$N$ をカードの枚数 $B-A+1$とします。問題の制約から $N \le 73$ です。
$O(n2^{n/2})$ 時間で独立集合の数え上げ
カードが $40$ 枚程度なら、独立集合の数え上げで解ける。
カードを頂点、数字が互いに素でないカードの組を辺とすれば、独立集合の数を求める問題になります。この問題は、下の方法(後で使います)で $n$ 頂点に対して計算量 $O(n2^{n/2})$ で解けますが、今のままでは $n \le 73$ なので無理です。
- 頂点の隣接関係を $n$ 個のビット配列して持つ
- 頂点集合を $S_0$ と $S_1$ の $2$ つに分ける
- $S_0$ と $S_1$ それぞれについて、 bit DP で各部分集合 $s$ が独立集合かどうか求める
- $S_1$ での 2. の結果をうまく累積和(高速ゼータ変換)して、各部分集合 $s$ について $s$ の部分集合のうち独立集合であるものの個数を求める
- $S_0$ の各部分集合 $s$ について、 $s$ のどの頂点とも隣接しない $S_1$ の頂点の集合 $s_1$ として $s_1$ における 3. の結果を求め、足し合わせる
偶数を特殊扱い
奇数すべてと偶数高々 $1$ つの場合(高々 $39$ パターン)について求まればよい。
偶数は複数選べません。これが求まれば、「偶数を含まない場合」と「特定の偶数を含む場合」が求まり、足し合わせれば答えになります。
計算量は、各パターンで $O(N2^{N/4})$ 、パターン数 $O(N)$ なので全体で $O(N^22^{N/4})$ ですが、TLE します(しました)。
提出コード(TLE)：https://atcoder.jp/contests/abc195/submissions/20896332
計算結果の使いまわし
偶数を含まない場合の結果を繰り返し用いて、全体で $O(N2^{N/4})$ 時間で求められる。
各パターンで計算内容はほぼ変わりません。「特定の偶数 $x$ を含む場合」は、「偶数を含まない場合」のうち、 $x$ と隣接するものを含まないものの個数です。「偶数を含まない場合」の結果を使って次のように $O(2^{N/4})$ 時間で求められます。
- 前計算として、 $S_0$ の各部分集合 $s$ について、 $s$ のどの頂点とも隣接しない $S_1$ の頂点の集合を $s_1(s)$ として保存しておく
- $S_0$ の各部分集合 $s$ で $x$ と隣接する頂点を含まないものについて、 $x$ と全く隣接しない $s_1(s)$ の頂点の集合を $s_1$ として $s_1$ における 3. の結果を求め、足し合わせる
提出コード
コンテスト後の提出：https://atcoder.jp/contests/abc195/submissions/20897771 https://atcoder.jp/contests/abc195/submissions/20927992 (2021 年 4 月 24 日 訂正、リンク先は同じです )
計算量は前述の通り、 $O(N2^{N/4})$ です。
コンテスト中の提出：https://atcoder.jp/contests/abc195/submissions/20897771
計算量は定数倍が小さめの $O(N^22^{N/4})$ です。