E - ∙ (Bullet) ATcodr beginner 168

思维题,最近没怎么写题,思维都有点跟不上了。

题解:把每个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;
} 

 

上一篇:python练习003


下一篇:题目2:一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?