ICPC 沈阳M - United in Stormwind SOSDP+FWT+容斥

46 阅读 0 评论 31 点赞

我是靠谱客的博主高大发夹，最近开发中收集的这篇文章主要介绍ICPC 沈阳M - United in Stormwind SOSDP+FWT+容斥，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：
题意是真的难懂，求题目集（0~1<<m）中满足>=k对不同的试卷，两张试卷不同当且仅当至少存在一位不同，而且该位在题目集里。 n<=2e5 m<=20
思路：
我们可以把a和b当做0和1处理，我们可以先求出 $i x o r j = k$ 的对数，为什么处理呢？因为对于任意某个位置为1的话那么就说明这两个试卷是不同的。怎么处理呢？可以fwt，a自己卷自己，先把a[0]减去n，然后记得a每个数/2，因为我们讨论的是i<j的情况，处理完以后，由于这个m比较小，我们可以二进制枚举每一种题目集的情况，假设赛制为x,那么显然我们要求的是 $假设t的当前枚举的数(sum_{t~and~i~!=0 ~and~i~!= 0}a[i])~>=k$ ,一开始我一看诶这不是i是t的子集就可以了吗，然后t除外的位置都没考虑，后来仔细想想发现这是错误的，那么我们想想能不能容斥，全集是n*(n-1)/2减去的就是k&t==0的点，那么我们需要保证k对于t的所有位置都要为0，别的位置可以任意取，那么显然可以nlogn sosdp，代表子集和，cnt-=(全集^t),然后判断cnt是否大于等于k就行了。

// Problem: M. United in Stormwind
// Contest: Codeforces - The 2020 ICPC Asia Shenyang Regional Programming Contest
// URL: https://codeforces.com/gym/103202/problem/M
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC target("avx")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
// created by myq 
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef pair<int,int> pii;
const int N = 4000010;
const int mod=998244353;
inline int read()
{
	int res=0;
	int f=1;
	char c=getchar();
	while(c>'9' ||c<'0')
	{
		if(c=='-')	f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		res=(res<<3)+(res<<1)+c-'0';
		c=getchar(); 
	}
	return res;
 } 
 ll a[N];
ll b[N];
ll dp[N];
int m;
void XOR(ll *a,int opt,int N)
{
    for(int i=1;i<N;i<<=1)
        for(int p=i<<1,j=0;j<N;j+=p)
            for(int k=0;k<i;++k)
            {
                ll X=a[j+k],Y=a[i+j+k];
                a[j+k]=(X+Y);a[i+j+k]=(X-Y);
                if(opt==-1)a[j+k]=1ll*a[j+k]/2,a[i+j+k]=1ll*a[i+j+k]/2;
            }
}
int main() 
{ 
	int n;
	ll k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		int cnt=0;
		for(int j=0;j<s.size();j++)
			if(s[j]=='A')
			cnt=cnt*2;
			else
			cnt=cnt*2+1;
			// cout<<cnt<<endl;
			a[cnt]++;
	}
	XOR(a,1,1<<m);
	for(int i=0;i<1<<m;i++){
		a[i]=a[i]*a[i];
	}
	XOR(a,-1,1<<m);

	for(int i=0;i<1<<m;i++){
		if(i==0)
		a[i]-=n;
		a[i]/=2;
		
	}
	memcpy(dp,a,sizeof a);
	for(int i=0;i<m;i++){
		for(int j=(1<<m)-1;j>=0;j--){
			if(j>>i&1){
				dp[j]+=dp[j^(1<<i)];
			}
		}
	}
	int res=0;
	for(int i=0;i<1<<m;i++){
		ll cnt=1ll*n*(n-1)/2;
		cnt-=dp[((1<<m)-1)^i];
		// cout<<cnt<<endl;	
		if(cnt>=k)
		res++;
	}
	cout<<res;
	return 0;
	
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/