苹果电脑做网站设计/最近发生的新闻

题意：
n个数，求多少个数满足$$\left(\genfrac{}{}{0ex}{}{a[i]}{a[j]}\right)$$为奇数。

思路：

由卢卡斯定理可以得到，如果存在n的某个二进制位为0，且m的该二进制位为1，那么就有
$\left(\genfrac{}{}{0ex}{}{n}{m}\right)\mathrm{m}\mathrm{o}\mathrm{d}2=0$。

所以只有m是$n$的子集的时候$\left(\genfrac{}{}{0ex}{}{n}{m}\right)$才会是奇数。

那么实际上就是求子集和，这个直接用SOS DP就好了。

#pragma optimize("-O3")#include <cstdio>
#include <cassert>
#include <cmath>
#include <vector>
#include <cstring>using namespace std;typedef long long ll;
const int maxn = (1 << 21) + 5;
int dp[maxn],cnt[maxn];int main() {int T;scanf("%d",&T);while(T--) {memset(dp,0,sizeof(dp));memset(cnt,0,sizeof(cnt));int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {int x;scanf("%d",&x);dp[x]++;cnt[x]++;}int all = 1 << 21;for(int j = 0;j <= 21;j++) {for(int i = all;i >= 0;i--) {if(i & (1 << j)) {dp[i] += dp[i ^ (1 << j)];}}}ll ans = 0;for(int i = 0;i <= all;i++) {if(cnt[i]) {ans += 1ll * dp[i] * cnt[i];}}printf("%lld\n",ans);}return 0;
}