P12294

lsj2009 · 2025-09-05 13:51:25 · 题解

将三目运算符刻画成，每次选取一个长为 3 的子串变成 0/1；令函数 f(s,t) 返回 s 能否进行如上操作后变成 t。当 t 固定时，构建自动机 A_t，若字符串 s_1,s_2 满足对于任意 01 串 s 有 f(s_1+s,t)=f(s_2+s,t)，则显然可以把 s_1/s_2 压入 A_t 种同一节点。若变化规律比较简单，自动机状态是有限的，且仅取所有 |s|\le m 的字符串 s 就可以区分所有状态（m 是一个常数）。

令 g(s) 为一个长度为 2^n 的序列，其中第 i 项存储 f(s+a_i,t) 的值，a_i 是 i 对应的 01 串；如何构建自动机？直接 bfs，每遇到一个新字符串 s，若其 g(s) 未出现过，则丢入队列并作为 g(s) 状态的代表元。则构建自动机复杂度为 \mathcal{O}\left(|A_t|(l+m)^32^m\right)，其中 l 是 A_t 所有状态对应的代表元的最长长度。对于所有 |t|\le 2 的 t 建立自动机 A_t，实际上有 l\le9,m\le 6,|A|\le47，复杂度可以接受。

如何构造 s_{l\sim r} 合成 t 的方案？若 |t|=2 则枚举合成 t_1,t_2 区间的分段点，否则 |t|=1 若 t_1't_2't_3'\to t，枚举 t_1',t_2't_3' 区间分段点，类似于启发式分裂，从两边开始向中间找；问题变成快速 check 一个区间 s_{l\sim r} 是否可以合成 t，对每个 A_t 建线段树即可，维护每个 A_t 上状态走过一个线段树区间对应的转移变成了什么；或者是建猫树，做到查询 \mathcal{O}(1)，但预处理复杂度和空间复杂度多带上一个 \log{n}。

用线段树做的复杂度是 \mathcal{O}\left(|A_t|(l+m)^32^m+|A_t|\sum n+\sum n\log^2{n}\right)。

