题解：P15650 [省选联考 2026] 摩卡串 / string

· · 题解

简单赛时做法。

令 s[l,r] 表示 s_ls_{l+1}\dots s_r 拼接而成的字符串。

考虑如何判定一个串 t 合不合法，考虑从左向右扫描线，扫描到 i 时考虑所有右端点为 i 的子串，维护两个集合 X,Y，X 中维护所有 t[l,i] 为 s 的一个前缀的 l，Y 中维护所有 t[l,i] 严格小于 s[1,i-l+1] 的 l，t[1,i] 中严格小于 s 的子串个数，以及有没有出现过 s 子串。每次插入新字符的时候简单维护即可。

我们注意到 X 实际上只与 t 目前在 s 的 kmp 自动机上匹配到的节点相关，因此本质不同的 X 只有 O(n) 种。

而对于 Y 我们实际上只关心他的大小，显然不超过 k。

然后每次在最后插入一个字符的时候我们会将 X 中一部分移动到 Y 中，移动的这部分显然只和当前在 kmp 自动机上匹配到的节点以及后面插入的字符相关。

因此我们只需要记录当前匹配到的 kmp 自动机上的节点 x，集合 Y 的大小 y，以及当前严格小于 s 的子串个数 z，以及有没有出现过 s 子串 w 这四个状态即可。

这样就得到了一个一共有 O(nk^2) 个状态，每个状态有 2 个转移，共计 O(nk^2) 个转移的可以用来判断一个串是否合法的自动机。

然后我们就得到了一个简单的 O(nk^2) 做法。建出这个自动机，在上面跑最短路，记录最短路的转移就可以反向还原出方案。

但是这个做法看起来非常卡不满，我们来分析一下它的复杂度。

我们发现，如果 t 的字典序严格小于 s，那么 t 的任何一个前缀一定也严格小于 s，所以 z\geq \frac{y(y+1)}{2}，y 实际上不超过 O(\sqrt k)，因此，该做法的复杂度实际上是 O(nk^{1.5})，可以通过。

#include<bits/stdc++.h>
using namespace std;
int n,m;
queue<int> q;
struct node{
    int x,y,z;bool w;
    int fa;
};
vector<node> Q;
bitset<3001> vis[2][201][82];
char s[209];
int f[209],g[209];
int fa[209],ch[209][2];
void dfs(int id){
    if(!id)return;
    dfs(Q[id].fa);
    node tmp=Q[Q[id].fa];
    int x=tmp.x,y=tmp.y,z=tmp.z;bool w=tmp.w;
    node t=Q[id];
    int xx=ch[x][0],yy=y+g[x],zz=z+(f[xx]-(xx==n))+yy;
    bool ww=w||(xx==n);
    if(xx==t.x&&yy==t.y&&zz==t.z&&ww==t.w){
        cout<<0;
    }
    else cout<<1;
}
void solve(){
    cin>>n>>m>>(s+1);
    int M=0;while(M*(M+1)/2<=m)++M;
    for(int i=0;i<=n;i++)fa[i]=f[i]=g[i]=ch[i][0]=ch[i][1]=0;
    for(int i=1;i<=n;i++)ch[i-1][s[i]-'0']=i;
    for(int i=0;i<2;i++)if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<2;i++){
            if(ch[u][i]){
                fa[ch[u][i]]=ch[fa[u]][i];
                q.push(ch[u][i]);
            }
            else{
                ch[u][i]=ch[fa[u]][i];
            }
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=1;j<=i;j++){
            int len=i-j+1;bool flag=1;
            for(int t=1;t<=len&&flag;t++){
                if(s[j+t-1]!=s[t])flag=0;
            }
            if(flag)f[i]++;
            if(s[len+1]>'0'&&flag)g[i]++;
        }
        g[i]+=(s[1]=='1');
    }
    Q.clear();
    for(int i=0;i<=n;i++){
        for(int j=0;j<=M;j++)vis[0][i][j].reset(),vis[1][i][j].reset();
    }
    Q.push_back(node{0,0,0,0,0});int head=0;
    vis[0][0][0][0]=1;
    while(head<Q.size()){
        node tmp=Q[head];++head;
        int x=tmp.x,y=tmp.y,z=tmp.z;
        bool w=tmp.w;
        {
            int xx=ch[x][0],yy=y+g[x],zz=z+(f[xx]-(xx==n))+yy;
            bool ww=w||(xx==n);
            if(zz==m&&ww==1){
                dfs(head-1);cout<<0<<"\n";return;
            }
            if(yy+zz<=m){
                if(!vis[ww][xx][yy][zz]){
                    vis[ww][xx][yy][zz]=1;
                    Q.push_back(node{xx,yy,zz,ww,head-1});
                }
            }
        }
        {
            int xx=ch[x][1],yy=y,zz=z+(f[xx]-(xx==n))+yy;
            bool ww=w||(xx==n);
            if(zz==m&&ww==1){
                dfs(head-1);cout<<1<<"\n";return;
            }
            if(yy+zz<=m){
                if(!vis[ww][xx][yy][zz]){
                    vis[ww][xx][yy][zz]=1;
                    Q.push_back(node{xx,yy,zz,ww,head-1});
                }
            }
        }
    }
    cout<<"Impossible\n";
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int C,T;cin>>C>>T;while(T--)solve();return 0;
}