torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Beginner Contest 168, E : ∙ (Bullet)

問題概要

 $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^x$ 通りの選び方がある
  • 仲が悪くなる種類のイワシがいて,その本数が $y$ 本 : $2^x + 2^y - 1$ 通りの選び方がある

となります.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;
}

*1:ここでは符号情報を 2 要素目にもたせていますが,一要素目でも構いません,多分

*2:Greatest Common Divisor : 最大公約数