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

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

https://loj.ac/problem/2351

分析:

• 首先有(2^{|?|})的暴力非常好做。
• 观察到(min(|1|,|0|,|?|)le 6)，我们只需要推出一个(2^{|0|})和(2^{|1|})的容斥式子
• 而这个式子也是很好推的。
• 考虑子集反演:
  (f(S)=sumlimits_{Tsubseteq S}g(T))
  (g(S)=sumlimits_{Tsubseteq S}(-1)^{|S|-|T|}f(T))
• 那么只需要求出(a_S=sumlimits_{Tsubseteq S}val_T)和(b_S=sumlimits_{Ssubseteq 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);
}