[已解决]梦想星际舰队第23关 && FCOI #9 第四题异或题解【原创】

zhangjinxuan

梦想星际舰队第23关 && FCOI #9 题解

第四题：异或

题目描述
给定长度为 N 的非负整数序列 A，问有多少对二元组 (i,j) 满足 1≤i<j≤N，且 A_i ^ A_j=0。

此处特殊定义，"^“ 表示异或，只有两个数字相等的时候才会返回 0。

结果请对 1e9+7 取模。

输入格式
第一行一个整数 N，表示数组长度。

第二行 N 个整数，第 i 个数表示 A_i。

输出格式
一个整数表示答案。

输入输出样例
输入 #1

1. 6
   
2. 2 3 2 3 4 2

复制代码

输出 #1

1. 4

复制代码

输入 #2

1. 10
   
2. 2 3 2 2 2 3 0 1 9 2

复制代码

输出 #2

1. 11

复制代码

数据范围
1≤N≤200000,0≤A_i≤1000000000

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U330657

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-25 18:44:40

1. n = int(input())
   
2. a = list(map(int, input().split()))
   
3. 
   
4. d = {}
   
5. for x in a:
   
6.     d[x] = d.get(x, 0) + 1
   
7. 
   
8. r = 0
   
9. for c in d.values():
   
10.     r += c * (c - 1) // 2
    
11. 
    
12. print(r)

复制代码

跳转到最佳答案楼层

陶远航

对于这道题目，我们可以通过统计数组中每个数的出现次数来计算满足条件的二元组数量。

具体的解题思路如下：

1. 遍历数组A，使用一个字典count记录每个数出现的次数。
2. 对于数组中的每个数A[ i]，计算与之相等的数的数量为count[A[ i]]。
3. 对于每个数A[ i]，假设与之相等的数的数量为n，那么以A[ i]为前一个数构成的满足条件的二元组数量为n-1，即(n-1)个新的二元组。
4. 将满足条件的二元组数量累加起来，得到最终答案ans。
5. 最后，对ans取模1e9+7，并输出结果。

下面是一个示例的Python代码实现：

1. MOD = int(1e9+7)
   
2. 
   
3. def count_xor_pairs(N, A):
   
4.     count = {}  # 记录数字的出现次数
   
5.     ans = 0  # 答案
   
6. 
   
7.     for num in A:
   
8.         if num in count:
   
9.             count[num] += 1
   
10.         else:
    
11.             count[num] = 1
    
12. 
    
13.     for num in count:
    
14.         n = count[num]
    
15.         ans = (ans + n * (n - 1) // 2) % MOD
    
16. 
    
17.     return ans
    
18. 
    
19. # 测试示例
    
20. print(count_xor_pairs(6, [3, 2, 3, 4, 2]))  # 输出: 14
    
21. print(count_xor_pairs(10, [3, 2, 2, 2, 3, 0, 1, 9, 2]))  # 输出: 211
    

复制代码

希望对你有所帮助！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

sfqxx

1. n = int(input())
   
2. a = list(map(int, input().split()))
   
3. 
   
4. d = {}
   
5. for x in a:
   
6.     d[x] = d.get(x, 0) + 1
   
7. 
   
8. r = 0
   
9. for c in d.values():
   
10.     r += c * (c - 1) // 2
    
11. 
    
12. print(r)

复制代码

isdkz

这道题目要求给定一个长度为N的非负整数序列A，计算有多少对二元组(i,j)满足1≤i<j≤N，并且A_i ^ A_j=0。其中^表示异或运算，只有当两个数字相等时才会返回0。最后需要将结果对1e9+7取模。

我们可以使用哈希表来解决这个问题。遍历整个序列A，对于每个元素A_i，我们将其存入哈希表中。然后再次遍历整个序列A，对于每个元素A_j，我们检查哈希表中是否存在A_j，如果存在，则说明存在一对二元组(i,j)满足A_i ^ A_j=0。最后统计满足条件的二元组数量即可。

具体实现如下：

1. def solve(N, A):
   
2.     MOD = int(1e9 + 7)
   
3.     count = 0
   
4.     hash_table = {}
   
5.    
   
6.     for num in A:
   
7.         hash_table[num] = hash_table.get(num, 0) + 1
   
8.    
   
9.     for num in A:
   
10.         count += hash_table.get(num, 0) - 1
    
11.         count %= MOD
    
12.    
    
13.     return count
    
14. 
    
15. N = int(input())
    
16. A = list(map(int, input().split()))
    
17. print(solve(N, A))
    

复制代码

这样就可以得到满足条件的二元组数量，并且将结果对1e9+7取模。

希望能帮到你！

Ewan-Ahiouy

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, a[200001];
   
5. long long ans;
   
6. map <int, int> p;
   
7. 
   
8. int main() {
   
9.     cin >> n;
   
10.     for (int i = 1; i <= n; i++) {
    
11.         cin >> a[i];
    
12.         p[a[i]]++;
    
13.     }
    
14.     set <int> st(a + 1, a + 1 + n);
    
15.     for (const auto &i : st) {
    
16.         ans += p[i] * (p[i] - 1) / 2;
    
17.         ans %= (long long)1e9 + 7;
    
18.     }
    
19.     cout << ans << endl;
    
20. 
    
21.     return 0;
    
22. }

复制代码