Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

P3502 [POI2010]CHO-Hamsters

Posted on

…

Solution

又是一道经典的矩阵快速幂在图论计数上的经典应用（自己鸽了这么多道，终于记得写了）。

首先指明一个显然的结论：$S$一定由这$n$个字符串中的一部分字符串首尾拼接组成。

得到这个结论后，我们将这$n$个字符串两两组合，找出他们首尾相接时最少的代价。

例如，字符串$A=abcabc$和字符串$B=bcda$相组合，$B$接在A后面所需的最小代价就是2。

然后我们需要在这个无向图任取一个起点上走$m-1$条边，使起点的长度+图中跑出来的代价最小。

观察我们$dp$的转移方程：$\ \forall i,j,k \rarr f[i][j]=\min (f[i][k]+f[k][j])$。

这个东西显然就是一个矩阵乘，写个矩阵加速幂就结束了。

复杂度为$O(n^2\sum len + n^3 \log m)$的，可以使用$hash$做到$O(n^2\log \sum len + n^3 \log m)$。

坑点：

  • 需要$long \ long$。
  • 从$i$和$i$的代价为$len[i]-ne[i][len[i]]$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar(' ');
}
const int N = 200 + 5, M = 1e5 + 5, mod = 2017;
const LL Inf = 1e18;
int n, m, t;
struct Node{
    LL a[N][N];
    Node operator* (Node b)
    {
        Node c;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++) c.a[i][j] = Inf;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                for(int k = 1;k <= n;k ++) 
                    c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
        return c;
    }
}b;
char s[N][M];
int ne[N][M], len[N];
inline void get_ne(int x)
{
    for(int i = 2, j = 0;i <= len[x];i ++)
    {
        while(j && s[x][j + 1] != s[x][i]) j = ne[x][j];
        if(s[x][j + 1] == s[x][i]) j ++;
        ne[x][i] = j;
    }
}
inline int kmp(int x, int y)
{
    int j = 0;
    for(int i = 1;i <= len[x];i ++)
    {
        while(j && s[y][j + 1] != s[x][i]) j = ne[y][j];
        if(s[y][j + 1] == s[x][i]) j ++;   
    }
    return j;
}
inline Node qpow(Node x, int k)
{
    Node res;
    memset(res.a, 0, sizeof(res.a));
    if(k == 0) return res;
    res = x, k --;
    while(k)
    {
        if(k & 1) res = res * x;
        x = x * x;
        k >>= 1;
    }
    return res;
}
LL ans;
char c[N];
int main()
{
    read(n, m);
    if(m == 0) return puts("0"), 0;
    for(int i = 1;i <= n;i ++)
    {
        scanf("%s", s[i] + 1), len[i] = strlen(s[i] + 1);
        get_ne(i);
    }
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            if(i != j) b.a[i][j] = len[j] - kmp(i, j);
            else b.a[i][j] = len[j] - ne[i][len[j]];
    b = qpow(b, m - 1);
    ans = Inf;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            ans = min(ans, b.a[i][j] + len[i]);
    write(ans);
    return 0;
}