ABC 168 E - ∙ (Bullet)
問題
$n$ 未満の自然数からなる集合の空でない部分集合で、$X _ i X _ j + Y _ i Y _ j = 0 \ (i \neq j)$ なる $i,j$ を同時に含まないものの個数を求めよ。（$n \leq 2 \times 10 ^ 5$）
解説
まず、各 $(X _ i , Y _ i)$ について $X _ i$ と $Y _ i$ をそれぞれ最大公約数 $\mathrm{gcd}(X _ i , Y _ i)$ で割る。ただし $\mathrm{gcd}(0,0)=1$ とする。
次に、$Y _ i < 0$ なる $(X _ i , Y _ i)$ を $(-X _ i , -Y _ i)$ に、$(-1,0)$ を $(1,0)$ に変換する。
以上の操作により、$X _ i$ と $Y _ i$ は互いに素かつ $Y _ i \geq 0$ となるので、$X _ i > 0, Y _ i \geq 0$ かつ $X _ i X _ j + Y _ i Y _ j = 0 \ (i \neq j)$ ならば $(X _ j, Y _ j) = (- Y _ i, X _ i)$ となる。
$S _ {x,y}$ を $(x,y)=(X _ i, Y _ i)$ なる $i$ の集合とする。
$ \bigcup_ {x,y} S _ {x,y}$ の部分集合で、$X _ i X _ j + Y _ i Y _ j = 0 \ (i \neq j)$ なる $i,j$ を同時に含まないもののうち $i \in S _ {0,0}$ を含むものは、$i$ 以外を含めることができないので、その個数は $| S _ {0,0} |$ である。
$S _ {0,0}$ を除いて、
$$
\bigcup _ {x \neq 0 \lor y \neq 0} S _ {x,y}
= \bigcup _ {x > 0 \land y \geq 0} (S _ {x,y} \cup S _ {-y,x})
$$
のように分解する。
$S _ {x,y} \cup S _ {-y,x}$ の部分集合で、$i \in S _ {x,y}$ と $j \in S _ {-y,x}$ を同時に含まないものは $S _ {x,y}$ の部分集合と $S _ {-y,x}$ の部分集合からなり、空集合はどちらにも含まれるから、その個数は $2 ^ {| S _ {x,y} |} + 2 ^ {| S _ {-y,x} |} - 1$ である。
各 $S _ {x,y} \cup S _ {-y,x}$ からはそれぞれ独立に部分集合を作れるので、$ \bigcup _ {x > 0 \land y \geq 0} (S _ {x,y} \cup S _ {-y,x})$ の部分集合で、$X _ i X _ j + Y _ i Y _ j = 0 \ (i \neq j)$ なる $i,j$ を同時に含まないものの個数は
$$
\prod _ {x > 0 \land y \geq 0} (2 ^ {| S _ {x,y} |} + 2 ^ {| S _ {-y,x} |} - 1)
$$
最後に $S _ {0,0}$ も含めて、空集合を除くと、求める部分集合の個数は
$$
\prod _ {x > 0 \land y \geq 0} (2 ^ {| S _ {x,y} |} + 2 ^ {| S _ {-y,x} |} - 1) + | S _ {0,0} | -1
$$
実装
collections.defaultdict を使うと、存在しないキーにアクセスした場合にデフォルト値を返すことができる。ここではデフォルト値を $0$ として、$C[x,y]$ を $(x,y)=(X _ i, Y _ i)$ なる $i$ の個数とする。
また、$S$ を $(X _ i, Y _ i) = (x,y)$ または $(X _ i, Y _ i) = (-y,x)$ なる $i$ が存在するような $(x,y)$ の集合として、
$$
\prod _ {(x,y) \in S} (2 ^ {C[x,y]} + 2 ^ {C[-y,x]} - 1) + C[0,0] -1
$$
を計算している。
from collections import defaultdict from math import gcd C = defaultdict(lambda: 0) for i in range(int(input())): x, y = map(int, input().split()) g = max(gcd(x, y), 1) x, y = x // g, y // g if y < 0 or (x == -1 and y == 0): x, y = -x, -y C[(x, y)] += 1 S = set() for x, y in C: if x > 0 and y >= 0: S.add((x, y)) if x <= 0 and y > 0: S.add((y, -x)) ans = 1 p = 10**9 + 7 for x, y in S: ans *= pow(2, C[(x, y)], p) + pow(2, C[(-y, x)], p) - 1 ans %= p print((ans + C[(0, 0)] - 1) % p)
