基础算法题——异或和之和(位运算、组合数)
程序员文章站
2022-06-07 18:53:57
...
异或和之和
解题思路
解题方案
暴力枚举:时间复杂度:O(n3),超时。
位操作+组合数:解铃还须系铃人。对于这种与、或、异或的位操作,一般也是通过位操作来解答。
总结规律
题目要求在 n 个正整数中枚举 3 个数进行位操作,若要确定 3 个数的异或结果,就要寻找对异或结果的位有影响的情况。
枚举可能情况:
0 ^ 0 ^ 0 = 0
0 ^ 0 ^ 1 = 1
0 ^ 1 ^ 0 = 1
0 ^ 1 ^ 1 = 0
1 ^ 0 ^ 0 = 1
1 ^ 0 ^ 1 = 0
1 ^ 1 ^ 0 = 0
1 ^ 1 ^ 1 = 1
①、当 3 个都为 1 时,异或的结果为 1 。
②、当 2 个为 0 时,异或结果为 1 。
③、除了 ①、② 外,其余情况为 0 。
代码解析
①、枚举每一位二进制数的值,先对 mod 求余防止溢出。
eg:1(1), 2(10), 4(100), 8(1000)…
f[0]=1;
for(int i=1; i<64; i++)
f[i] = (f[i-1]<<1)%mod;
②、统计 n 个整数的每一位 1 的个数及 0 的个数。
0 的个数 = n - 1 的个数。可以不必再求。
//统计 n 个整数每一位为 1 的数量
//eg:num[j]: n 个整数第 j 位为 1 的数量
for(int i=0; i<n; i++){
ll tmp;
scanf("%lld", &tmp);
for(int j=0; j<64; j++)
num_1[j] += (tmp>>j)&1;
}
③、计算出每一位异或和结果能够得到多少个 1 ( k ) ,最后将答案与该位大小 * 1 的个数( f [ i ] * k ) 累加起来,并求余。
for(int i=0; i<64; i++){
ll one=num_1[i], zero=n-num_1[i], k;
//1 0 0 | 0 1 0 | 0 0 1
if(zero>=2 && one>=1){
k = zero*(zero-1)*one/2%mod;
ans = (ans+k*f[i]%mod)%mod;
}
//1 1 1
if(one>=3){
k = one*(one-1)*(one-2)/6%mod;
ans = (ans+k*f[i]%mod)%mod;
}
}
注意优先级 :
‘*’、’/’ > ‘+’、’-’ > ‘%’ > ‘<<’、’>>’ > ‘=’
实现代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans=0;
int f[64]={0}, num_1[64]={0};
const int mod = 1e9+7;
int main(){
int n;
scanf("%d", &n);
f[0]=1;
for(int i=1; i<64; i++)
f[i] = (f[i-1]<<1)%mod;
//<<优先级小于 mod
for(int i=0; i<n; i++){
ll tmp;
scanf("%lld", &tmp);
for(int j=0; j<64; j++)
num_1[j] += (tmp>>j)&1;
}
for(int i=0; i<64; i++){
ll one=num_1[i], zero=n-num_1[i], k;
//0 0 1
if(zero>=2 && one>=1){
k = zero*(zero-1)*one/2%mod;
ans = (ans+k*f[i]%mod)%mod;
}
//1 1 1
if(one>=3){
k = one*(one-1)*(one-2)/6%mod;
ans = (ans+k*f[i]%mod)%mod;
}
}
//优先级 :
//'*'、'/' > '+'、'-' > '%' > '<<'、'>>' > '='
printf("%lld", ans);
return 0;
}
总结
位操作对于异或、与、或等位运算是十分有效的。
上一篇: 7-53-两个有序序列的中位数-编程题