#1955. 第二基地

    ID: 1955 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2557来源:qoj.ac数据:公开样例字符串

第二基地

第二基地

题目描述

标题: 第二基地 - Problem - QOJ.ac

#14578. 第二基地

Statistics

群星的尽头

题目大意

给定整数 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