AtCoder ABC #168 : E - ∙ (Bullet)

この時期コンテスト多くて記事書くのが追い付かないよね。
https://atcoder.jp/contests/abc168/tasks/abc168_e

問題

2次元ベクトルがN個与えられる。
このうち1つ以上を選択するとき、内積が0となるベクトル対が含まれないようにしたい。
選び方は何通りか。

解法

まず条件を考える。
X座標もY座標も0でないベクトルA,Bのみを考えてみよう。
同時に含められないのは、Ax*Bx+Ay*By=0よりAx/Ay = -By/Bxである。

各ベクトルに対し、X座標とY座標の絶対値が互いに素となるように割っても上記条件は変化しない。
また、ベクトルを-1倍しても変化しない。
そこで、Y座標を正とし、X,Y座標互いの絶対値が素となるように割ることを考える。
これを正規化と呼ぶことにする。

そうすると、同時に含められないのは、互いに素な正整数a,bに対し、正規化後に(a,b)と(-b,a)の形になるベクトル対である。
C(a,b) := 入力のベクトルを正規化すると(a,b)になるものと(-b,a)になるものの個数のタプル
とする。
C(a,b) := (p,q)
とすると、これらp+q個のベクトルのうち、前者と後者の両方を選ぶことはできないので(2^p+2^q-1)通り選ぶことができる。
各(a,b)に対し、C(a,b)を求め、この値を掛けていけば解が出る。
なお、全体から「1個も選ばないケース」を1引いておく必要がある。

なお、0が含むケースは以下のように考えるとよい。

• X座標もY座標も0なものは、それ単独で選ぶことができるので、その分解に加算する。
• X座標だけ0なものと、Y座標だけ0なものは、同時には選択できない。
  • 上記C(a,b)で、例外として、「C(0,0) := X座標が0のベクトルの個数とY座標が0のベクトルの個数のタプル」として考えると他と同様に扱える。

int N;
map<pair<ll,ll>,pair<ll,ll>> M;
int Z;
ll p2[202020];
const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,201010) p2[i+1]=p2[i]*2%mo;
	
	
	cin>>N;
	FOR(i,N) {
		ll X,Y;
		cin>>X>>Y;
		if(X==0 && Y==0) Z++;
		else if(X==0) {
			M[{0,0}].first++;
		}
		else if(Y==0) {
			M[{0,0}].second++;
		}
		else {
			if(Y<0) X=-X,Y=-Y;
			ll g=__gcd(abs(X),abs(Y));
			X/=g;
			Y/=g;
			if(X<0) M[{Y,-X}].first++;
			else M[{X,Y}].second++;
			
		}
	}
	ll ret=1;
	FORR(m,M) {
		ll a=p2[m.second.first]+p2[m.second.second]-1;
		ret=(ret*a)%mo;
	}
	
	cout<<(ret+Z+mo-1)%mo<<endl;
	
	
}

まとめ

0の扱いが面倒だね。