这里是人肉爬虫114514号awa,这是我爬出的第2个题目,以下是由生物计算机(已迭代20次)生成的内容:

知识点:

• KMP算法: 高效的字符串匹配算法,要解决的是这样一个经典问题：在一个主文本字符串 text 中，查找一个模式字符串 pattern 是否出现，以及出现的位置。
• KMP 算法的核心在于：利用next数组，来决定模式串在匹配失败后应该向后滑动多少位，而不是仅仅一位。
• 当在模式串的第 j 个位置匹配失败时，说明模式串的前 j-1 个字符(P0到Pj-2)已经和文本串对应位置的字符匹配成功了。那么，我们可以找到已匹配成功的那段子串(P0到Pj-2)中，最长公共前后缀。
• 前缀：指除了最后一个字符以外，一个字符串的全部头部组合。
• 后缀：指除了第一个字符以外，一个字符串的全部尾部组合。
• 最长公共前后缀（LPS）：一个字符串中，最长的那个既是前缀又是后缀的子串的长度。
• eg:子串 "ABAB"：前缀 ["A","AB","ABA"]，后缀 ["B","AB","BAB"]，公共是 "AB"，长度为 2。 然后得出next[4]=2,即当第5位(从0开始,j=4)与text[i]不匹配时,i不变,j从2开始（匹配时i++,j++）。
• 如果从0开始，则设next[0]=-1/0;从1开始设next[1]=-1/0;当next[j]=-1/0时,i++,j=0;其它情况则如例子一样,i不变j变

主要思想

• 1.通过KMP算出所有字符串后接所有字符串所产生的代价；
• 2.定义矩阵A(0,n)为以字符串Sn+1结尾的最小长度,其初始化长度为字符串Sn+1的长度; 再定义B(m,n)为字符串m+1后添加字符串n+1所产生的代价，其初始值为第一步算出的值。
• 3(最难).定义矩阵乘法*运算和矩阵幂^运算，具体情况看代码中的注释。

免责声明

• 我只是个在三友行刷了400题左右的小卡拉米，这道题对于我来说真超标了。
• 我之前刷到过动态规划的题，但我真的很难理解它(前缀和和差分我都理解了)，所以我对于此类题的态度是放弃。但现在完成动态规划的题是我的任务，我只能硬着头皮去理解了。
• 总而言之，算了，去看题解吧。

题解(复制到编译器里看)

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

int n[N], m, k;  // n[i]: 第i个字符串的长度; m: 字符串数量; k: 需要出现的最小次数
ll as = inf;     // 存储最终答案
string a[N];     // 存储所有字符串
vector<int> nxt[N];  // KMP算法的next数组
int d[N][N];  // d[i][j]: 在字符串i后面接上字符串j时，需要额外添加的字符数

// KMP预处理函数，为第x个字符串计算其next数组nxt[x][i] 
void KMP(int x) 
{
    nxt[x].resize(n[x] + 1, 0);  // 初始化next数组

    // 标准的KMP算法next数组计算过程
    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;  // 匹配成功，j前进

        nxt[x][i] = j;  // 记录next值
    }
}



// 计算两个字符串之间的重叠关系
int mt(int x, int y)
{
    // 使用KMP算法计算字符串x的后缀与字符串y的前缀的最大匹配长度（要在x后面接上y） 
    
    //KMP放在for循环中可读性确实差 
    
    for (int i = 1, j = 0; i <= n[x]; ++i) 
	{
        while (j && a[x][i] != a[y][j + 1])//j=0时,i++;j!=0且不相等时，i不变j变 
            j = nxt[y][j];  // 失配时回退

        if (a[x][i] == a[y][j + 1])
            ++j;  // 匹配成功，j前进

        // 如果已经匹配到字符串x的末尾，返回当前匹配长度
        if (i == n[x])
            return j;
            
        // 如果完全匹配了字符串y，回退到next位置继续匹配(因为不是求y在不在x，而是求y的前缀与x的后缀的重叠长度)
        if (j == n[y])
            j = nxt[y][j];
    }

    return -1;  // 理论上不会执行到这里
}

