HDU 2243 AC自动机 + 矩阵快速幂

发表于 | 分类于 | 阅读次数：

比想象中要A的顺利很多，关键还是知道怎么处理矩阵。考察的知识很多，是很多题目的综合。

题目链接

题意

告诉你N个词根，求长度不超过L，只有小写字母组成，至少包含一个词根的单词个数。

思路

看了至少包含一个，我们自然就应该想到考虑它的对立面，就是一个也不包含，很简单把（我想不到QAQ）.然后我们看它几乎就和POJ那个DNA sequence 完全一样了，但是这个题目求的是小于L长度的，所以我们在求出转移矩阵A之后，需要求$$A^1 + A^2 + … A^L$$,这个怎么求呢，请参考POJ 3233，应用的是矩阵快速幂。最后的答案就是总的可能的种类数目也就是($26 ^ 1 + .. 26^n$),再减去最终得到的那个矩阵第一行的和。需要再提几点，就是这个可能的种类数目不要用等比数列求，因为是有余数操作的，但是我没试过到底等比数列行不行，我这里依然是矩阵快速幂求的。另外一个，题目答案要求对$2^{64}$取余,我们不必设置余数，只要把int都换成unsigned long long即可，程序就自动取余了。好久没写这么长的代码了，调BUG还好很快就过了。

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll unsigned long long
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1005;
const int kind = 26;
int cnt;

struct Matrix{
   ll m[101][101];
}M;
int nxt[50][kind], fail[50], mark[50];
int newnode()
{
    ++cnt;
    for(int i = 0; i < kind; ++i)
    {
        nxt[cnt][i] = -1;
    }
    mark[cnt] = 0;
    return cnt;
}

void word_insert(char s[])
{
    int sz = strlen(s);
    int now = 0;
    for(int i = 0; i < sz; ++i)
    {
        int tmp = s[i] - 'a';
        if(nxt[now][tmp] == -1)
            nxt[now][tmp] = newnode();
        now = nxt[now][tmp];
    }
    mark[cnt] = 1;
}


void build()
{
    fail[0] = 0;
    queue<int>Q;
    for(int i = 0; i < kind; ++i)
    {
        if(nxt[0][i] == -1)
            nxt[0][i] = 0;
        else{
            fail[nxt[0][i]] = 0;
            Q.push(nxt[0][i]);
        }
    }
    while(!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        if(mark[fail[now]])
            mark[now] = 1;
        for(int i = 0; i < kind; ++i)
        {
            if(nxt[now][i] == -1)
                nxt[now][i] = nxt[fail[now]][i];
            else{
                fail[nxt[now][i]] = nxt[fail[now]][i];
                Q.push(nxt[now][i]);
            }
        }
    }
}

void build_matrix()
{
    memset(M.m, 0, sizeof(M.m));
    for(int i = 0 ; i <= cnt; ++i)
    {
        for(int j = 0; j < kind; ++j)
        {
            if(!mark[i] && !mark[nxt[i][j]])
            {
                M.m[i][nxt[i][j]]++;
            }
        }
    }
}

Matrix mul(Matrix A, Matrix B, int sz)
{
    Matrix tmp;
    for(int i = 0; i <= sz; ++i)
    {
        for(int j = 0; j <= sz; ++j)
        {
            tmp.m[i][j] = 0;
            for(int k = 0; k <= sz; ++k)
            {
                tmp.m[i][j] = (tmp.m[i][j] + A.m[i][k] * B.m[k][j]);
            }
        }
    }
    return tmp;
}

Matrix pow(Matrix A, int n, int sz)
{
    Matrix res;
    memset(res.m, 0, sizeof(res.m));
    for(int i = 0; i <= sz; ++i)
        res.m[i][i] = 1;
    while(n)
    {
        if(n & 1)
        res = mul(res, A, sz);
        A = mul(A, A, sz);
        n >>= 1;
    }
    return res;
}

void init(){
  cnt = -1;
  newnode();
}
int main()
{
    int n,l;
    char s[6];
    while(scanf("%d %d",&n,&l) != EOF)
    {
        memset(nxt, -1, sizeof(nxt));
        memset(mark,0,sizeof(mark));
        Matrix A,B,C,D;
        A.m[0][0] = 26;
        A.m[0][1] = 1;
        A.m[1][0] = 0;
        A.m[1][1] = 1;
        B.m[0][0] = 26;
        B.m[1][0] = 26;
        A = pow(A, l - 1, 1);
        B = mul(A,B,1);
        ll num = B.m[0][0];
        init();
        for(int i  =1; i <= n; ++i)
        {
            scanf("%s",s);
            word_insert(s);
        }
        build();
        build_matrix();
        memset(C.m,0,sizeof(C.m));
        for(int i = 0; i <= cnt; ++i)
                C.m[i][i] = 1;
        for(int i = cnt + 1; i <= 2 * cnt + 1; ++i)
        {
            for(int j = cnt + 1; j <= 2 * cnt + 1; ++j )
            {
                C.m[i][j] = C.m[i - cnt - 1][j] =  M.m[i - cnt - 1][j - cnt - 1];
            }
        }
        memset(D.m, 0, sizeof(D.m));
        for(int i = cnt + 1; i <= 2 * cnt + 1; ++i)
        {
            for(int j = 0; j <= cnt; ++j)
            {
                D.m[i][j] = D.m[i - cnt - 1][j] =  M.m[i - cnt - 1][j];
            }
        }
        C = pow(C, l - 1, 2 * cnt + 1);
        D = mul(C, D, 2 * cnt + 1);
        ll sum = 0;
        for(int i = 0; i <= cnt; ++i)
        {
            sum = (sum + D.m[0][i]);
        }
        cout << num - sum << '\n';
    }
}