[coci2011]友好数对 容斥
2024-08-29 09:28:07
无趣的小x在玩一个很无趣的数字游戏。他要在n个数字中找他喜欢友好数对。
他对友好数对的定义是:如果有两个数中包含某一个以上相同的数位(单个数字),这两个数就是友好数对。
比如:123和345 就是友好数对,因为都包含数位3,显然123和234也是由号数对。而12和34则不是友好数对,因为它们没有相同的数位。
刚拿到题没怎么读懂,因为我直观的想法是存一下扫一遍就行了,后来一想,得用容斥;又犯蠢了;
其实这道题的容斥比较基本,看代码吧;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
#define LL long long
int n;
LL x=;
int b[<<],c[<<];
void init(){
cin>>n;
int y,p;
for(int i=;i<=n;i++){
scanf("%I64d",&x);
p=;
while(x!=){
y=x%;
x/=;
p=p|(<<y);
}
b[p]++;
}
}
LL col(LL x){return x*(x-)/;}
void work(){
for(int i=;i<<<;i++)
for(int j=;j<<<;j++)
if((i|j)==i)c[j]+=b[i];
int sum=;
LL ans=;
for(int i=;i<<<;i++){
sum=;
for(int j=;j<;j++){
if(i&(<<j))sum++;
}
if(sum%)ans+=col(c[i]);
else ans-=col(c[i]);
}
cout<<ans<<endl;
}
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
init();
work();
}
最新文章
- 通过Wireshark抓包进行Cookie劫持
- jquery 实现 返回顶部
- 网络编程3--毕向东java基础教程视频学习笔记
- JavaScript——事件模型
- MyEclipse 10 中如何更改字体
- scrapy爬虫框架入门教程
- I2c串行总线组成及其工作原理
- 双缓冲(Double Buffer)原理和使用
- module_init宏解析
- git push用法和常见问题分析
- python计算文件夹大小(linux du命令 简化版)
- UI自动化测试表单重要代码
- 手动搭建express框架
- c++(快速排序)
- [转]usdt omnicore testnet 测试网络
- 多线程系列之十一:Two-Phase Termination模式
- 区间dp板子题:[noi1995]石子合并
- PTA编程总结3—抓老鼠啊~亏了还是赚了?
- 使用Oracle DBLink进行数据库之间对象的访问操作
- 【PyQt5-Qt Designer】猜数字(小项目)