BZOJ 2085

Posted on Edited on Views:

本地笔记整理重发，原文写于2019/8/28，2019/12/8上传

分析

首先使用哈希计算字符串两两之间的overlap，这个的时间复杂度不是特别显然：

\sum_{i=1}^n\sum_{j=1}^n\min\{a_i,a_j\}
其中a_i, a_j分别是第i个和第j个字符串的长度。假设a_i从小到大排了序，那么就变为：
\sum_{i=1}^n \left[\sum_{j=1}^ia_j+(n-i)a_i\right]
这样每一个a_i都会被计算n-i+1+n-i=2n-2i+1次，则时间复杂度为：
\begin{aligned} \sum_{i=1}^n (2n-2i+1)a_i \end{aligned}
显然这个时候越前面的a_i越大越好，但是a_i是递增的，所以极限情况是各a_i相等取最大值，时间复杂度就是O\left(n\sum_{i=1}^na_i\right)。

然后Floyd 矩阵乘法即可。

双哈希大法好

卡常Nice

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;
const int MOD1 = 998244353, MOD2 = 1e9 + 7;
const int EPS = 26;
const int N = 210;
const int S = 100010;
typedef long long ll;
typedef pair<int, int> hsh;
int n, m;
vector<hsh> h[N];
hsh p[S];
inline hsh operator +(const hsh &a, const hsh &b) {
    hsh ret = make_pair(a.first + b.first, a.second + b.second);
    if (ret.first >= MOD1) ret.first -= MOD1;
    if (ret.second >= MOD2) ret.second -= MOD2;
    return ret;
}
inline hsh operator -(const hsh &a, const hsh &b) {
    hsh ret = make_pair(a.first - b.first, a.second - b.second);
    if (ret.first < 0) ret.first += MOD1;
    if (ret.second < 0) ret.second += MOD2;
    return ret;
}
inline hsh operator +(const hsh &a, char b) {
    int c = b - 'a';
    return make_pair(((ll)a.first * EPS + c) % MOD1, 
            ((ll)a.second * EPS + c) % MOD2);
}
inline hsh operator *(const hsh &a, const hsh &b) {
    return make_pair((ll)a.first * b.first % MOD1, 
            (ll)a.second * b.second % MOD2);
}
inline hsh cut(int i, int l, int r) {
    return h[i][r] - h[i][l] * p[r - l];    
}
inline int intersect(int a, int b) {
    int la = h[a].size() - 1, lb = h[b].size() - 1;
    int lim = a == b ? la - 1 : min(la, lb);
    int ret = 0;
    for (int i = 1; i <= lim; i++)
        if (cut(a, la - i, la) == cut(b, 0, i)) ret = i;
    return ret;
}
struct floyd {
    ll d[N][N];
    floyd() { memset(d, 0x3f, sizeof d); }
    ll *operator [](int x) { return d[x]; }
    const ll *operator [](int x) const { return d[x]; }
    floyd operator *(const floyd &b) const {
        floyd ret;
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) 
                    ret[i][j] = min(ret[i][j], d[i][k] + b[k][j]);
        return ret;
    }
} f;
int main() {
    scanf("%d%d", &n, &m);
    int maxlen = 0;
    for (int i = 1; i <= n; i++) {
        static char tmp[S]; scanf("%s", tmp + 1);
        int len = strlen(tmp + 1);
        maxlen = max(maxlen, len);
        h[i].push_back(make_pair(0, 0));
        for (int j = 1; j <= len; j++)
            h[i].push_back(h[i].back() + tmp[j]);
    }
    p[0] = make_pair(1, 1);
    for (int i = 1; i <= maxlen; i++) p[i] = p[i - 1] * make_pair(EPS, EPS);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) 
            f[i][j] = h[j].size() - 1 - intersect(i, j);
    floyd ans; for (int i = 1; i <= n; i++) ans[i][i] = h[i].size() - 1;
    int y = m - 1;
    for (; y; y >>= 1) {
        if (y & 1) ans = ans * f;
        f = f * f;
    }   
    ll mn = 1ll << 60;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) mn = min(mn, ans[i][j]);
    printf("%lld\n", mn);
    return 0;
}