题目分析

这是一个字符串与矩阵快速幂结合的题目。我们需要构造一个字符串，使得给定的n个字符串在其中出现至少m次，求最短长度。

关键点

1. 字符串出现：A在B中出现意味着A是B的子串
2. 互不包含：给定的字符串之间互不包含
3. 最短长度：需要找到满足条件的最短字符串

核心思路

1. 问题转化：将问题转化为在字符串之间建立转移关系，然后用矩阵快速幂加速计算
2. KMP预处理：计算字符串之间的重叠部分，减少重复计数
3. 矩阵快速幂：将转移关系表示为矩阵，用快速幂计算m-1次转移后的最短长度

算法步骤

1. KMP预处理：

   • 对每个字符串计算next数组
   • 用于快速计算两个字符串之间的最大重叠长度

2. 计算转移代价：

   • d[i][j]表示在字符串i后面接字符串j时，需要额外添加的字符数
   • 等于len(j) - (i和j的最大重叠长度)

3. 矩阵快速幂：

   • 初始状态：直接使用每个字符串的长度
   • 转移矩阵：B[i][j] = d[i+1][j+1]
   • 计算A * (B^(m-1))得到最终结果

复杂度分析

• KMP预处理：O(总串长)
• 计算转移矩阵：O(n² * 平均串长)
• 矩阵快速幂：O(n³ * log m)
• 总复杂度：O(n³ * log m)，对于n ≤ 200, m ≤ 1e9可接受

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 205;
const ll inf = 1e18;

int n[N], m, k;
ll as = inf;
string a[N];
vector<int> nxt[N];

// KMP预处理next数组
void KMP(int x) {
    nxt[x].resize(n[x] + 1, 0);
    
    for (int i = 2, j = 0; i <= n[x]; ++i) {
        while (j && a[x][i] != a[x][j + 1])
            j = nxt[x][j];
            
        if (a[x][i] == a[x][j + 1])
            ++j;
            
        nxt[x][i] = j;
    }
}

// 计算字符串x和y的最大重叠长度
int mt(int x, int y) {
    for (int i = 1, j = 0; i <= n[x]; ++i) {
        while (j && a[x][i] != a[y][j + 1])
            j = nxt[y][j];
            
        if (a[x][i] == a[y][j + 1])
            ++j;
            
        if (i == n[x])  // 匹配到x的末尾
            return j;
            
        if (j == n[y])  // 完全匹配y
            j = nxt[y][j];
    }
    return -1;
}

int d[N][N];

// 矩阵类，用于快速幂
struct mat {
    ll a[N][N];
    mat() {
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                a[i][j] = inf;
    }
    mat operator * (const mat &t) const {
        mat as;
        for (int k = 0; k < m; ++k) {
            for (int i = 0; i < m; ++i) {
                ll tt(a[i][k]);
                for (int j = 0; j < m; ++j)
                    as.a[i][j] = min(as.a[i][j], tt + t.a[k][j]);
            }
        }
        return as;
    }
    mat operator ^ (int b) {
        mat as, base;
        for (int i = 0; i < m; ++i)
            as.a[i][i] = 0;  // 单位矩阵
            
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                base.a[i][j] = a[i][j];
                
        while (b) {
            if (b & 1)
                as = as * base;
            base = base * base, b >>= 1;
        }
        return as;
    }
};

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> m >> k;
    
    // 读入字符串并预处理
    for (int i = 1; i <= m; ++i) {
        cin >> a[i], n[i] = a[i].size(), a[i] = " " + a[i];
        KMP(i);
    }
    
    // 计算转移代价矩阵
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= m; ++j)
            d[i][j] = n[j] - (i == j ? nxt[i][n[i]] : mt(i, j));
    
    // 构建矩阵并快速幂
    mat A, B;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < m; ++j)
            B.a[i][j] = d[i + 1][j + 1];
            
    for (int i = 0; i < m; ++i)
        A.a[0][i] = n[i + 1];  // 初始状态：直接使用每个字符串
        
    A = A * (B ^ (k - 1));  // 转移k-1次
    
    // 找最小值
    for (int i = 0; i < m; ++i)
        as = min(as, A.a[0][i]);
        
    cout << as;
    return 0;
}

总结

本题的关键在于：

1. 问题建模：将字符串构造问题转化为图上的最短路径问题
2. KMP应用：高效计算字符串间的重叠部分
3. 矩阵快速幂：处理大规模的状态转移

这个解法巧妙地利用了：

• KMP算法快速计算字符串重叠
• 矩阵表示状态转移关系
• 快速幂处理指数级的状态转移次数

通过将字符串拼接问题转化为图论问题，再利用矩阵快速幂加速计算，成功解决了大规模m值的问题。