問題概要
$N$ 本のイワシがあり，$i$ 番目のイワシは 2 つのパラメータ $A_i, B_i$ をもつ．ここからイワシを一本以上選んでクーラーボックスに入れるが，イワシ $i$ と イワシ $j$ は，$A_i A_j + B_i B_j = 0$ を満たすときに限って仲が悪く，同時には選べない．
イワシの選び方の総数を $\pmod{ 10 ^ 9 + 7 }$ で求めよ．
制約
- 入力は整数
- $1 \leq N \leq 2 \times 10 ^ 5$
- $-10 ^ { 18 } \leq A_i, B_i \leq 10 ^ { 18 }$
解法
まず，$( A_i, B_i ) = ( 0, 0 )$ なイワシについて考えると，他の任意のイワシ $j$ について
\begin{align*}
A_i A_j + B_i B_j &= 0 \\
0 A_j + 0 B_j &= 0 \\
0 &= 0
\end{align*}
となって他の誰とも仲が悪いので，選ぶのであればちょうど一本選ぶことしかできません．このパターンは，そのようなイワシの本数を数えておけば，選び方の総数は本数に等しくなります．これで，$( A_i, B_i ) = ( 0, 0 )$ なイワシは除外して考えることができるようになります．
以下では，$( A_i, B_i ) \neq ( 0, 0 )$ と仮定します．問題文の，仲が悪くなる条件の式をそのまま使おうとすると，添字 $i, j$ がある種「入り混じっている」ことから二重ループが必要そうに見えますが，それをやると TLE するので工夫します．ここでは，添字を分けるイメージで式をいじってみます．
\begin{align*}
A_i A_j + B_i B_j &= 0 \\
A_i A_j &= -B_i B_j \\
- \frac { A_i } { B_i } &= \frac { B_j } { A_j }
\end{align*}
ここで，$A_i$ や $B_i$ が $0$ だと数学的に都合が悪いので，この有理数をそのまま使うのではなく，分母と分子の順序対だと思うことにしましょう．つまり，左辺は $( A_i, -B_i )$ ，右辺は $( B_j, A_j )$ です*1．入力の時点で $A_i$ が負であった場合は，両方に $-1$ をかけて正規化します）．また，有理数の気持ちに戻って考えると使っているのは（両辺の等値性を比較していることから）傾きに関する情報なので，分数としては既約になっていて欲しいです．なので，各 $A_i, B_i$ を予め $\mathrm{ GCD }( A_i, B_i )$ で割っておく必要があります*2．で，細かい部分の整理が終わったところで順序対を眺めてみると，あるイワシと仲が悪いイワシとは，自身のパラメータを入れ替え，符号を反転させたものをパラメータとしてもつイワシであることが見て取れます．
こうなると，イワシを正規化して種類ごとに分けて数えてから，同時に選ぶと仲が悪くなるグループ対に着目しつつ数えられるような気になってきます．具体的には，ある種類のイワシに着目して，その本数が $x$ であるとき，
となります．2 の冪乗が出てくるのは，イワシの部分集合を選ぶ操作をしているためで，後者で $1$ を引いているのは，$0$ 本選ぶパターンを重複して数えることを防ぐためです．あとはこれを全種類に渡って計算しかけ合わせたものと，$( 0, 0 )$ のイワシを選ぶパターンを足せば答えが求まります．
計算量としては，イワシを std::map などで管理すれば $O( N \log N )$ になります．
コード
constexpr int MOD = 1000000007; // a^x を mod で求める // 反復二乗法 // O( log x ) long long mod_pow( long long a, long long x, long long mod ); int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); cout << setprecision( 12 ) << fixed; IN( int, N ); VT< LL > A( N ), B( N ); REP( i, N ) { cin >> A[i] >> B[i]; } LL zero_zero = 0; map< pair< LL, LL >, int > counts; REP( i, N ) { if ( A[i] == 0 && B[i] == 0 ) { ++zero_zero; continue; } const LL d = __gcd( A[i], B[i] ); A[i] /= d; B[i] /= d; if ( A[i] < 0 ) { A[i] *= -1; B[i] *= -1; } ++counts[ MP( A[i], B[i] ) ]; } LL res = 1; set< PII > done; FOR( p, counts ) { if ( EXISTS( done, p.fst ) ) { continue; } const LL a = p.fst.fst; const LL b = p.fst.snd; const int r1 = p.snd; const auto q = b < 0 ? MP( -b, a ) : MP( b, -a ); if ( EXISTS( counts, q ) ) { const int r2 = counts[q]; ( res *= mod_pow( 2, r1, MOD ) + mod_pow( 2, r2, MOD ) - 1 ) %= MOD; done.insert( q ); } else { ( res *= mod_pow( 2, r1, MOD ) ) %= MOD; } } ( res += zero_zero ) %= MOD; ( res += MOD - 1 ) %= MOD; cout << res << endl; return 0; }