// 矩阵类，用于快速幂优化动态规划,这是这道题最难的地方 
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;
    }
    
    // 定义了一个特殊的矩阵乘法(最难)
// A = [……](字符串为?个,表示分别以s1,s2,s3……结尾的长度最小值) 

//如何得到以s1为结尾的长度最小值呢?你只需要在每个字符串后面都试着加上s1就行了。但出现次数的最大值来到了恐怖的10^9次方，这对想法的实现要求非常高。 
//设A1=[s1.len,s2.len,s3.l3n……] 

//假如有两个字符串，那么可以通过A1计算 s1.len+(s1到s1的代价),s2.len+(s2到s1的代价)……取其最小得到A2[SS1.len,……] 

//假如有三个字符串，那么可以通过A2计算SS1.len+(s1到s1的代价),SS2.len+(s2到s1的代价)……取其最小得到A3 
//…… 

	//假设有3个字符串：
	//s1: "ab" (长度2)
	//s2: "bc" (长度2)
	//s3: "cd" (长度2)
//得出	A = [2, 2, 2](字符串为一个,表示分别以s1,s2,s3结尾的长度最小值)


//B = [2, 1, 2]  // 第0行: s1→s1, s1→s2, s1→s3
//    [2, 2, 1]  // 第1行: s2→s1, s2→s2, s2→s3  
//    [2, 2, 2]  // 第2行: s3→s1, s3→s2, s3→s3

//      A*B = [4, 3, 3](字符串为两个,表示分别以s1,s2,s3结尾的长度最小值)
//      A*B = [C(0,0),C(0,1),C(0,2)];
		//k=0: A[0][0] + B[0][0] = 2 + 2 = 4  // s1→s1
		//k=1: A[0][1] + B[1][0] = 2 + 2 = 4  // s2→s1  
		//k=2: A[0][2] + B[2][0] = 2 + 2 = 4  // s3→s1
		//C[0][0] = min(4, 4, 4) = 4;C[0][1]同理 在所有可能字符串后加上s2 
 
//		B*B = [3, 3, 2]   //第0行:s1→?→s1 的最小代价是3,s1→?→s2 的最小代价是3,s1→?→s3 的最小代价是2 
//     		 [3, 3, 3]
//     		 [4, 3, 3]
//第1轮：i=0, j=0（s1→s1）
// k=0: C[0][0] = min(inf, B[0][0] + B[0][0]) = min(inf, 2+2) = 4 (1→1→1)
// k=1: C[0][0] = min(4, B[0][1] + B[1][0]) = min(4, 1+2) = 3  (1→2→1)
// k=2: C[0][0] = min(3, B[0][2] + B[2][0]) = min(3, 2+2) = 3  (1→3→1)
//C[0][0] = 3 即 s1→?→s1 的最小代价是3
//C[1][0] = 3 即 s2→?→s1 的最小代价是3
//C[2][0] = 4 即 s3→?→s1 的最小代价是3

