【题解】毒蛇越狱(FWT+容斥)

问了一下大家咋做也没听懂，按兵不动没去看题解，虽然已经晓得复杂度了....最后感觉也不难

用FWT_OR和FWT_AND做一半分别求出超集和和子集和，然后

枚举问号是01，裸的，\(O(2^{cnt[?]})\)
默认问号是1，利用子集和求，\(O(2^{cnt[1]})\)
默认问号是0，利用超集和求，\(O(2^{cnt[0]})\)

可以知道\(min(cnt)\le n/3\)，所以复杂度\(O(n2^n 2^{n/3}Q)\)

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

	int ret=0,f=0,c=getchar();

	while(!isdigit(c)) f|=c==45,c=getchar();

	while( isdigit(c)) ret=ret*10+c-48,c=getchar();

	return f?-ret:ret;

}

const int maxn=1<<20|1;

char s[maxn];

int data[maxn],c[maxn],s0[maxn],s1[maxn],n,q;

int cnt[3];

inline void FWT_AND(int*a,const int&len,const int&tag){

	for(int t=1;t<len;t<<=1)

		for(int i=0;i<len;i+=t<<1)

			for(int k=0;k<t;++k)

				a[i+k]+=a[t+i+k]*tag;

}

inline void FWT_OR(int*a,const int&len,const int&tag){

	for(int t=1;t<len;t<<=1)

		for(int i=0;i<len;i+=t<<1)

			for(int k=0;k<t;++k)

				a[t+i+k]+=a[i+k]*tag;

}

int num[maxn],u;

int main(){

	n=qr(); q=qr();

	u=(1<<n)-1;

	scanf("%s",s);

	for(int t=1;t<1<<n;++t) num[t]=num[t^(t&-t)]+1;

	for(int t=0;t<1<<n;++t) data[t]=s[t]-48,s0[t]=data[t],s1[t]=data[t];

	FWT_AND(s0,1<<n,1); FWT_OR(s1,1<<n,1);

	while(q--){

		if(scanf("%s",s)==EOF) return 0;

		memset(cnt,0,sizeof cnt);

		for(int t=0;t<n;++t){

			if(isdigit(s[t])) c[t]=s[t]==49;

			else c[t]=2;

			++cnt[c[t]];

		}

		int base=0,wen=0,ans=0,k=min({cnt[0],cnt[1],cnt[2]});

		for(int t=0;t<n;++t)

			if(c[t]<=1) base=base<<1|c[t],wen<<=1;

			else wen=wen<<1|1,base<<=1;

		if(cnt[2]==k){

			for(int t=wen;~t;--t>=0?t&=wen:t)

				ans+=data[t|base];

		}else if(cnt[1]==k){

			for(int t=base;~t;--t>=0?t&=base:t){

				int g=t|wen;

				if(num[base^t]&1) ans-=s1[g];

				else ans+=s1[g];

			}

		}else{

			base^=u; base^=wen;

			for(int t=base;~t;--t>=0?t&=base:t){

				int g=t|wen;

				if(num[base^t]&1) ans-=s0[g^u];

				else ans+=s0[g^u];

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

【题解】毒蛇越狱(FWT+容斥)

【题解】毒蛇越狱(FWT+容斥)

最新文章

热门文章