Blackops

初心易得，始终难守

0%

CCF CSP 201509-5 最佳文章（AC自动机+矩阵快速幂）

发表于 更新于 分类于 ，

问题描述

　　小明最近在研究一门新的语言，叫做Q语言。Q语言单词和文章都可以用且仅用只含有小写英文字母的字符串表示，任何由这些字母组成的字符串也都是一篇合法的Q语言文章。

　　在Q语言的所有单词中，小明选出了他认为最重要的n个。使用这些单词，小明可以评价一篇Q语言文章的“重要度”。
　　文章“重要度”的定义为：在该文章中，所有重要的Q语言单词出现次数的总和。其中多次出现的单词，不论是否发生包含、重叠等情况，每次出现均计算在内。
　　例如，假设n = 2，小明选出的单词是gvagv和agva。在文章gvagvagvagv中，gvagv出现了3次，agva出现了2次，因此这篇文章的重要度为3+2=5。
　　现在，小明想知道，一篇由m个字母组成的Q语言文章，重要度最高能达到多少。

输入格式

　　输入的第一行包含两个整数n, m，表示小明选出的单词个数和最终文章包含的字母个数。
　　接下来n行，每行包含一个仅由英文小写字母构成的字符串，表示小明选出的这n个单词。

输出格式

　　输出一行一个整数，表示由m个字母组成的Q语言文章中，重要度最高的文章的重要度。

样例输入

3 15
agva
agvagva
gvagva

样例输出

11

样例说明

　　15个字母组成的重要度最高的文章为gvagvagvagvagva。
　　在这篇文章中，agva出现4次，agvagva出现3次，gvagva出现4次，共计4+3+4=11次。

评测用例规模与约定

　　在评测时将使用10个评测用例对你的程序进行评测。
　　设s为构成n个重要单词字母的总个数，例如在样例中，$s=4+7+6=17$；$a$为构成$n$个重要单词字母的种类数，例如在样例中，共有3中字母’a’,’g’,’v’，因此$a=3$。
　　评测用例1和2满足$2 ≤ n ≤ 3$，$1500 ≤ m ≤ 2000$，$s = 40$；
　　评测用例3和4满足$m = 20$，$2 ≤ a ≤ 3$；
　　评测用例5、6和7满足$2000 ≤ m≤ 100000$；
　　评测用例8满足$n = 2$；
　　所有的评测用例满足$1 ≤ s ≤ 100$，$1 ≤ m≤ 10^{15}$，每个单词至少包含1个字母，保证单词中仅出现英文小写字母，输入中不含多余字符，不会出现重复的单词。

题目链接：最佳文章

首先肯定是构造AC自动机，然后本来是用$dp[i][j]$表示构造长度为$i$，走到第$j$个节点的最高重要度，$dp$数组初始化设为$-\infty$，$dp[0][0]=0$，然后$O(m*s)$地只通过合法点转移，但是后面几组数据很大，明显是矩阵快速幂，由于$max$函数具有可加性，因此可以用矩阵快速幂加一点的变形，将加号改成$max$函数，然后做$m$次$AC$自动机对应矩阵$A$的幂，最后$max{dp[0][i]}$就是答案了。

代码：

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 105;
char s[N];

namespace ac {
    struct Trie
    {
        int nxt[26], w, f;
        void init() {
            fill(nxt, nxt + 26, -1);
            w = f = 0;
        }
    } L[N];
    int sz;

    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    inline int newnode()
    {
        L[sz].init();
        return sz++;
    }
    void ins(char s[], int len)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - 'a';
            if(L[u].nxt[v] == -1)
                L[u].nxt[v] = newnode();
            u = L[u].nxt[v];
        }
        L[u].w = 1;
    }
    void build()
    {
        queue<int>Q;
        L[0].f = 0;
        for (int i = 0; i < 26; ++i)
        {
            int &v = L[0].nxt[i];
            if(~v)
            {
                Q.push(v);
                L[v].f = 0;
            }
            else
                v = 0;
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].f;
            L[u].w += L[uf].w;
            for (int i = 0; i < 26; ++i)
            {
                int &v = L[u].nxt[i];
                if(~v)
                {
                    Q.push(v);
                    L[v].f = L[uf].nxt[i];
                }
                else
                    v = L[uf].nxt[i];
            }
        }
    }
}
struct Mat
{
    LL A[N][N];
    void zero() {
        for (register int i = 0; i < N; ++i)
            for (register int j = 0; j < N; ++j)
                A[i][j] = -0x3f3f3f3f3f3f3f3f;
    }
    friend Mat operator *(const Mat &a, const Mat &b) {
        Mat ret;
        ret.zero();
        for (register int i = 0; i < N; ++i) {
            for (register int k = 0; k < N; ++k) {
                for (register int j = 0; j < N; ++j) {
                        ret.A[i][j] = max(ret.A[i][j], a.A[i][k] + b.A[k][j]);
                }
            }
        }
        return ret;
    }
    friend Mat operator ^(Mat a, LL b) {
        Mat ret = a;
        --b;
        while (b) {
            if(b & 1)
                ret = ret * a;
            a = a * a;
            b >>= 1;
        }
        return ret;
    }
} A;
int main(void)
{
    register int n, i, k;
    LL m;
    scanf("%d%lld", &n, &m);
    ac::init();
    for (i = 0; i < n; ++i)
    {
        scanf("%s", s);
        ac::ins(s, strlen(s));
    }
    ac::build();
    A.zero();
    for (i = 0; i < ac::sz; ++i)
    {
        for (k = 0; k < 26; ++k)
        {
            int v = ac::L[i].nxt[k];
            A.A[i][v] = ac::L[v].w;
        }
    }
    A = A ^ m;
    LL ans = 0;
    for (int i = 0; i < ac::sz; ++i)
        ans = max(ans, A.A[0][i]);
    printf("%lld\n", ans);
    return 0;
}