IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【题解】ABC172 E. Bullet -> 正文阅读

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

题意

从集合中选一个非空子集,若满足 a_ia_j+b_ib_j=0i!=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;
}
  数据结构与算法 最新文章
寒假第一周总结
蓝桥杯python(题目思路即解答(笔记,持续
堆排序的理解
如何获得数组长度
NC61 两数之和
简谈ArrayList特有的方法
剑指offer - 调整数组顺序使奇数位于偶数前
【力扣】难度【简单】20. 有效的括号
LeetCode | 373. Find K Pairs with Smalle
链表中为什么要设置虚拟头结点dummy?
上一篇文章      下一篇文章      查看所有文章
加:2021-07-14 23:11:55  更:2021-07-14 23:12:49 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年1日历 -2022/1/20 0:40:10-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码