思维题,最近没怎么写题,思维都有点跟不上了。
题解:把每个sardine都看成一个平面的左边,然后保存个点和原点的斜率,在平面坐标中与斜率A垂直的斜率一定只有一个。所以如果两个斜率相垂直,那么我们把这俩斜率放一起,假设a和b的个数分别位C和D,那么选a不能选b,所以这种组合的个数为pow(2,C)+pow(2,D)-1,就是选a的话有pow(2,c)种可能,选b同理,最后减去同时选a和b的这种情况。如果没有和斜率d垂直的那么考虑斜率d是否取,这种组合的个数为pow(2,cnt[d])。然后将他们乘起来就可以了,最后还有减去一种情况,就是都不取。保存斜率的时候可以用mp来存。另外,如果遇到了0,0这种情况,要特殊处理一下,因为如果选0,0的话,就不能选其他的了。最后加上{0,0}的个数就行了。
code:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const ll N=2e5+7; struct stu{ ll x,y; bool friend operator < (const stu &a,const stu &b){ if(a.x==b.x) return a.y>b.y; return a.x>b.x; } }arr[N]; map<stu,ll>mp; ll ksm(ll x,ll y){ ll res=1; while(y){ if(y&1) res=res*x%mod; x=x*x%mod; y>>=1; } return res%mod; } int main(){ ll n,x,y; cin>>n; stu c; int pos=0; for(ll i=1;i<=n;i++){ cin>>c.x>>c.y; if(c.x==0&&c.y==0){ mp[{0,0}]++; continue ; } ll g=__gcd(c.x,c.y); c.x/=g;c.y/=g; if(c.x<0){ c.x=0-c.x; c.y=0-c.y; } if(mp[c]==0){ arr[pos++]=c; } mp[c]++; } ll ans=1; for(ll i=0;i<pos;i++){ if(mp[arr[i]]==0) continue ; ll a1=arr[i].x*(-1); ll b1=arr[i].y; ll c1=__gcd(a1,b1); b1/=c1;a1/=c1; if(b1<0) { b1=0-b1; a1=0-a1; } ll tmp=0; if(mp[{b1,a1}]==0){ tmp+=ksm(2,mp[arr[i]]); } else { tmp+=ksm(2,mp[arr[i]]); tmp=(tmp+mod)%mod; tmp+=ksm(2,mp[{b1,a1}]); tmp-=1; tmp=(tmp+mod)%mod; mp[{b1,a1}]=0; } ans*=tmp; ans=ans%mod; } ans=(ans+mp[{0,0}]-1+mod)%mod; cout<<ans<<endl; return 0; }