题解 P3502 【[POI2010]CHO-Hamsters】
wlzhouzhuan
·
·
题解
讲一下自己的大致思路。
先说一下暴力分：
这是我看到此题的第一反应：dp，复杂度为O(n^2m)。
我们先定义两字符串间的距离值dis[i][j]，表示j号串拼接在i号串之后，需要在i号串末尾添加的字符数。
此时我们再用dp[i][j] 表示这个串里应经有了i个字符串，并且最后出现在该串里的子串是j号串的答案，显然可以按下转移：
dp[1][i]=len(i)$，表示取1个字符串，并且是第$i$个字符串结尾，那么它的代价显然是$len(i)
后面拼接上$j$号字符串，添加字符量即为$dis[k][j]$。
注意转移时的顺序，应该先枚举$i$，再枚举$j$和$k$。读者可以想想，为什么？
贴一下`dp`的核心部分：
```cpp
void DP() {
memset(dp, 0x7f, sizeof(dp));
for (int i = 1; i <= n; i++)
dp[1][i] = len[i];
for (int i = 2; i <= m; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
dp[i][j] = min(dp[i][j], dp[i - 1][k] + dis[k][j]);
}
```
所以，我们分析想到了转移公式，那么答案即为$min\{ dp[m][i]\}$，其中$1\le i\le n$（因为一共有$n$种字符串）。
看到有$n$个字符串，并且是一个个字符串首尾拼接而成的，我们很自然的想到`AC自动机`。
在本人经过长达1小时的思考后，终于想出了正解。。。
本人比较擅长`KMP算法`，看到这题，果断想到是`KMP`，粗略计算一下，`KMP()`函数部分的复杂度为$O(\sum^{n}_{i=1}\sum^{n}_{j=1}(len(i)+len(j)))= O(\sum^{n}_{i=1}(n\times len[i]+\sum |S|))≈ O(n|S|)$，稍微带一点小常数。
下面是`KMP`部分的代码：
```cpp
void KMP() {
// kmp1：单个字符串内匹配
for (int p = 1; p <= n; p++) {
int j = 0;
for (int i = 2; i <= len[p]; i++) {
while (j > 0 && str[p][j + 1] != str[p][i])
j = nxt[p][j];
if (str[p][j + 1] == str[p][i]) j++;
nxt[p][i] = j;
}
}
// kmp2：两两字符串间匹配
for (int p1 = 1; p1 <= n; p1++) {
for (int p2 = 1; p2 <= n; p2++) {
int j = 0;
for (int i = 2; i <= len[p1]; i++) {
while (j > 0 && str[p2][j + 1] != str[p1][i])
j = nxt[p2][j];
if (str[p2][j + 1] == str[p1][i]) j++;
if (i == len[p1]) {
a.v[p1][p2] = len[p2] - j;
}
}
}
}
}
```
好，既然我们已经预处理`KMP`得到了两两字符串间的关系（末尾添加字符量），那么我们接下来考虑如何优化`dp`。
读者不妨再回头去看看`dp`的转移部分，有没有发现，这个转移方式似曾相识？
没错，这似乎与`floyd`的转移代码有异曲同工之妙。它的转移方式，跟`floyd`是一模一样的！那么这个转移方式等价于一个$O(n^3)$的`floyd`，我们从另一种角度去考虑如何优化这个伪的`floyd`。
在优化复杂度之前，请读者先考虑一些细节问题：
首先，将这个转换成`floyd`，是基于点操作的，我们可以将每一个字符串的每一个字符都视作是一个点，这下次就是彻彻底底的`floyd`了233。
其次，我们不知道该从第几号字符串作为整一个串的起点，所以我们考虑加一个`超级源`，设它为$0$号串，将$0$号串连接到第$i(1\le i\le n)$号串。从$0$到$i$的权值为$dis[0][i] = len(i)$，从$i$到$0$显然做不到，所以设置为无穷大，即：$dis[i][0] = inf$。
好了，接下来我们考虑如何去优化复杂度。
很显然，数据范围中$m$的范围特别大，已经到了$1e9$的地步，此时我们就数据范围倒推，显然不可能是$O(m)$线性扫，所以极大可能是$O(\sqrt{m})$或者$O(logm)$。
如果是$O(\sqrt{n})$，那么一定有关于开根号的东西，但`floyd`显然不可能与根号发生关系，所以暂时排除。
那么我们发现只可能是$O(logm)$的复杂度内运行`floyd`，此时我们果断想到：与$log$有关的，极大可能是`快速幂`，但这不是$a^p$的形式，而是一个二维的幂形式。
相信读者都已经猜到了，这就是`矩阵快速幂`！
综上，我们发现，这道题可以在$O(n|S|+n^2*log\space m)$的复杂度内跑出结果，常数较小，值得一试。
同时，作为前人，也提醒一下大家：这道题可能要开$-O2$才能$AC$,`数据#1`稍微有点卡常数！
献上代码，完美撒花：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 202;
const int M = 100002;
string str[N];
int len[N], t;
int nxt[N][M];
//int dis[201][201];
int n, m;
struct MAT {
ll v[N][N];
void print() {
for (int i = 0; i <= n; i++, puts(""))
for (int j = 0; j <= n; j++)
printf("%lld ", v[i][j]);
putchar('\n');
}
} ans, a;
MAT operator * (MAT a, MAT b) {
MAT c;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
c.v[i][j] = 1e15;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++)
c.v[i][k] = min(c.v[i][k], a.v[i][j] + b.v[j][k]);
return c;
}
void KMP() {
// init
a.v[0][0] = 1e15;
for (int p = 1; p <= n; p++)
a.v[0][p] = len[p], a.v[p][0] = 1e15;
// kmp1
for (int p = 1; p <= n; p++) {
int j = 0;
for (int i = 2; i <= len[p]; i++) {
while (j > 0 && str[p][j + 1] != str[p][i])
j = nxt[p][j];
if (str[p][j + 1] == str[p][i]) j++;
nxt[p][i] = j;
}
}
// kmp2
for (int p1 = 1; p1 <= n; p1++) {
for (int p2 = 1; p2 <= n; p2++) {
int j = 0;
for (int i = 2; i <= len[p1]; i++) {
while (j > 0 && str[p2][j + 1] != str[p1][i])
j = nxt[p2][j];
if (str[p2][j + 1] == str[p1][i]) j++;
if (i == len[p1]) {
a.v[p1][p2] = len[p2] - j;
}
}
}
}
/*
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
printf("dis[%d][%d] = %d\n", i, j, dis[i][j]);
*/
}
void ksm() {
//a.print();
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
ans.v[i][j] = a.v[i][j];
// woc, m--!
m--;
while (m > 0) {
//printf("in ksm %d\n", m);
//ans.print(); a.print();
//printf("----------\n");
if (m & 1) ans = ans * a;
a = a * a; m >>= 1;
}
}
bool check() {
for (int i = 1; i <= n; i++) {
if (len[i] == 1) return 1;
}
return 0;
}
signed main() {
scanf("%lld%lld", &n, &m);
if (m == 0) {
puts("0"); return 0;
}
for (int i = 1; i <= n; i++) {
cin >> str[i];
len[i] = str[i].size();
str[i] = ' ' + str[i];
}
if (check()) {
printf("%lld\n", m);
return 0;
}
KMP();
ksm();
ll anss = 2e15;
for (int i = 1; i <= n; i++)
anss = min(anss, ans.v[0][i]);
printf("%lld\n", anss);
return 0;
}
```
附：如果有$WA$的网友，我在这里提供几组$hack$数据，您可以不妨一测。
$\color{red}hack1.in
5 100
a
b
c
d
e
\color{red}hack1.out
100
\color{red}hack2.in
1 0
a
\color{red}hack2.out
0
\color{red}hack3.in
4 5
ab
bc
cd
de
\color{red}hack3.out
7