Description：

给一个 $01$ 串集合 $S$ ，求有几个长度为 $n$ 的 $01$ 回文串中不存在 $1\leqslant a\leqslant b<c\leqslant d\leqslant n$ 使得 $[a:b]$ 和 $[c:d]$ 都出现过。

$1\leqslant n\leqslant 1000,1\leqslant l\leqslant 30,1\leqslant \sum l\leqslant 1000$

Solution：

考虑从两边往中间枚举字符，建立两个 $AC$ 自动机，分别插入正串和反串，设 $f[i][x][y][0/1]$ 表示经过了 $i$ 位，第一个自动机匹配到了 $x$ ，第二个自动机匹配到了 $y$ ，目前产生了 $0/1$ 个匹配，因为如果匹配大于等于 $2$ 就不合法了，然后每次枚举字符转移，注意因为要求两个匹配不交，那么如果产生了一个匹配就把指针指到根节点上去，如果 $n$ 是奇数就让左指针单独转移一下，这样看上去时间复杂度是 $O(n(\sum l_i)^2)$ 的，但是由于一个指针一定是另一个的前缀，那么我们用 $vector$ 来记录有用的状态，时间复杂度 $O(n\sum l_i\max{l_i})$ ，最后要把两边的合并，就暴力的把一个往根节点上跳，另一个跟着走，如果走到了一个标记处就非法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXL 1010

char c[MAXL];

struct ACAM

{

	struct node

	{

		int tr[2],fail;

		int tag;

		int fa,w;

	}t[MAXL];

	int ptr;

	ACAM(){ptr = 0;}

	int newnode(){return ++ptr;}

	int root;

	void insert(char c[])

	{

		int l = strlen(c + 1);

		int cur = root;

		for(int i = 1;i <= l;++i)

		{

			int w = c[i] - '0';

			if(t[cur].tr[w] == 0)

			{

				t[cur].tr[w] = newnode();

				t[t[cur].tr[w]].w = w;

				t[t[cur].tr[w]].fa = cur;

			}

			cur = t[cur].tr[w];

		}

		t[cur].tag = 1;

		return;

	}

	void make_fail()

	{

		queue<int> q;

		for(int i = 0;i <= 1;++i)

		{

			if(t[root].tr[i])

			{

				t[t[root].tr[i]].fail = root;

				q.push(t[root].tr[i]);

			}

		}

		while(!q.empty())

		{

			int k = q.front();q.pop();

			for(int i = 0;i <= 1;++i)

			{

				if(t[k].tr[i] != 0)

				{

					t[t[k].tr[i]].fail = t[t[k].fail].tr[i];

					t[t[k].tr[i]].tag |= t[t[t[k].tr[i]].fail].tag;

					q.push(t[k].tr[i]);

				}

				else t[k].tr[i] = t[t[k].fail].tr[i];

			}

		}

	}

}t1,t2;

int f[2][MAXL][MAXL][2];

struct state{int x,y,v;};

vector<state> st[2];

#define MOD 1000000007

int main()

{

	freopen("palindrome.in","r",stdin);

	freopen("palindrome.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%s",c + 1);

		t1.insert(c);

		int l = strlen(c + 1);

		for(int x = 1,y = l;x < y;++x,--y)swap(c[x],c[y]);

		t2.insert(c);

	}

	t1.make_fail();t2.make_fail();

	int cur = 0;

	f[cur][0][0][0] = 1;st[cur].push_back((state){0,0,0});

	for(int i = 1;i <= n / 2;++i)

	{

		cur ^= 1;

		for(vector<state>::iterator it = st[cur].begin();it != st[cur].end();++it)f[cur][it -> x][it -> y][it -> v] = 0;

		st[cur].clear();

		for(vector<state>::iterator it = st[cur ^ 1].begin();it != st[cur ^ 1].end();++it)

		{

			int x = it -> x,y = it -> y,v = it -> v;

			if(f[cur ^ 1][x][y][v] == 0)continue;

			for(int k = 0;k <= 1;++k)

			{

				int nx = t1.t[x].tr[k],ny = t2.t[y].tr[k];

				int sum = t1.t[nx].tag + t2.t[ny].tag + v;

				if(t1.t[nx].tag)nx = t1.root;

				if(t2.t[ny].tag)ny = t2.root;

				if(sum <= 1)

				{

					if(f[cur][nx][ny][sum] == 0)st[cur].push_back((state){nx,ny,sum});

					f[cur][nx][ny][sum] = (f[cur][nx][ny][sum] + f[cur ^ 1][x][y][v]) % MOD;

				}

			}

		}

	}

	if(n & 1)

	{

		cur ^= 1;

		memset(f[cur],0,sizeof(f[cur]));

		for(int k = 0;k <= 1;++k)

		{

			for(vector<state>::iterator it = st[cur ^ 1].begin();it != st[cur ^ 1].end();++it)

			{

				int x = it -> x,y = it -> y,v = it -> v;

				if(f[cur ^ 1][x][y][v] == 0)continue;

				int nx = t1.t[x].tr[k];

				int sum = t1.t[nx].tag + v;

				if(t1.t[nx].tag)nx = t1.root;

				if(sum <= 1)

				{

					f[cur][nx][y][sum] = (f[cur][nx][y][sum] + f[cur ^ 1][x][y][v]) % MOD;

				}

			}

		}

	}

	int ans = 0;

	for(int i = 0;i <= t1.ptr;++i)

	{

		for(int j = 0;j <= t2.ptr;++j)

		{

			ans = (ans + f[cur][i][j][0]) % MOD;

			int cur1 = i,cur2 = j;

			bool tag1 = true,tag2 = true;

			while(cur1)

			{

				cur2 = t2.t[cur2].tr[t1.t[cur1].w];

				cur1 = t1.t[cur1].fa;

				if(t2.t[cur2].tag){tag1 = false;break;}

			}

			while(cur2)

			{

				cur1 = t1.t[cur1].tr[t2.t[cur2].w];

				cur2 = t2.t[cur2].fa;

				if(t1.t[cur1].tag){tag2 = false;break;}

			}

			if(f[cur][i][j][1] && tag1 && tag2)ans = (ans + f[cur][i][j][1]) % MOD;

		}

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}