#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define umap unordered_map
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
int op[8];
struct DFA {
    static const int N=50,L=20,m=6;
    int trans[N][2],f[L][L][6],s[N],t,p;
    bool ok[N];
    map<bint,int> h;
    bint check(int s) {
        int n=lg(s);
        rep(i,0,n-1) {
            rep(j,0,n-1) {
                rep(k,0,5)
                    f[i][j][k]=false;
            }
            f[i][i][(s>>i)&1]=true;
        }
        rep(len,2,n) {
            rep(l,0,n-len) {
                int r=l+len-1;
                rep(k,l,r-1) {
                    rep(i,0,5) {
                        if(!f[l][k][i])
                            continue;
                        rep(j,0,5) {
                            if(!f[k+1][r][j])
                                continue;
                            if(i<=1&&j<=1)
                                f[l][r][(i|(j<<1))+2]=true;
                            else if(i<=1)
                                f[l][r][op[i|((j-2)<<1)]]=true;
                            else if(j<=1)
                                f[l][r][op[(i-2)|(j<<2)]]=true;
                            else {
                                f[l][r][(((i-2)&1)|(op[((i-2)>>1)|((j-2)<<1)]<<1))+2]=true;
                                f[l][r][(op[(i-2)|(((j-2)&1)<<2)]|((j-2)&2))+2]=true;
                            }
                        }
                    }
                }
            }
        }
        return f[0][n-1][t];
    }
    bint calc(int s) {
        int x=lg(s);
        bint res=0;
        int cnt=0;
        rep(j,0,m) {
            if(j) {
                s^=1<<(x+j-1);
                s^=1<<(x+j);
            }
            rep(i,0,(1<<j)-1)
                res|=check(s|(i<<x))<<(cnt++);
        }
        return res;
    }
    void build(int _t) {
        t=_t;
        queue<int> q;
        bint g=calc(1);
        h[g]=++p;
        ok[p]=g&1;
        s[p]=1;
        q.push(p);
        while(!q.empty()) {
            int u=q.front(); q.pop();
            int x=lg(s[u]);
            int u0=s[u]^(1<<x)^(1<<(x+1)),u1=s[u]^(1<<(x+1));
            bint gu0=calc(u0),gu1=calc(u1);
            if(!h.count(gu0)) {
                h[gu0]=++p;
                s[p]=u0;
                ok[p]=gu0&1;
                q.push(p);
            }
            if(!h.count(gu1)) {
                h[gu1]=++p;
                s[p]=u1;
                ok[p]=gu1&1;
                q.push(p);
            }
            trans[u][0]=h[gu0];
            trans[u][1]=h[gu1];
        }
    }
}; DFA f[6];
const int N=1e5+5;
char s[N];
struct SGT {
    static const int M=50;
    int m;
    struct node {
        int l,r,trans[M];
    }; node tree[N<<2];
    #define ls(k) (k<<1)
    #define rs(k) (k<<1|1)
    void push_up(int k) {
        rep(i,1,m)
            tree[k].trans[i]=tree[rs(k)].trans[tree[ls(k)].trans[i]];
    }
    void build(int k,int l,int r,DFA &f) {
        tree[k].l=l; tree[k].r=r;
        if(l==r) {
            rep(i,1,m)
                tree[k].trans[i]=f.trans[i][s[l]-48];
            return;
        }
        int mid=(l+r)>>1;
        build(ls(k),l,mid,f);
        build(rs(k),mid+1,r,f);
        push_up(k);
    }
    int query(int k,int ql,int qr,int u) {
        if(ql<=tree[k].l&&tree[k].r<=qr)
            return tree[k].trans[u];
        if(ql<=tree[ls(k)].r)
            u=query(ls(k),ql,qr,u);
        if(qr>=tree[rs(k)].l)
            u=query(rs(k),ql,qr,u);
        return u;
    }
    #undef ls
    #undef rs
}; SGT T[6];
bool check(int l,int r,int op) {
    return f[op].ok[T[op].query(1,l,r,1)];
}
void solve(int l,int r,int c) {
    // debug("([%d,%d],%d)\n",l,r,c);
    if(l==r) {
        printf("%c",s[l]);
        return;
    }
    if(c<=1) {
        putchar('(');
        int pl=l,pr=r;
        while(true) {
            bool flag=false;
            rep(i,0,1) {
                rep(j,0,3) {
                    if(op[i|(j<<1)]!=c)
                        continue;
                    if(pl!=r&&check(l,pl,i)&&check(pl+1,r,j+2)) {
                        solve(l,pl,i);
                        solve(pl+1,r,j+2);
                        flag=true;
                        break;
                    }
                    if(l!=pr&&check(l,pr-1,i)&&check(pr,r,j+2)) {
                        solve(l,pr-1,i);
                        solve(pr,r,j+2);
                        flag=true;
                        break;
                    }
                }
                if(flag)
                    break;
            }
            if(flag)
                break;
            ++pl; --pr;
        }
        putchar(')');
    } else {
        int pl=l,pr=r;
        while(true) {
            if(pl!=r&&check(l,pl,(c-2)&1)&&check(pl+1,r,(c-2)>>1)) {
                solve(l,pl,(c-2)&1);
                solve(pl+1,r,(c-2)>>1);
                break;
            }
            if(l!=pr&&check(l,pr-1,(c-2)&1)&&check(pr,r,(c-2)>>1)) {
                solve(l,pr-1,(c-2)&1);
                solve(pr,r,(c-2)>>1);
                break;
            }
            ++pl; --pr;
        }
    }
}
void solve() {
    rep(i,0,7) {
        char ch;
        cin>>ch;
        op[i]=ch-48;
    }
    rep(i,0,5)
        f[i].build(i);
    int q;
    scanf("%d",&q);
    while(q--) {
        scanf("%s",s+1);
        int n=strlen(s+1);
        rep(i,0,5)
            T[i].m=f[i].p,T[i].build(1,1,n,f[i]);
        if(!check(1,n,1)) {
            puts("-1");
            continue;
        }
        solve(1,n,1);
        puts("");
    }
}
bool M2;
// g++ P12294.cpp -std=c++14 -Wall -O2 -o P12294
signed main() {
    // file_IO();
    int testcase=1;
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
    return 0;
}