蓝桥杯第一场强者挑战赛（C）SOSdp

之前在cf上面接触过SOSdp（子集dp），这里就碰到了。

??????

思路： 异或运算即非进位加法运算，因此如果需要进位的话，那么就无法满足题意，因此条件弱化为不需要进位，也就是不存在同一位上面都是1。也就是说，对于而言，中为1的地方，其他数不能为1，也就是说其对答案的贡献为的子集的个数。

????????

#include <iostream>
using namespace std;
// SOS dp
int dp[(1 << 21)];
#define int long long
const int N = 21;
signed main()
{
	int n;
	cin >> n;
	int a[n];
	for(int i = 0 ; i <n ; i ++){
		cin >> a[i];
		dp[a[i]]++;
	}    
	int ans = 0;
	for(int i = 0;i < N; ++i) {
	    for(int mask = 0; mask < (1 << N); mask++){
	  	  if(mask & (1 << i))
	        dp[mask] += dp[mask^(1 << i)];
		}
	}
	for(int i = 0 ; i < n ; i ++){
	    ans += dp[(1 << N) - 1 - a[i]];
	}
	cout << ans;
  return 0;
}