题解：CF461E Appleman and a Game

· · 题解

考虑 s 已知时我们如何操作最优，答案十分显然：假设当前已经匹配了 i-1 个字符，则我们找出最大的 j 满足 s_{i,j} 是 t 的子串操作即可。这种操作方法对后面的影响最小，所以一定最优。

由此，我们可以将 s 划分成若干段，每段都是 t 的一个子串，且第 i+1 段的开头不能被拼接在第 i 段后。此刻，每一段的关键信息仅有开头字符与结尾能够拼接上哪些字符集合。我们可以记录一个状态 f_{i,j,S} 表示目前已有 i 段，开头字符为 j，下一段的开头字符可以是集合 S 里面字符时，s 的最小长度。考虑转移，首先我们需要求出满足 j,S 两个限制的最短的 t 的子串，发现其长度不超过 \log_4 |s|，可以暴力枚举 j,S,len 算出。

随后，根据此状态 DP 可以做到 O(2^{12}n)。

发现 n 非常大，且转移为线性转移，可以直接矩阵优化转移。判定答案过程中可以用二分转倍增的优化，最终复杂度即可做到 O(2^{18} \log n)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline long long read(){
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
long long m;
int n;
char s[N];
unsigned long long ksm[N],base=13131,hsh[N];
struct matrix{
    __int128 f[75][75];
    inline matrix operator*(matrix b){
        matrix c;
        for(int i = 0;i<64;i++){
            for(int j = 0;j<64;j++){
                c.f[i][j]=1e30;
                for(int k = 0;k<64;k++)c.f[i][j]=min(c.f[i][j],f[i][k]+b.f[k][j]);
            }
        }
        return c;
    }
}ans,f[61];
vector<int>v[5];
inline int id(int x,int y){
    return x*16+y;
}
map<unsigned long long,int>mp;
int main(){
    m=read();scanf("%s",s+1),n=strlen(s+1);
    ksm[0]=1;
    for(int i = 1;i<=n;i++){
        ksm[i]=ksm[i-1]*base;hsh[i]=hsh[i-1]*base+s[i]-'A';
        v[s[i]-'A'].push_back(i);
    }
    for(int i = 0;i<16;i++){
        for(int j = 0;j<4;j++){
            int len = 1,now=1;
            while(1){
                mp.clear();
                for(int k = 0;k<4;k++){
                    if(!(i&(1<<k)))continue;
                    for(auto pos : v[k])if(pos>len && s[pos-len]==j+'A')mp[hsh[pos-1] - hsh[pos-len-1]*ksm[len]]++;
                }
                if(mp.size()<now)break;
                len++,now*=4;
            }
            for(int k = 0;k<4;k++){
                if(i&(1<<k)){
                    for(int o = 0;o<16;o++)f[0].f[id(j,i)][id(k,o)]=len;
                }
                else{
                    for(int o = 0;o<16;o++)f[0].f[id(j,i)][id(k,o)]=1e18;
                }
            }
        }
    }
    for(int i = 1;i<=60;i++){
        f[i]=f[i-1]*f[i-1];
    }
    long long res=1;
    for(int i = 60;i>=0;i--){
        auto now = ans*f[i];
        __int128 minn=1e30;
        for(int j = 0;j<64;j++)minn=min(minn,now.f[1][j]);
        if(minn>=m)goto fail;
        res+=(1ll<<i);ans=now;
        fail:;
    }
    cout<<res;
    return 0;
}