[数据结构与算法]【题解】ABC172 E. Bullet

题意

从集合中选一个非空子集，若满足 a_ia_j+b_ib_j=0 ，i!=j 则不合法。求方案总数。n<=5e5 。

Solution:

稍作变形：a_i/b_i=-b_j/a_j

做到这里，我们把 a_i/b_i 存入 map ，然后在 map 中查找一个值，计算另一个值即可。每一对的贡献为 2^x+2^y-1 。

但是我们可以继续变形：

(a_i/b_i)*(a_j/b_j)=-1 ，于是乎将 a_i/b_i 配对即可。

注意 double 可能有误差。我们考虑用 pair<x,y> 存储一个分数，同时保证 x>=0 。

这里要特判 (0,0) 的情况，因为和任何一对都会不合法。

最后去掉空集的情况。答案为 mul+zero-1 。时间复杂度 O(nlogn) 。

本题同样因为取模的特判 wa 了很多次。要长记性。

#include<bits/stdc++.h>
#define All(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define ll long long
#define double long double
#define pll pair<long long,long long>
using namespace std;
//Task : atcoder abc
//author : cqbzly
const int mod=1e9+7;
int n,m,zero;
vector<pll> a;
set<pll> b;
map<pll,int> value; 
map<pll,bool> vis;
ll fpow(ll x,ll y) {
	ll mul=1;
	for(;y;y>>=1) {
		if(y&1) mul=mul*x%mod;
		x=x*x%mod;
	}
	return mul; 
} 
ll gcd(ll x,ll y) {
	return (y==0)?x:gcd(y,x%y);
}
int main() {
//	freopen("data.in","r",stdin);	
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) {
		ll x,y; cin>>x>>y;
		if((x==0&&y==0)) zero++;
		else {
			ll z=gcd(x,y);
			x/=z,y/=z;
			if(x<0) x=-x,y=-y;
			value[make_pair(x,y)]++;
			b.insert(make_pair(x,y));
		}
	}
	ll mul(1);
	//search for one
	for(auto x:b) {
		if(vis[x]) continue;
		vis[x]=1;
		pll y=make_pair(-x.second,x.first);
		if(y.first<0) y.first=-y.first,y.second=-y.second;
		vis[y]=1;
		mul=mul*(fpow(2,value[x])+fpow(2,value[y])-1)%mod; 
	}
	mul=(mul+zero-1)%mod;
	if(mul<0) mul+=mod;
	cout<<mul;
}