//不应该理会B*B的具体含义，因为原理中是A*B*B，只是实现中是A*(B^2)，如果要理解的话还是得看原理 
//A:只有一个字符串，是所有字符串的集合;
//A*B:两个字符串，通过对A中每个字符串后加上sn选其长度最小值来当A的第n个字符串 
//A*B*B:三个字符串，通过对(A*B)中每个字符串后加上sn选其长度最小值来当A的第n个字符串 
    mat operator * (const mat &t) const {
        mat as;  // 结果矩阵
        
		//m:字符串数量 
        // 三重循环实现特殊矩阵乘法(A*B)，但使用min操作而非加法
        //这不能根据实现来看原理，原理中k在内循环，但因空间局部性，作者把k放在了外循环!!!!
		//我的天啊, 这都要贪啊，一个月工资多少啊你。 
        for (int k = 0; k < m; ++k)
		{
            for (int i = 0; i < m; ++i) 
			{
                ll tt(a[i][k]);  // 中间值 等价于ll tt = this→a[i][k],即被乘矩阵A(传进来的t是乘矩阵B); 

                for (int j = 0; j < m; ++j) 
                    as.a[i][j] = min(as.a[i][j], tt + t.a[k][j]); 
                    //                           ↑A 
            }
        }

        return as;
    }
    
    // 矩阵快速幂
    mat operator ^ (int b) {
        mat as, base;  // as: 单位矩阵，base: 底数矩阵

        // 初始化单位矩阵（对角线为0，其他为inf）
        for (int i = 0; i < m; ++i)
            as.a[i][i] = 0;

        // 复制当前矩阵(B)到底数矩阵
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < m; ++j)
                base.a[i][j] = a[i][j];

        // 快速幂算法(B*B*B……)
        while (b) 
		{
            if (b & 1)//b&1指b是奇数(最低位为1) 这是个很美丽的数学公式,本来as也要像base一样累乘的,写这段代码的人肯定是个大佬。 
                as = as * base;  // 当前位为1时乘到结果中

            base = base * base;  // 底数平方
            b >>= 1;  // 右移一位
        }

        return as;
    }
};

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
    cin >> m >> k;  // 读入字符串数量和需要出现的最小次数
	
    // 读入所有字符串并预处理
    for (int i = 1; i <= m; ++i) 
	{
        cin >> a[i];  // 读入字符串
        n[i] = a[i].size();  // 记录长度
        a[i] = " " + a[i];  // 在字符串前添加空格，使得下标从1开始
        KMP(i);  // 计算KMP(见知识点) next数组(数据结构)
    }

    // 计算转移矩阵d
    // d[i][j]表示在字符串i后面接上字符串j时，需要额外添加的字符数。eg:ab+bc 只需要加上c即可 
    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));
//                                     ↑表示字符串与自己的最长公共前后缀长度 abab 在后面链接 abab 只需要再加个 ab 即可 
	// mt(i, j):计算 字符串i的后缀 与 字符串j的前缀 的最大公共长度 

	//上面的还算好理解,就是个KMP算法的应用题,下面的就有点难了。	
	
    // 动态规划过程，使用矩阵快速幂优化(没错,又是DP)
    
    // 状态定义：f[i][u]表示使用i个字符串，以字符串u结尾时的最小长度
    // 转移方程：f[i][u] + d[u][v] -> f[i+1][v] (容易理解)
	// 本来用f已经可以做出来这题了，但作者为了降低时复,用了矩阵快速幂 
	 
    mat A, B;  // A: 初始状态矩阵，B: 转移矩阵
	
    // 初始化转移矩阵B(就是把d换个下标和数据类型) 
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < m; ++j)
            B.a[i][j] = d[i + 1][j + 1];  // 注意下标映射,d从1开始 

    // 初始化初始状态矩阵A
    // 一开始，A.a[0][i]表示以第i个字符串开头时的初始长度
    for (int i = 0; i < m; ++i)
        A.a[0][i] = n[i + 1];//容易理解 

    // 使用矩阵快速幂计算经过k-1次转移后的状态(跳转到mat类查看* ^的定义)
    A = A * (B ^ (k - 1));
	//k:需要出现的次数 
	
	//我们要构造包含 k 个字符串出现的优美字符串
	//需要从初始状态进行 k-1 次转移:B ^ (k - 1)
	
	
    // 在所有可能的最终状态中找最小值
    for (int i = 0; i < m; ++i)
        as = min(as, A.a[0][i]);
	//最后，A.a[0][j]表示：包含 k 个字符串出现的优美字符串以第j个字符串作为最后一个出现的最小长度
	
	
    cout << as;  // 输出答案
}
//你猜我得出“这不能根据实现来看原理，原理中k在内循环，但因空间局部性，作者把k放在了外循环!!!!” 这个结论花了多少时间？T_T