LOJ#2351. 「JOI 2018 Final」毒蛇越狱
分析:
- 首先有\(2^{|?|}\)的暴力非常好做。
- 观察到\(min(|1|,|0|,|?|)\le 6\)，我们只需要推出一个\(2^{|0|}\)和\(2^{|1|}\)的容斥式子
- 而这个式子也是很好推的。
- 考虑子集反演:
\(f(S)=\sum\limits_{T\subseteq S}g(T)\)
\(g(S)=\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}f(T)\) - 那么只需要求出\(a_S=\sum\limits_{T\subseteq S}val_T\)和\(b_S=\sum\limits_{S\subseteq T}val_T\)就行了。
- 然后这个东西可以用\(fwt\)快速求出。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1100050
int L,Q;
int a[N],b[N];
char str[N],w[23],cnt[N];
void fwt(int *a,int l,int o) {
int i,j,k,t;
for(k=2;k<=l;k<<=1)for(t=k>>1,i=0;i<l;i+=k)for(j=i;j<i+t;j++)o?(a[j+t]+=a[j]):(a[j]+=a[j+t]);
}
char pbuf[20000000],*pp=pbuf;
int st[20],tp;
char buf[2000000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,2000000,stdin),p1==p2)?EOF:*p1++)
inline char rc() {
char s=nc();
while(s!='0'&&s!='1'&&s!='?') s=nc();return s;
}
int main() {
scanf("%d%d%s",&L,&Q,str);
int i,n=(1<<L);
for(i=0;i<n;i++) str[i]-='0',a[i]=b[i]=str[i],cnt[i]=cnt[i>>1]+(i&1);
fwt(a,n,1),fwt(b,n,0);
while(Q--) {
int c1=0,c0=0,cw=0,s1=0,s0=0,sw=0,ans=0,num=0;
for(i=0;i<L;i++) {
w[i]=rc();
if(w[i]=='0') c0++,s0|=(1<<(L-i-1));
else if(w[i]=='1') c1++,s1|=(1<<(L-i-1)),num|=(1<<(L-i-1));
else cw++,sw|=(1<<(L-i-1));
}
int mn=min(c0,min(c1,cw));
if(cw==mn) {
for(i=sw;i!=-1;i=i?(i-1)&sw:-1) {
ans+=str[i^num];
}
}else if(c1==mn) {
for(i=s1;i!=-1;i=i?(i-1)&s1:-1) {
if(cnt[s1^i]&1) ans-=a[i|sw];
else ans+=a[i|sw];
}
}else {
for(i=s0;i!=-1;i=i?(i-1)&s0:-1) {
if(cnt[i]&1) ans-=b[i|s1];
else ans+=b[i|s1];
}
}
tp=0;
do{ st[++tp]=ans%10,ans/=10;}while(ans);
while(tp) *pp++=st[tp--]+'0'; *pp++='\n';
}
fwrite(pbuf,1,pp-pbuf,stdout);
}