题意： n个数，求多少个数满足 ( a [ i ] a [ j ] ) \tbinom{a[i]}{a[j]} (a[j]a[i])为奇数。
思路： 由卢卡斯定理可以得到，如果存在n的某个二进制位为0，且m的该二进制位为1，那么就有 ( n m ) m o d 2 = 0 \tbinom{n}{m}\mod2=0 (mn)mod2=0。
所以只有m是 n n n的子集的时候 ( n m ) \tbinom{n}{m} (mn)才会是奇数。
那么实际上就是求子集和，这个直接用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; }