洛谷——P4932 浏览器
2024-09-24 12:31:23
P4932 浏览器
__stdcall给了你n个点,第i个点有权值x[i],对于两个点u和v,如果x[u] xor x[v]的结果在二进制表示下有奇数个1,那么在u和v之间连接一个Edge,现在__stdcall想让你求出一共有多少个Edge。
如果你没能成功完成任务,那么__stdcall会让你痛苦一下,你这个测试点就没分了。
由于不小心看到这道题,然后一点儿思路都枚举,果断看了题解
发现了这么一句话(此题关键):
规律:当两个数的二进制数$1$的个数为一奇一偶时,他们抑或的值的二进制数的个数才为偶数,否则为奇数
那么答案显然是奇数个数乘以偶数个数
但是暴力统计时间复杂度为$O(nlogV)$,只可以通过$\%50$的数据
$bitset$貌似是优化了这个过程,$bitset.count()$STL中表示这个$bitset$的$1$的个数
#include<bits/stdc++.h> #define LL long long
#define N 10000005
using namespace std; LL n,a,b,c,d,x[N],sum[];
int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d,&x[]);
for(int i=;i<=n;i++){
x[i]=((a*x[i-]%d*x[i-]%d)%d+(b%d*x[i-]%d)%d+c%d)%d;
x[i]=(x[i]%d+d)%d;
}
for(int i=;i<=n;i++){
bitset<>p=x[i];
sum[p.count()&]++;
} printf("%lld\n",sum[]*sum[]); return ;
}
最新文章
- GZFramwork快速开发框架演练之会员系统(四)添加商品管理
- Java集合之TreeMap
- iOS _BSMachError: (os/kern) invalid capability (20)
- PostgreSQL Replication之第十一章 使用Skytools(5)
- ios上取得设备唯一标志的解决方案
- android开发之应用Crash自动抓取Log_自动保存崩溃日志到本地
- Hive - 建表和加载数据指令小结 以及使用Load data指令的注意事项
- Android setTag IllegalArgumentException
- VS2012下基于Glut OpenGL glDepthMask示例程序:
- Redis4.0 Cluster — Centos7
- 2019.04.16打卡(java 数组)
- Python-random模块-59
- Python_每日习题_0004_一年中的第几天
- MySQL数据库一
- Perl 文件处理范例
- Android GridView 滑动条设置一直显示状态
- Python 入门网络爬虫之精华版
- 文件名过滤器FilenameFilter的用法
- UOJ #56. 【WC2014】非确定机
- 技术分享:SSH实战项目