LOJ #2351. 「JOI 2018 Final」毒蛇越狱

题面传送门

奇妙的看上去不能过的题目。

首先有一个非常sb的暴力，大概就是枚举?的子集，然后统计，时间复杂度\(O(2^{cnt_1})\)单次。

直接算没有优化空间，考虑子集容斥，先FWT预处理出\(f_i\)表示\(i\)的子集的和，然后枚举当前串\(1\)的子集算答案。时间复杂度\(O(2^{cnt_2})\)。平衡后复杂度\(O(2^{\frac{n}{2}})\)。

还是不能过，再考虑超集容斥，预处理\(g_i\)表示\(i\)的超集的和，然后枚举当前串的\(0\)算答案。时间复杂度\(O(2^{cnt_3})\)，平衡后复杂度\(O(2^{\frac{n}{3}})\)。

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=20+5,M=(1<<20)+5,K=1e5+5,mod=1e9+7,Mod=mod-1,INF=2e9+7;const db eps=1e-5;
int n,m,k,C1,C2,C3,x,y,z,f[M],g[M],H[M],Ans;char s[N],c[M];
int main(){
	freopen("1.in","r",stdin);
	int i,j,h;scanf("%d%d",&n,&m);k=(1<<n);scanf("%s",c);for(i=0;i<k;i++) g[i]=f[i]=c[i]-='0';
	for(i=2;i<=k;i<<=1) for(j=0;j<k;j+=i) for(h=j;h<j+i/2;h++) f[h]+=f[h+i/2],g[h+i/2]+=g[h];H[0]=1;for(i=1;i<k;i++) H[i]=H[i>>1]*(i&1?-1:1);
	while(m--){Ans=x=y=0;scanf("%s",s);C1=C2=C3=0;for(i=0;i<n;i++) C1+=(s[i]=='0'),C2+=(s[i]=='1'),C2+=(s[i]=='?');
		if(C2<=7){
			for(i=0;i<n;i++) s[i]=='1'&&(x|=(1<<n-i-1)),s[i]=='?'&&(y|=(1<<n-i-1));
			Ans=c[x];for(i=y;i;i=(i-1)&y) Ans+=c[x|i];
		}else if(C1<=7){
			for(i=0;i<n;i++) s[i]=='0'&&(x|=(1<<n-i-1)),s[i]=='1'&&(y|=(1<<n-i-1));
			Ans=H[0]*f[y];for(j=x;j;j=(j-1)&x) Ans+=H[j]*f[j|y];
		}else {
			for(i=0;i<n;i++) s[i]=='?'&&(x|=(1<<n-i-1)),s[i]=='1'&&(y|=(1<<n-i-1));
			Ans=H[0]*g[x];for(j=y;j;j=(j-1)&y) Ans+=H[j]*g[j|x];Ans=abs(Ans);
		}
		printf("%d\n",Ans);
	}
}