Counting Good Teams Gym - 101484K （高维前缀和）

题目

https://vjudge.net/problem/Gym-101484K

题意

给你n个数 问有多少合法数对

定义合法为 A||B > max(A,B)

思路

高位前缀和 看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[(1<<21)|5],cnt[(1<<21)|5];
//  子集出现的次数  这个数出现的次数
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){int k;scanf("%d",&k);dp[k]++;cnt[k]++;}ll ans=1ll*n*(n-1)/2;for(int i=0;i<m;i++)for(int j=(1<<m)-1;j>0;j--)if(j&(1<<i))dp[j^(1<<i)]+=dp[j];for(int i=0;i<(1<<m);i++){ans-=1ll*(dp[i]-cnt[i])*cnt[i]; //(子集-本身)*本身ans-=1ll*(cnt[i]-1)*cnt[i]/2;  //自己和自己组合}printf("%lld\n",ans);
}