基础算法题——异或和之和（位运算、组合数）

川长思鸟来 2022-12-14 13:39 122阅读 0赞

### 异或和之和 ###

[题目链接][Link 1]  
![题目1][1]  
![题目2][2]

--------------------

#### 解题思路 ####

解题方案  
**暴力枚举**：时间复杂度：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;
    }

#### 总结 ####

位操作对于异或、与、或等位运算是十分有效的。

[Link 1]: https://ac.nowcoder.com/acm/contest/5600/J
[1]: /images/20221123/64c9118d940445a9b067760efc4a94ae.png
[2]: /images/20221123/a6a4a017ec9f41de959d86683a33ffc0.png