Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has n 01 strings si, and he wants to know the number of 01 antisymmetric strings of length 2L which contain all given strings si as continuous substrings.
A 01 string s is antisymmetric if and only if s[i]≠s[|s|−i+1] for all i∈[1,|s|].
It is too difficult for Rikka. Can you help her?
In the second sample, the strings which satisfy all the restrictions are 000111,001011,011001,100110.
Input
The first line contains a number t(1≤t≤5), the number of the testcases.
For each testcase, the first line contains two numbers n,L(1≤n≤6,1≤L≤100).
Then n lines follow, each line contains a 01 string si(1≤|si|≤20).
Output
For each testcase, print a single line with a single number -- the answer modulo 998244353.
Sample Input
2
2 2
011
001
2 3
011
001
Sample Output
1
4
题意：反对称：对于一个长为2*N的串s[0~2*N-1]，s[i]^s[2*N-1-i]=1 。现在有n个01串，求有多少个长为2*L的并且包含这n个串的 反对称01串？
思路：对于一个串包含在2*L的01串中，那么这个串要么在2*L的前半部分，要么后半部分，或者跨越中间，如果在后半部分，则需要找到其在前半部分的反对称01串，对于跨越中间的01串，则需要找到其在前面部分的串，例如：0 | 11，以竖线作为串中间，那么如果前面部分如果以00结束，那么一定含有 011这个串。把每个串的所有形式放入AC自动机对应的tire树中，然后状压递推。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
const int mod=;
const int N=;
struct Node{
int id;
Node *fail;
Node *son[];
int tag1,tag2;
}node[N];
queue<Node *>q;
int tot;
int dp[][][]; void insert1(string s,int id)
{
int len=s.length();
Node *now=&node[];
for(int i=;i<len;i++)
{
int x=s[i]-'';
if(now->son[x]==NULL) now->son[x]=&node[tot++];
now=now->son[x];
}
now->tag1|=(<<id);
}
void insert2(string s,int id)
{
int len=s.length();
Node *now=&node[];
for(int i=;i<len;i++)
{
int x=s[i]-'';
if(now->son[x]==NULL) now->son[x]=&node[tot++];
now=now->son[x];
}
now->tag2|=(<<id);
}
void init()
{
for(int i=;i<N;i++)
{
node[i].id=i;
node[i].fail=NULL;
node[i].son[]=node[i].son[]=NULL;
node[i].tag1=node[i].tag2=;
}
}
void setFail()
{
Node* root=&node[];
q.push(root);
while(!q.empty())
{
Node* now=q.front(); q.pop();
for(int i=;i<;i++)
{
if(now->son[i])
{
Node* p=now->fail;
while(p && (!(p->son[i]))) p=p->fail;
now->son[i]->fail=(p)?(p->son[i]):(root);
now->son[i]->tag1|=now->son[i]->fail->tag1;
now->son[i]->tag2|=now->son[i]->fail->tag2;
q.push(now->son[i]);
}
else now->son[i]=(now!=root)?now->fail->son[i]:(root);
}
}
}
void print()
{
Node* now=&node[];
queue<Node*>qq;
qq.push(now);
while(!qq.empty())
{
now=qq.front(); qq.pop();
cout<<"Y:"<<now->id<<" ";
for(int i=;i<;i++)
{
if(now->son[i]) qq.push(now->son[i]),cout<<now->son[i]->id<<" ";
else cout<<"NULL"<<" ";
}
cout<<endl;
}
}
int main()
{
///cout << "Hello world!" << endl;
int t; cin>>t;
while(t--)
{
init();
tot=;
int n,L; scanf("%d%d",&n,&L);
for(int i=;i<n;i++)
{
string s; cin>>s;
insert1(s,i);
string t=s;
reverse(t.begin(),t.end());
int len=s.length();
for(int j=;j<len;j++)
t[j]=(char)((t[j]-'')^+'');
insert1(t,i); int mnLen=min(len,L);
for(int j=;j<mnLen;j++)
{
int f=;
for(int l=j,r=j+; l>=&&r<len; l--,r++)
{
if((s[l]^s[r])==) { f=; break; }
}
if(!f) continue;
t=s.substr(,j+);
for(int k=*j+;k<len;k++)
{
t=(char)((s[k]-'')^+'')+t;
}
insert2(t,i);
}
}
///print();
setFail();
memset(dp,,sizeof(dp));
dp[][][]=;
int cn=,stu=(<<n);
for(int i=;i<L;i++)
{
int c=cn^;
memset(dp[c],,sizeof(dp[c]));
for(int j=;j<tot;j++)
{
for(int s=;s<stu;s++)
{
if(!dp[cn][j][s]) continue;
if(i<L-)
for(int k=;k<;k++)
{
int x=node[j].son[k]->id;
int tag=node[x].tag1;
dp[c][x][s|tag]=(dp[c][x][s|tag]+dp[cn][j][s])%mod;
}
else
for(int k=;k<;k++)
{
int x=node[j].son[k]->id;
int tag=node[x].tag1|node[x].tag2;
dp[c][x][s|tag]=(dp[c][x][s|tag]+dp[cn][j][s])%mod;
}
}
}
cn=c;
}
int ans=;
for(int i=;i<tot;i++)
{
ans=(ans+dp[cn][i][stu-])%mod;
}
printf("%d\n",ans);
}
return ;
}