51nod 1622 集合对[算法马拉松19 C]

题目链接：https://www.51nod.com/contest/problem.html#!problemId=1622

题解：

设M = P xor A，则 M∈A，M是P的补集，M与P一一对应。

设N = Q xor B，则 N∈B，N是B的补集，N与B一一对应。

所以(P xor A)xor(Q xor B) = M xor N = A xor B

即求有多少对（M,N），M∈A，N∈B，满足上式。

因为属于A而不属于B的元素一定在M中，属于B而不属于A的元素一定在N中，A∩B的元素，要么同时属于M和N，要么都不属于，所以答案就是A∩B的子集个数2^c

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int mod = 1e9+7;
 6 typedef long long ll;
 7 ll pow(ll a, ll n){
 8     ll r = 1;
 9     ll t = a % mod;
10     while(n){
11         if(n & 1)
12             r = (r * t) % mod;
13         t = t * t % mod;
14         n >>= 1;
15     }
16     return r;
17 }
18 int main(){
19     ll a, b, c;
20     scanf("%lld%lld%lld", &a, &b,&c);
21     printf("%lld
", pow(2,c));
22     return 0;
23 }

View Code