Codeforces Round #383 (Div. 2) B. Arpa’s obvious problem and Mehrdad’s terrible solution 数论、易错

My Solution

题意：找出多少组ai和aj 使 ai ^ aj == x.

数论、易错

ai ^ aj == x.   =>   ai ^ x  == aj

这样把sz[ai] 为数ai出现的次数，对于每个ai，ans += sz[ai] * sz[ai ^ x] ;  sz[ai ^ x] = 0; //即每一对 ai 和 aj 只处理一次。

很显然还有一个特殊情况，即x == 0 的时候， ai ^ ai == 0, 故此时特殊处理  ans += sz[ai] * (sz[ai] - 1) / 2;

然后 中间过程有int相乘(sz[ai] * sz[ai ^ x] )(sz[ai] * (sz[ai] - 1) / 2) ，故 int 很可能会溢出，故用long long

复杂度 O(n)

#include 
#include 
#include 

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx