Codeforces

Luogu

分析

首先可以证明图的直径长度不超过 $15$。

先预处理 $f_{i,j}$ 表示 $i$ 走到一个颜色为 $j$ 的点的最短路、$g_{i,j}$ 表示某个颜色为 $i$ 的点走到某个颜色为 $j$ 的点的最短路。这可以通过以每种颜色为起点 BFS 一遍求出。

接着我们枚举 $i$，并试着找到 $j\in[1,i)$ 使得 $dis(i,j)$ 最小。实际上有 $dis(i,j)=\min\left\{i-j,f_{i,c}+f_{j,c}+1\right\}$。

对于 $i$ 前面的 $15$ 个点，我们可以暴力枚举计算答案。

当 $i-j>15$ 时一定有 $dis(i,j)=\min\left\{f_{i,c}+f_{j,c}+1\right\}$，注意到 $f_{i,c}$ 一定为 $g_{s_i,c}$ 和 $g_{s_i,c}+1$ 中的某个值，所以我们可以状压成一个八位二进制数。那么对于颜色和状态都相同的点，它们到 $i$ 的距离也一定相等，可以批量处理。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

char s[N];
int n,c[N],vis[N],visc[8],f[N][8],g[8][8],o[8][256];
vector<int> vec[8];
queue<int> Q;

int main() {
    n=read(); scanf("%s",s+1);
    for (int i=1;i<=n;++i) c[i]=s[i]-'a',vec[c[i]].emplace_back(i);
    memset(f,0x3f,sizeof(f)),memset(g,0x3f,sizeof(g));
    for (int i=0;i<8;++i) {
        memset(vis,0,sizeof(vis)),memset(visc,0,sizeof(visc));
        for (int j:vec[i]) f[j][i]=0,vis[j]=1,Q.push(j);
        g[i][i]=0,visc[i]=1;
        while (!Q.empty()) {
            int u=Q.front(); Q.pop();
            if (u>1&&!vis[u-1]) f[u-1][i]=f[u][i]+1,vis[u-1]=1,Q.push(u-1);
            if (u<n&&!vis[u+1]) f[u+1][i]=f[u][i]+1,vis[u+1]=1,Q.push(u+1);
            if (!visc[c[u]]) {
                visc[c[u]]=1,g[c[u]][i]=f[u][i];
                for (int v:vec[c[u]])
                    if (!vis[v]) f[v][i]=f[u][i]+1,vis[v]=1,Q.push(v);
            }
        }
    }
    int ans=0; ll cnt=0;
    auto update=[&](int w,int c) {
        if (w>ans) ans=w,cnt=c;
        else if (w==ans) cnt+=c;
    };
    for (int i=1;i<=n;++i)
        for (int j=max(1,i-15);j<i;++j) {
            int w=i-j;
            for (int k=0;k<8;++k) w=min(w,f[i][k]+f[j][k]+1);
            update(w,1);
        }
    for (int i=17;i<=n;++i) {
        int S=0;
        for (int j=0;j<8;++j)
            S|=(f[i-16][j]-g[c[i-16]][j])<<j;
        ++o[c[i-16]][S];
        for (int j=0;j<8;++j)
            for (int k=0;k<256;++k) {
                if (!o[j][k]) continue;
                int w=2e9;
                for (int l=0;l<8;++l) w=min(w,f[i][l]+g[j][l]+(k>>l&1)+1);
                update(w,o[j][k]);
            }
    }
    printf("%d %lld\n",ans,cnt);
    return 0;
}