[蓝桥杯 2016 国 AC] 碱基

Luogu
IDLGP8643
Time1000ms
Memory256MB
DifficultyP5
动态规划 DP2016哈希 hashing蓝桥杯国赛
生物学家正在对 $n$ 个物种进行研究。 其中第 $i$ 个物种的 DNA 序列为 $s[i]$,其中的第 $j$ 个碱基为 $s[i][j],$ 碱基一定是 `A`,`G`,`C`,`T` 之一。 生物学家想找到这些生物中一部分生物的一些共性,他们现在关注那些至少在 $m$ 个生物中出现的长度为 $k$ 的连续碱基序列。准确的说,科学家关心的序列用 $2m$ 元组 $(i_1,p_1,i_2,p_2 \cdots ,i_m,p_m)$ 表示, 满足: $$1 \le i_1<i_2< \cdots <i_m \le n$$ 且对于所有 $q(0 \le q<k)$, $$s[i_1][p_1+q]=s[i_2][p_2+q]= \cdots =s[i_m][p_m+q]$$ 现在给定所有生物的 DNA 序列,请告诉科学家有多少的 $2m$ 元组是需要关注的。如果两个 $2m$ 元组有任何一个位置不同,则认为是不同的元组。 ## Input 输入的第一行包含三个整数 $n$,$m$,$k$,两个整数之间用一个空格分隔,意义如题目所述。 接下来 $n$ 行,每行一个字符串表示一种生物的 DNA 序列。 DNA 序列从 $1$ 至 $n$ 编号,每个序列中的碱基从 $1$ 开始依次编号,不同的生物的 DNA 序列长度可能不同。 ## Output 输出一个整数,表示关注的元组个数。 答案可能很大,你需要输出答案除以 $1000000007(10^9+7)$ 的余数。 [samples] ## Note ### 数据规模与约定 对于 $20\%$ 的数据,$k \le 5,$ 所有字符串总长 $L$ 满足 $L \le 100$。 对于 $30\%$ 的数据,$L \le 10000$。 对于 $60\%$ 的数据,$L \le 30000$。 对于 $100\%$ 的数据,$n \le 5,m \le 5,1 \le k \le L \le 10^5$。 保证所有 DNA 序列不为空且只会包含`A`,`G`,`C`,`T` 四种字母。 时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛
Samples
Input #1
3 2 2
ATC
TCG
ACG
Output #1
2
Input #2
4 3 3
AAA
AAAA
AAA
AAA
Output #2
7
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2016 国 AC] 碱基",
    "description": {
      "content": "生物学家正在对 $n$ 个物种进行研究。 其中第 $i$ 个物种的 DNA 序列为 $s[i]$,其中的第 $j$ 个碱基为 $s[i][j],$ 碱基一定是 `A`,`G`,`C`,`T` 之一。 生物学家想找到这些生物中一部分生物的一些共性,他们现在关注那些至少在 $m$ 个生物中出现的长度为 $k$ 的连续碱基序列。准确的说,科学家关心的序列用 $2m$ 元组 $(i_1,p_1,i_2",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8643"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "生物学家正在对 $n$ 个物种进行研究。\n\n其中第 $i$ 个物种的 DNA 序列为 $s[i]$,其中的第 $j$ 个碱基为 $s[i][j],$ 碱基一定是 `A`,`G`,`C`,`T` 之一。\n\n生物学家想找到这些生物中一部分生物的一些共性,他们现在关注那些至少在 $m$ 个生物中出现的长度为 $k$ 的连续碱基序列。准确的说,科学家关心的序列用 $2m$ 元组 $(i_1,p_1,i_2...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments