#P3768. spoj 4660 Binary palindrome二进制回文串

    ID: 2971 传统题 1000ms 256MiB 尝试: 29 已通过: 12 难度: 8 上传者: 标签>CF2400提高+/省选-AC 自动机按结束时间选区间AC 自动机 DP计数 DP滚动数组

spoj 4660 Binary palindrome二进制回文串

题目描述

给定 kk 个长度不超过 LL 的 0101 串,求有多少长度为 nn 的 0101 串 SS 满足:

  • 该串是回文串;
  • 在给定的 kk 个串中,该串不存在两个不重叠的子串。

即不存在 a≤b<c≤da \le b < c \le d,Sa∼bS_{a \sim b} 是 kk 个串中的一个,Sc∼dS_{c \sim d} 是 kk 个串中的一个。

举个例子,若给定 22 个 0101 串 (即 k=2k=2):101 和 1001 。那么 1010001 和 1010101 均不满足条件。前者不满足条件一,后者不满足条件二。

输入格式

第一行两个整数 n,kn,k。 以下 kk 行,每行一个 0101 串。

输出格式

输出一个整数表示答案,答案对 109+710^9+7 取模。

5 1
0
2

数据规模与约定

对于 100%100\% 的数据,n≤100n \le 100,k≤20k \le 20,L≤10L \le 10。