JOI 2018 Final E 毒蛇越狱 题解

· · 题解

这是一种经典的做法，题解里竟然没有。

设 S 中 0,1,\texttt{?} 的个数分别为 a,b,c。

算法一：暴力将每个 \texttt{?} 换成 0 或 1 求和，时间复杂度 O(2^c)。

算法二：对 0 容斥，也就是写成 (\times s(0))=(\times (s(\texttt{?})-s(1))) 的形式，将每个 0 换成 \texttt{?} 和 1，而对于只有 \texttt{?} 和 1 的情况可以直接预处理高维后缀和后计算，时间复杂度 O(2^a)。

算法三：对 1 容斥，过程同上，用高维前缀和计算，时间复杂度 O(2^b)。

选取最优的算法，单次询问时间复杂度 O(\min(2^a,2^b,2^c))，而由于 a+b+c=n 所以我们有 \min(a,b,c)\leq \dfrac{n}{3}，加上高维前后缀和的复杂度，总的时间复杂度为 O(q2^{\frac{n}{3}}+n\times 2^n)。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1200010;
int l,q,ans,cnt0,cnt1,cntq,sz0,sz1,cq[30],c0[30],c1[30],a[MAXN],b[MAXN],c[MAXN];
char t[30],s[MAXN];
void dfsq (int x,int msk) {
    if (x==cntq+1) {ans+=a[msk];return;}
    dfsq(x+1,msk);
    dfsq(x+1,msk|(1<<cq[x]));
    return;
}
void dfs0 (int x,int flg,int msk) {
    if (x==cnt0+1) {ans+=c[msk]*flg;return;}
    dfs0(x+1,flg,msk);
    dfs0(x+1,-flg,msk|(1<<c0[x]));
    return;
}
void dfs1 (int x,int flg,int msk) {
    if (x==cnt1+1) {ans+=b[msk]*flg;return;}
    dfs1(x+1,flg,msk|(1<<c1[x]));
    dfs1(x+1,-flg,msk);
    return;
} 
int main () {
    scanf("%d%d%s",&l,&q,s+1);
    for (int i=0;i<(1<<l);i++) {a[i]=b[i]=c[i]=s[i+1]-'0';}
    for (int i=1;i<(1<<l);i<<=1) {
        for (int j=0;j<(1<<l);j+=(i<<1)) {
            for (int k=0;k<i;k++) {b[i+j+k]+=b[j+k];}
        }
    }
    for (int i=1;i<(1<<l);i<<=1) {
        for (int j=0;j<(1<<l);j+=(i<<1)) {
            for (int k=0;k<i;k++) {c[j+k]+=c[i+j+k];}
        }
    }
    for (int i=1;i<=q;i++) {
        scanf("%s",t+1);
        for (int i=1;i<=l/2;i++) {swap(t[i],t[l-i+1]);}
        cnt0=0,cnt1=0,cntq=0,sz0=0,sz1=0;
        for (int i=0;i<l;i++) {
            if (t[i+1]=='0') {c0[++cnt0]=i;}
            else if (t[i+1]=='1') {c1[++cnt1]=i,sz1|=(1<<i);}
            else {cq[++cntq]=i,sz0|=(1<<i);}
        }
        ans=0;
        if (cntq<=6) {dfsq(1,sz1);}
        else if (cnt0<=6) {dfs0(1,1,sz1);}
        else {dfs1(1,1,sz0);}
        printf("%d\n",ans);
    }
    return 0;
}