P15650 题解

· · 题解

Problem Link

一个比较好写且常数比较小的做法。

首先考虑如何数 t 有多少子串字典序 <s。

考虑增量，从 t[1,i-1]\to t[1,i] 只要考虑所有的后缀，而这些后缀又继承了 t[1,i-1] 的后缀信息。

把 t[1,i-1] 的后缀分为三种：已经 <s 或 >s，以及当前是 s 前缀。

显然只要记录第一类的数量 y，以及 t[1,i-1] 在 s 的 kmp 自动机上匹配到的点 x。

如果总数为 z，则转移形如 (x,y,z)\to^c(\mathrm{trans}(x,c),y+w(x,c),z+y'+\mathrm{dep}_{x'})，其中 w 表示有多少个原先匹配的后缀在加入 t_i=c 后比出大小且 <s。

那么直接记录 x,y,z 和长度，状态数 nk^3。

考虑优化掉 y，注意到在当前时刻让 y 增加 t，那么对 z 的贡献就是后续每插入一个字符就让 z\gets z+t。

所以只要知道串长 |t|，那么这一步对 z 的贡献就是 \mathrm{dep}_{x'}+(|t|-i+1)\times w(x,c)。

直接把 dp 过程转置，从后往前插入 t 的每一个元素，此时就能直接知道 |t|-i+1 的值，从而省掉 y 一维。

对 x 的转移转置，依旧枚举 t[1,i-1] 时的 x，然后从 \mathrm{trans}(x,c) 的位置转移过来，用 bitset 优化 z 一维的修改。

时间复杂度 \mathcal O\left(\dfrac{nk^2}{\omega}\right)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,K,fa[205],e[205][2],w[205][2],d[205];
bitset <3005> f[3415][2][205],tf;
void solve() {
    string s;
    cin>>n>>K>>s,s=" "+s;
    for(int i=2,j=0;i<=n;++i) {
        for(;j&&s[j+1]!=s[i];j=fa[j]);
        fa[i]=j+=(s[j+1]==s[i]);
    }
    for(int i=1;i<=n;++i) d[i]=d[fa[i]]+(i<n);  
    for(int i=0;i<=n;++i) for(int c:{0,1}) {
        int j=i;
        for(;j&&(j==n||s[j+1]!=c+'0');j=fa[j]);
        e[i][c]=j+(s[j+1]==c+'0'),w[i][c]=0;
        for(int x=i;;x=fa[x]) {
            w[i][c]+=x<n&&s[x+1]>c+'0';
            if(!x) break;
        }
    }
    for(int x=0;x<=n;++x) {
        f[0][0][x].reset(),f[0][1][x].reset();
        f[0][x==n][x][K]=1;
    }
    for(int i=1;i<=K+n*2+5;++i) {
        bool op=0;
        for(int x=0;x<=n;++x) {
            f[i][0][x].reset(),f[i][1][x].reset();
            for(int o:{0,1}) for(int c:{0,1}) {
                int v=w[x][c]*i+d[e[x][c]];
                if(v>K) continue;
                tf=f[i-1][o][e[x][c]],tf>>=v,f[i][o||x==n][x]|=tf;
            }
            op|=f[i][0][x].any()||f[i][1][x].any();
        }
        if(f[i][1][0][0]) {
            string ans="";
            for(int j=i-1,x=0,y=0,o=0;~j;--j) {
                o|=x==n;
                for(int c:{0,1}) {
                    int v=w[x][c]*(j+1)+d[e[x][c]];
                    if(y+v>K) continue;
                    if(f[j][1][e[x][c]][y+v]||(o&&f[j][0][e[x][c]][y+v])) { x=e[x][c],y+=v,ans+=c+'0'; break; }
                }
            }
            return cout<<ans<<"\n",void();
        }
        if(!op) break;
    }
    cout<<"Impossible\n";
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int ty,_; cin>>ty>>_;
    while(_--) solve();
    return 0;
}