题解：P16003 [ICPC 2020 NAC] Editing Explosion

Euouae · 2026-11-04 22:01:22 · 题解

考虑 DP 套 DP。

首先是自动机的设计，容易发现内层 DP 就是 P2758 。

但是记录每一位的值状态爆炸，考虑结合板子的 LCS 的类似性质，发现对于编辑距离，一个确定的状态 g ，再多加一个字符 c ，转移为：

容易发现相邻两位的值的差值 ：

考虑压缩成差分，不一样的是，这题是三进制的。

有了自动机，剩下的就是常规计数。

先预处理转移，然后滚动数组计数即可。

:::info[参考代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Mod=998244353;
const int N=60005;

int trans[N][26],l;
int t[N],a[N];
string s;
ll ans;

int gnxt(int sta,int c){
    int g[20],h[20];
    g[0]=0;
    for(int i=1;i<=l;i++){
        g[i]=g[i-1]+sta%3-1;
        sta/=3;
    }
    h[0]=1;
    for(int i=1;i<=l;i++){
        h[i]=min({g[i]+1,h[i-1]+1,g[i-1]+(c!=a[i])});
        // 删除，插入 
    }

    int res=0;
    for(int i=l;i>=1;i--)
        res=res*3+(h[i]-h[i-1]+1);
    return res;
}

int f[2][N],d;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>s;
    cin>>d;
    l=s.size();
    for(int i=1;i<=l;i++)
        a[i]=s[i-1]-'A';

    int full=1;
    for(int i=1;i<=l;i++)
        full=full*3;

    for(int sta=0;sta<full;sta++){

        int x=sta;
        int sum=0;
        for(int i=1;i<=l;i++){
            sum=sum+(x%3)-1;
            x/=3;
        }
        t[sta]=sum;

        for(int c=0;c<26;c++)
            trans[sta][c]=gnxt(sta,c);
    }

    int cur=0,nxt=1;
    int st=full-1;
    f[cur][st]=1;

    for(int k=0;k<=l+d;k++){
        for(int sta=0;sta<full;sta++){
            if(!f[cur][sta]) continue;
            if(k+t[sta]==d) ans=(ans+f[cur][sta])%Mod;
        }
        if(k==l+d) continue;

        memset(f[nxt],0,sizeof(f[nxt]));

        for(int sta=0;sta<full;sta++){
            if(!f[cur][sta]) continue;
            for(int c=0;c<26;c++){
                int v=trans[sta][c];
                f[nxt][v]=(f[nxt][v]+f[cur][sta])%Mod;
            }
        }
        swap(cur,nxt);
    }

    cout<<ans<<'\n';

    return 0;
}

:::