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

· · 题解

没去省选，在家自测，做了3h牢，居然拿了90，卡了卡常，居然过了。预先声明：不知道是不是正解，复杂度也不知道，\Theta(能过)。出了官方数据再测一测。第二次写黑体题解祭。

首先，观察样例我们可以发现，字典序小于 s 的分为两类，一类是它的真前缀，一类是从某一位开始比它小，对于第二类，会永远比它小，对于第一类，只需要用一个 KMP 来记录当前匹配到哪了就行了，然而我当时忘了 KMP 怎么写，于是使用 AC 自动机进行平替，然后 BFS，只需要记录以下几个值就可以了：一，当前匹配到哪了，即在字典图上哪个节点，用于统计第一类；二，第二类有多少个；三，总共有多少个比 s 小的；四：是否已经包含 s。

然后再预处理 AC 自动机或 KMP 时顺便预处理如果这一位填零或一，会有多少个后缀会因为这一位而成为第二类，和有多少个后缀是 s 的真前缀，就可以转移第二个值了，很明显第三个值的增加量就等于第二个值和真前缀的数量，最简单的就是处理第四个，只需要看看走到头没有就行了。

这样就能过了吗？当然不行，只有九十分，我们需要继续剪枝，对于字典图上的每个点记录匹配到哪里了，然后对于还没有包含 s 的字符串算出增加量最少的情况，包含 s 的时候第三个值是多少，如果大于 k，就提前结束。当然，可以再预处理时预处理准确值而非 BFS 时使用估算值，但我懒得改了。

最后，输出方案，只需要用一个哈希表，记录每个状态和他的上一个状态以及填的什么，就可以还原出来了。

代码。

#include<bits/stdc++.h>
#include <bits/extc++.h>
#define ull unsigned long long
using namespace std;
using namespace __gnu_pbds;
int n,m,T,k;
char s[200005];
namespace AC{
    struct node{
        int son[2],an,fail,du,idx,g,sm[2],pr;
        void init(){
            memset(son,0,sizeof(son));
            an=fail=idx=0;pr=0;
            sm[0]=sm[1]=0;
        }
    }tr[205];
    int tot,an[205],pid;
    void init(){
        tot=pid=0;
        tr[0].init();
        memset(an,0,sizeof(an));
    }
    void insert(char s[],int &idx){
        int u=0;tr[u].an=0;
        for(int i=1;s[i];i++){
            int &son=tr[u].son[s[i]-'0'];
            tr[u].g=s[i]-'0';
            if(!son){
                son=++tot;
                tr[son].init();
            }
            u=son;
            tr[u].an=i;
        }
        if(!tr[u].idx)tr[u].idx=++pid;
        idx=tr[u].idx;
    }
    queue<int>q;
    void build(){
        while(!q.empty())q.pop();
        for(int i=0;i<2;i++)if(tr[0].son[i])q.push(tr[0].son[i]);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=0;i<2;i++){
                if(tr[u].son[i]){
                    tr[tr[u].son[i]].fail=tr[tr[u].fail].son[i];
                    tr[tr[tr[u].fail].son[i]].du++;
                    q.push(tr[u].son[i]);
                }else tr[u].son[i]=tr[tr[u].fail].son[i];
            }
        }
        for(int i=0;i<=tot;i++){
            for(int x=0;x<2;x++){
                for(int p=i;;p=tr[p].fail){
                    if(tr[p].an<n&&x<(s[tr[p].an+1]-'0'))tr[i].sm[x]++;
                    if(!p)break;
                }
            }
            for(int p=i;p;p=tr[p].fail)if(tr[p].an<n)tr[i].pr++;
        }
    }
    void query(char t[]){
        int u=0;
        for(int i=1;t[i];i++){
            u=tr[u].son[t[i]-'a'];
            tr[u].an++;
        }
    }
}
struct node{
    int s,k,u,h;
    ull hsh()const{
        return ((ull)h<<42)|((ull)u<<32)|((ull)s<<16)|(ull)k;
    }
}h,t;
int idx[205];
queue<node>q;
struct chash {
    size_t operator()(ull x) const {
        x ^= x >> 33;
        x *= 0xff51afd7ed558ccdLL;
        x ^= x >> 33;
        x *= 0xc4ceb9fe1a85ec53LL;
        x ^= x >> 33;
        return x;
    }
};
ull tt;
gp_hash_table<ull,pair<ull,char>,chash>mp;
void print(ull h){
    if(h==tt)return;
    print(mp[h].first);
    printf("%c",mp[h].second);
}
void solve(){
    mp.clear();
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    AC::init();
    AC::insert(s,idx[1]);
    AC::build();
    while(!q.empty())q.pop();
    q.push((node){0,0,0,0});
    h={0,0,0,0};
    mp[tt=h.hsh()]=make_pair(h.hsh(),'\0');
    while(!q.empty()){
        h=q.front();
        q.pop();
        for(int x=0;x<2;x++){
            t=h;
            t.u=AC::tr[h.u].son[x];
            t.s+=AC::tr[h.u].sm[x];
            t.k+=t.s+AC::tr[t.u].pr;
            if(AC::tr[t.u].an==n)t.h=1;
            if(!t.h&&1ll*(n-AC::tr[t.u].an)*t.s+t.k>k)continue;
            if(mp.find(t.hsh())!=mp.end()||t.k>k||t.s>k)continue;
            mp[t.hsh()]=make_pair(h.hsh(),x+'0');
            if(t.h&&t.k==k){
                print(t.hsh());
                puts("");
                return;
            }
            q.push(t);
        }
    }
    puts("Impossible");
}
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    scanf("%d%d",&T,&T);
    while(T--)solve();
    return 0;
}