P12294

· · 题解

如果你做过 AT_agc022_e 或 gym102586J，可以知道这种将 01 串中连续三个替换为一个字符的问题可以造一个自动机判定。

考虑直接根据等价关系建自动机，根据 Myhill-Nerode 定理，x\equiv_L y 当且仅当对于任意字符串 z，xz\in L 当且仅当 yz\in L。因为规则简单，自动机的结构应该也很简单，经试验，仅考察 |x|\leq 9 的 x 的等价关系就可区分出所有串。同理，对于 z，长度较长的 z 也只会在自动机上绕圈，经试验，只用考察 |z|\leq 6 的 z。实现时根据接受 xz 的情况划分 x 的等价类，每个等价类取长度最小的串为代表元，考察代表元的转移建出 DFA。

考虑怎么输出方案，假设 solve(l,r,type) 表示区间 [l,r] 要合出串 type，我们需要对 [l,r] 找到最后一次合并时每个字符由哪个区间合出来，然后递归地合并。每次我们分离一个 \texttt 0 或 \texttt 1 并递归到两半。找这个分界点可以启发式分裂，同时从两边开始找，此部分的枚举量 O(n\log n)。type 可以是 \texttt 0,\texttt 1,\texttt{00},\texttt{10},\texttt{01},\texttt{11}，我们需要查一段区间是否能合成这六个之一，因此需要造六个自动机。自动机最大点数为 47。

判定子区间能否合成，可以用倍增维护自动机每个节点从 i 跳 2^j 步会到哪，单次 O(\log n)。可能会有空间问题，可以套个底层分块缓解。复杂度 O(n|Q|\log n+n\log^2n)(|Q|=47)。

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int t,n,g[65536],p[1029],type[1029],id[105];
char a[100005];
string opt;
vector<bool>l[1029];
bool cmp(int a,int b){
  return l[a]==l[b]?a<b:l[a]<l[b];
}
bool dfs(int s,string opt,int t){
  if((__lg(s)&1)!=(__lg(t)&1))return g[s]=0;
  if(g[s]!=-1)return g[s];
  for(int i=0;i<__lg(s)-2;i++)if(dfs(s>>(i+3)<<(i+1)|(opt[s>>i&7]-'0')<<i|(s&((1<<i)-1)),opt,t))return g[s]=1;
  return g[s]=0;
}
struct DFA{
  int tr[50][2],cnt,s,f[15][3130][50];
  bool b[50];
  void build(string opt,int t){
    int num=0;
    cnt=0,memset(g,-1,sizeof(g)),g[2]=g[3]=g[4]=g[5]=g[6]=g[7]=0,g[t]=1;
    for(int lenx=0;lenx<=9;lenx++){
      for(int x=1<<lenx;x<2<<lenx;x++){
        l[x].clear(),p[++num]=x;
        for(int leny=0;leny<=6;leny++)for(int y=1<<leny;y<2<<leny;y++)l[x].push_back(dfs(y<<__lg(x)|(x&~(1<<__lg(x))),opt,t));
      }
    }
    sort(p+1,p+num+1,cmp);
    for(int i=1;i<=num;i++){
      if(l[p[i]]!=l[p[i-1]])id[++cnt]=p[i];
      type[p[i]]=cnt;
    }
    s=type[1];
    for(int i=1;i<=cnt;i++)tr[i][0]=type[3<<__lg(id[i])^id[i]],tr[i][1]=type[3<<__lg(id[i])|id[i]];
    for(int i=1;i<=cnt;i++)b[i]=dfs(id[i],opt,t);
  }
  void init(int n,char a[]){
    for(int i=1;i<n>>5;i++){
      for(int j=1;j<=cnt;j++)f[0][i][j]=j;
      for(int j=i<<5;j<(i+1)<<5;j++)for(int k=1;k<=cnt;k++)f[0][i][k]=tr[f[0][i][k]][a[j]-'0'];
    }
    for(int i=1;i<=__lg(n)-5;i++)for(int j=1;j+(1<<i)<=n>>5;j++)for(int k=1;k<=cnt;k++)f[i][j][k]=f[i-1][j+(1<<(i-1))][f[i-1][j][k]];
  }
  bool check(int l,int r){
    int pos=s;
    while(l<=r&&l&31)pos=tr[pos][a[l++]-'0'];
    for(int i=__lg(n)-5;i>=0;i--)if(l+(1<<(i+5))<=r)pos=f[i][l>>5][pos],l+=1<<(i+5);
    while(l<=r)pos=tr[pos][a[l++]-'0'];
    return b[pos];
  }
}d[6];
void solve(int l,int r,int type){
  if(l==r){
    putchar(a[l]);
    return;
  }
  if(type<=1){
    for(int i=l,j=r;i<=j;i+=2,j-=2){
      for(int k=0;k<8;k++){
        if(opt[k]==type+'0'&&d[k&1].check(l,i)&&d[(k>>1)+2].check(i+1,r)){
          putchar('('),solve(l,i,k&1),solve(i+1,r,(k>>1)+2),putchar(')');
          return;
        }
        if(opt[k]==type+'0'&&d[(k&3)+2].check(l,j-1)&&d[k>>2].check(j,r)){
          putchar('('),solve(l,j-1,(k&3)+2),solve(j,r,k>>2),putchar(')');
          return;
        }
      }
    }
  }
  else{
    for(int i=l,j=r;i<=j;i+=2,j-=2){
      if(d[(type-2)&1].check(l,i)&&d[(type-2)>>1].check(i+1,r)){
        solve(l,i,(type-2)&1),solve(i+1,r,(type-2)>>1);
        return;
      }
      if(d[(type-2)&1].check(l,j-1)&&d[(type-2)>>1].check(j,r)){
        solve(l,j-1,(type-2)&1),solve(j,r,(type-2)>>1);
        return;
      }
    }
  }
}
int main(){
  cin>>opt>>t;
  for(int i=0;i<6;i++)d[i].build(opt,i+2);
  while(t--){
    cin>>a+1,n=strlen(a+1);
    for(int i=0;i<6;i++)d[i].init(n,a);
    if(!d[1].check(1,n))puts("-1");  
    else solve(1,n,1),putchar('\n');
  }
  return 0;
}