E - ∙ (Bullet)(组合数学）

传送门

思路：显然对于一组 $(a,b)$ 只有两种情况， $pos1:$ 同号或者异号, $pos2：$ $a,b$ 存在0。

$pos1:$

且要使 $A_iA_j+B_iB_j=0\rightarrow \dfrac{A_i}{B_i}=\dfrac{-B_j}{A_j}$ 。显然是同号与异号进行组合。

$ep:i:(a,b),j:(b,-a)\rightarrow ab+b(-a)=0$

且我们只需考虑 $(a,b)$ 除去最大公因数 $gcd$ 的组合.

因为 $\dfrac{a}{b}=\dfrac{\dfrac{a}{gcd}}{\dfrac{b}{gcd}}$ 。

所以我们考虑储存同号的个数及对应异号的个数。(这里用 $map$ 实现即可）

对于当前组 $pair_i$ ，假设同号个数为 $cnt_1$ ,异号个数为 $cnt_2$ ，由于不能同时选同号和异号的，

显然我们可以只选同号或者只选异号的，这样有 $2^{cnt_1}+2^{cnt_2}$ 种情况。

$2^{cnt_1}$ 和 $2^{cnt_2}$ 同时包含了当前组一个数不选的情况，所以要减去1.

即对于当前组的贡献为 $pair_i=2^{cnt_1}+2^{cnt_2}-1$ .

所以根据乘法原理有:

$ans=pair_1\times pair_2\dots\times pair_n$

$pos2:$

1.显然当 $a,b$ 中只有一个 $0$ 时，等价于 $(1,0)$ 与 $(0,1)$ 进行组合，可以归为 $pos1$ .

2.当 $a=b=0$ 时，因为它们不能与其他数共存，只能单独存在。所以对于这样的数贡献为 $cnt_{a=b=0}$

由于集合的非空性：所以还要减去所有组一个数都不选的情况

$\therefore ans=pair_1\times pair_2\dots\times pair_n+cnt_{a=b=0}-1$

时间复杂度: $O(nlogn)$

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
int n,cnt;
ll ksm(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main(){
    map<pair<ll,ll>,pair<int,int> >mp;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        if(!a&&!b){
            cnt++;
            continue;
        }
        ll g=__gcd(a,b);
        a/=g,b/=g;
        if(b<0) a=-a,b=-b;//保证同号的时候都为正，异号的时候b恒为正. 
        if(a<=0) mp[{b,-a}].second++;//该组同号对应的异号个数. 
        else mp[{a,b}].first++;    //该组同号个数 
    }
    ll ans=1;
    for(auto it:mp){
        ans=(ans*(mod+ksm(2,it.second.first)+ksm(2,it.second.second)-1)%mod)%mod;//防止负数要+mod 
    }
    printf("%lld\n",(mod+ans+cnt-1)%mod);
    return 0;
}