#1955. 第二基地
第二基地
第二基地
题目描述
标题: 第二基地 - Problem - QOJ.ac
#14578. 第二基地
群星的尽头
题目大意
给定整数 m,定义字符集 Σ 为前 m 个小写字母,对于两个字符集为 Σ 的串 A,B,定义 f(A,B) 为如下问题的答案:存在一个有限大小的自动机 M,使得输入字符集为 Σ 的,任意长度的字符串 S,都可以比较 A 与 B 在 S 中的出现次数(返回 <,=,>)。如果存在,则 f(A,B)=1,否则 f(A,B)=0。给定 n 个串 s1∼sn,你要求出 ∑1≤i<j≤nf(si,sj)
在本题中,我们定义自动机 M 是一个五元组 (Q,Σ,δ,q0,F),其中 Q 是状态集合,Σ 是字符集,δ:Q×Σ→Q 是转移函数,q0 是起始状态,F:Q→{<,=,>} 表示每个状态对应的结果。定义这个自动机可以比较 A 和 B 在 S 中的出现次数,当且仅当 F(δ(…δ(δ(q0,S1),S2)…,S|S|))∈{<,=,>} 为 A 和 B 在 S 中出现次数的大小关系。
输入格式
第一行两个正整数 n,m。
接下来 n 行,第 i 行一个字符串 si,字符集为前 m 个小写字母
输出格式
输出一行一个整数,表示答案。
样例输入 1
3 26
ct
ctt
cts
样例输出 1
2
样例 2~7
见附加文件中的 ex_dfa2.in/out 到 ex_dfa7.in/out,第 i+1 个样例满足子任务 i 的限制。
数据范围
对于所有测试点,2≤n≤106,N=∑i=1n|si|≤106,2≤m≤26。
子任务编号 N≤ 特殊性质 分数 1 1000 |si|≤3,m≤3 10 2 5000 m=10 10 3 106 m=10 20 4 500 无 20 5 5000 无 10 6 106 无 30
本题开启合理的子任务依赖
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 26
ct
ctt
cts
2
样例 2
300 2
b
aba
ba
ba
bb
b
bb
aba
b
aa
ba
b
baa
abb
aa
ab
aa
b
b
b
ba
aa
b
ab
aaa
baa
bb
abb
aaa
baa
b
ab
ab
ba
aa
b
bba
b
b
a
aa
a
aa
abb
bb
aa
bba
a
bba
bb
baa
bba
a
abb
ab
bba
b
b
a
bbb
bb
b
aab
aba
a
bba
b
aba
a
aa
aa
aaa
b
baa
a
a
aaa
bb
ba
a
abb
a
a
aaa
bba
aab
baa
b
a
ab
a
ab
bab
ab
b
ba
bb
ba
aa
ab
ba
bb
aa
aab
a
bba
a
b
bba
aa
a
b
aab
aaa
ab
a
a
a
ab
b
aab
ba
aaa
a
b
bbb
aa
a
a
aa
b
ab
baa
ba
b
b
bbb
ab
aa
b
bab
b
aa
abb
bab
abb
ba
bb
aab
a
b
bb
ab
aba
b
b
aba
b
ab
ba
a
a
a
b
a
a
b
aab
bb
aa
a
aba
aa
a
b
aa
aba
ba
b
b
bbb
bba
ab
baa
a
bbb
bbb
bbb
aab
bba
aaa
aa
a
aa
aba
aab
aa
bbb
baa
aab
b
b
b
b
b
b
b
ba
a
bab
bab
bb
bb
bbb
aa
a
b
b
b
bab
b
bba
a
baa
aaa
bbb
aba
bbb
a
a
bb
b
ab
b
aa
bbb
aab
b
baa
abb
bab
abb
bb
aaa
b
baa
b
a
aa
ba
bbb
aaa
abb
ab
a
bb
aa
aa
bb
ba
a
a
b
bab
a
aaa
aba
ab
aa
bb
aab
aba
b
ab
bba
a
ba
aab
b
aa
ab
bbb
ab
bab
abb
bbb
ab
aa
aa
a
aba
aa
bab
bab
ba
a
aba
aa
a
aaa
26321