Farmland(AC自动机+状压DP+FWT)

描述

题目来源:2018ICPCCamp Day3 - Problem F

Given $n$($1 ≤ n ≤ 6$) strings, Mr. B wants to know the number of strings with length $l$, that contain all the given strings as substrings.
As the result might be very large, he wants to know the result modulo $998244353$.
Only the lower case letters are allowed, which means there are $26$ letters.
The length of each given string is at most $6$.

Input

The first line contains two integers $l$($0 ≤ l ≤ 10 ^ 9 $), $n$($1 ≤ n ≤ 6$).
The next $n$ lines contains $n$ strings.

Output

Output the answer in one line.

Example

Input Output
1
2
3
3 2
a
b
1
150
1
2
3
6 2
xyy
xxy
1
2030
1
2
100 1
bike
1
422613838

思路

  • 建立AC自动机,我们可以得到一个显然(似乎不显然啊0.0和之前做过的CF696D有点像的套路?)的DP。
    $dp[s][i][j]$表示$i→j$经过一条边后字符串状态为$s$的方案数。那么有
    $$dp[r][i][j] = \sum_{r=s \lor t} \sum_k dp[s][i][k] * dp[t][k][j]$$这样做$l-1$次显然是不行的,使用矩阵快速幂加速。这样复杂度就是$O(2^{2n}\sum \limits_i{|s_i|} \log l)$。
  • 由于上面的DP方程有个集合并的卷积式,我们可以考虑对矩阵做快速沃尔什变换(或快速莫比乌斯变换),这样在做矩阵集合并卷积运算时就可以减少复杂度了。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;

typedef vector<ll> vec;
typedef vector<vec> mat;
typedef vector<mat> Mat;

Mat mul(Mat& A, Mat& B)
{
Mat C(A.size(), mat(A[0].size(), vec(A[0].size())));
int n = A.size();
int m = A[0].size();
for (int u = 0; u < n; u++)
for (int i = 0; i < m; i++)
for (int k = 0; k < m; k++)
if (A[u][i][k])
for (int j = 0; j < m; j++)
(C[u][i][j] += A[u][i][k] * B[u][k][j]) %= mod;
return C;
}

Mat Pow(Mat& A, ll n)
{
Mat B(A.size(), mat(A[0].size(), vec(A[0].size())));
B = A;
int sz = A[0].size();
--n;
for (; n; n >>= 1, A = mul(A, A))
if (n & 1) B = mul(B, A);
return B;
}

mat Add(mat& A, mat& B)
{
int n = A.size();
mat C(n, vec(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = (A[i][j] + B[i][j]) % mod;
return C;
}

mat Sub(mat& A, mat& B)
{
int n = A.size();
mat C(n, vec(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = (A[i][j] - B[i][j] + mod) % mod;
return C;
}

void fwt(Mat& a, int l, int r)
{
if (l == r) return;
int mid = l + r >> 1, len = mid - l + 1;
fwt(a, l, mid);
fwt(a, mid + 1, r);
for (int i = l; i <= mid; i++)
{
mat u = a[i], v = a[i + len];
a[i + len] = Add(u, v);
}
}

void ifwt(Mat& a, int l, int r)
{
if (l == r) return;
int mid = l + r >> 1, len = mid - l + 1;
for (int i = l; i <= mid; i++)
{
mat u = a[i], v = a[i + len];
a[i + len] = Sub(v, u);
}
ifwt(a, l, mid);
ifwt(a, mid + 1, r);
}

ll Pow(ll a, ll n)
{
ll t = 1;
for (; n; n >>= 1, (a *= a) %= mod)
if (n & 1) (t *= a) %= mod;
return t;
}

const int maxn = 50;
struct Trie
{
int ch[maxn][26], f[maxn], val[maxn];
int sz, rt;
int newnode()
{
clr(ch[sz], -1), val[sz] = 0;
return sz++;
}
void init() { sz = 0, rt = newnode(); }
inline int idx(char c) { return c - 'a'; };
void insert(const char* s, const int& id)
{
int u = 0, n = strlen(s);
for (int i = 0; i < n; i++)
{
int c = idx(s[i]);
if (ch[u][c] == -1) ch[u][c] = newnode();
u = ch[u][c];
}
val[u] |= (1 << id);
}
void build()
{
queue<int> q;
f[rt] = rt;
for (int c = 0; c < 26; c++)
{
if (~ch[rt][c])
f[ch[rt][c]] = rt, q.push(ch[rt][c]);
else
ch[rt][c] = rt;
}
while (!q.empty())
{
int u = q.front();
q.pop();
val[u] |= val[f[u]];
for (int c = 0; c < 26; c++)
{
if (~ch[u][c])
f[ch[u][c]] = ch[f[u]][c], q.push(ch[u][c]);
else
ch[u][c] = ch[f[u]][c];
}
}
}
void solve(int l, int n)
{
if (l == 0)
{
puts("0");
return;
}
Mat G((1 << n), mat(sz, vec(sz)));
for (int u = 0; u < sz; u++)
for (int c = 0; c < 26; c++)
G[val[ch[u][c]]][u][ch[u][c]]++;
fwt(G, 0, G.size() - 1);
G = Pow(G, l);
ifwt(G, 0, G.size() - 1);
ll ans = 0;
for (int i = 0; i < sz; i++)
(ans += G[(1 << n) - 1][rt][i]) %= mod;
printf("%lld\n", ans);
}
} ac;

char buf[10];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int l, n;
scanf("%d%d", &l, &n);
ac.init();
for (int i = 0; i < n; i++)
{
scanf("%s", buf);
ac.insert(buf, i);
}
ac.build();
ac.solve(l, n);
return 0;
}
捐助作者
0%