题意
有
n
n
n 个单词，现在要生成
m
m
m 个字母的文本，问至少出现一个单词的文本有多少种。
n
≤
60
,
m
≤
100
,
∣
s
i
∣
≤
100
n\leq 60,m\leq 100,|s_i|\leq 100
n≤60,m≤100,∣si∣≤100
s
i
s_i
si 只包含大写英文字母。
分析
这算是一道很典型的
A
C
AC
AC 自动机上
d
p
dp
dp 的题目。 答案就是用
2
6
m
26^m
26m 减去一个单词都没出现过的。现在我们求一下后面的东西。 令
f
i
,
j
f_{i,j}
fi,j 表示长度为
i
i
i，来到节点
j
j
j 的方案数。 那么如果
t
r
j
,
k
tr_{j,k}
trj,k 不是末尾节点，就可以转移到
t
r
j
,
k
tr_{j,k}
trj,k。 初始条件
f
0
,
0
=
1
f_{0,0}=1
f0,0=1。 总复杂度是
O
(
26
n
∣
s
∣
m
)
O(26n|s|m)
O(26n∣s∣m)
代码如下
#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds
;
using namespace std
;
typedef long long LL
;
typedef unsigned long long uLL
;
struct custom_hash
{
static uint64_t splitmix64(uint64_t x
) {
x
+= 0x9e3779b97f4a7c15;
x
= (x
^ (x
>> 30)) * 0xbf58476d1ce4e5b9;
x
= (x
^ (x
>> 27)) * 0x94d049bb133111eb;
return x
^ (x
>> 31);
}
size_t
operator()(uint64_t x
) const {
static const uint64_t FIXED_RANDOM
= chrono
::steady_clock
::now().time_since_epoch().count();
return splitmix64(x
+ FIXED_RANDOM
);
}
};
LL z
= 1;
int read(){
int x
, f
= 1;
char ch
;
while(ch
= getchar(), ch
< '0' || ch
> '9') if(ch
== '-') f
= -1;
x
= ch
- '0';
while(ch
= getchar(), ch
>= '0' && ch
<= '9') x
= x
* 10 + ch
- 48;
return x
* f
;
}
int ksm(int a
, int b
, int p
){
int s
= 1;
while(b
){
if(b
& 1) s
= z
* s
* a
% p
;
a
= z
* a
* a
% p
;
b
>>= 1;
}
return s
;
}
const int mod
= 1e4 + 7, N
= 6e3 + 5;
int f
[105][N
], ch
[N
][26], fail
[N
], v
[N
], cnt
;
char s
[N
];
void insert(char *s
){
int i
, p
= 0, c
, n
= strlen(s
);
for(i
= 0; i
< n
; i
++){
c
= s
[i
] - 'A';
if(!ch
[p
][c
]) ch
[p
][c
] = ++cnt
;
p
= ch
[p
][c
];
}
v
[p
] = 1;
}
void get_fail(){
int i
, a
;
queue
<int> q
;
for(i
= 0; i
< 26; i
++) if(ch
[0][i
]) q
.push(ch
[0][i
]);
while(!q
.empty()){
a
= q
.front(); q
.pop();
for(i
= 0; i
< 26; i
++){
if(ch
[a
][i
]) v
[ch
[a
][i
]] |= v
[ch
[fail
[a
]][i
]], fail
[ch
[a
][i
]] = ch
[fail
[a
]][i
], q
.push(ch
[a
][i
]);
else ch
[a
][i
] = ch
[fail
[a
]][i
];
}
}
}
int main(){
int i
, j
, k
, n
, m
, ans
;
n
= read(); m
= read();
for(i
= 1; i
<= n
; i
++){
scanf("%s", s
);
insert(s
);
}
get_fail();
ans
= ksm(26, m
, mod
);
f
[0][0] = 1;
for(i
= 0; i
<= m
; i
++){
for(j
= 0; j
<= cnt
; j
++){
for(k
= 0; k
< 26; k
++){
if(!v
[ch
[j
][k
]]){
f
[i
+ 1][ch
[j
][k
]] = (f
[i
+ 1][ch
[j
][k
]] + f
[i
][j
]) % mod
;
}
}
}
}
for(i
= 0; i
<= cnt
; i
++) ans
= (ans
- f
[m
][i
]) % mod
;
printf("%d", (ans
+ mod
) % mod
);
return 0;
}
