Rikka with String

Problem DescriptionAs 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.

 InputThe 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).

 OutputFor each testcase, print a single line with a single number — the answer modulo 998244353. Sample Input2
2 2
011
001
2 3
011
001 Sample Output1
4  题解：　　要是能在比赛中A掉就爽了　　和题解做法一样　　

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 1e4+, M = 1e3+,inf = 2e9;const LL mod = 998244353LL;int dp[][][][],sum[][N];
int nex[][N][],cnt0,cnt1,head1,tail1,head0,tail0,q[][N],fail[][N];void insert(char *s,int p) {
    int now = ,len = strlen(s);
    for(int i = ; i < len; ++i) {
        int index = s[i] - '';
        if(!nex[][now][index])
            nex[][now][index] = ++cnt0;
        sum[][nex[][now][index]] |= sum[][now];
        now = nex[][now][index];
        //cout<<now<<" "<<index<<endl;
    }
    sum[][now] |= (<<p);    now = ;
    for(int i = len-; i >= ; --i) {
        int index = s[i] - '';
        if(!nex[][now][index])
            nex[][now][index] = ++cnt1;
        sum[][nex[][now][index]] |= sum[][now];
        now = nex[][now][index];
        //cout<<now<<" "<<index<<endl;
    }
    sum[][now] |= (<<p);
}void build_fail() {
    head0 = , tail0 = ;head1 = , tail1 = ;
    for(int i = ; i < ; ++i)
        nex[][][i] = ,nex[][][i] = ;    fail[][] = ,fail[][] = ;
    q[][tail0++] = ;q[][tail1++] = ;
    while(head0 != tail0) {
        int now = q[][head0++];
        sum[][now] |= sum[][fail[][now]];
        for(int i = ; i < ; ++i) {
            int p = fail[][now];
            if(!nex[][now][i]) {
                nex[][now][i] = nex[][p][i];continue;
            }
            fail[][nex[][now][i]] = nex[][p][i];
            q[][tail0++] = nex[][now][i];
        }
    }
    while(head1 != tail1) {
        int now = q[][head1++];
        sum[][now] |= sum[][fail[][now]];
        for(int i = ; i < ; ++i) {
            int p = fail[][now];
            if(!nex[][now][i]) {
                nex[][now][i] = nex[][p][i];continue;
            }
            fail[][nex[][now][i]] = nex[][p][i];
            q[][tail1++] = nex[][now][i];
        }
    }
}
int len[N],mx,n,L;
char a[N];
int dfs() {
    int now = ;
    int ret = ;
    for(int i = ; i <= *mx; ++i) {
        now = nex[][now][len[i]];
        ret |= sum[][now];
    }
    return ret;
}
int ma(int p) {
    int now = ;
    if(p)
        for(int i = mx; i >= ; --i)
            now = nex[][now][len[i]];
    else
        for(int i = mx+; i <= *mx; ++i)
            now = nex[][now][len[i]];
    return now;
}
void init() {
    memset(dp,,sizeof(dp));
    memset(nex,,sizeof(nex));
    cnt0 = ;mx = -;cnt1 = ;
    memset(fail,,sizeof(fail));
    memset(sum,,sizeof(sum));
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&L);
        init();
        for(int i = ; i <= n; ++i) {
            scanf("%s",a);
            insert(a,i-);
            mx = max(mx,(int)strlen(a));
        }
        int ff = ;
        mx-=;
        build_fail();
        for(int i = ; i < (<<mx); ++i) {
            for(int j = ; j <= mx; ++j) len[j] = ((i>>(j-))&);
            for(int j = mx+; j <= *mx; ++j) len[j] = ^(len[*mx - j + ]);
            int now = dfs();
            int z = ma(),f = ma();
            dp[ff][z][f][now] += ;
             dp[ff][z][f][now] %= mod;
           // cout<<i<<" "<<now<<" "<<z<<" "<<f<<endl;
        }        for(int i = mx; i < L; i++) {
            memset(dp[ff^],,sizeof(dp[ff^]));
            for(int j = ; j < tail1; ++j) {
                for(int k = ; k < tail0; ++k) {
                    for(int h = ; h < (<<n); ++h) {                        if(!dp[ff][q[][j]][q[][k]][h]) continue;                        int p = nex[][q[][j]][],np = nex[][q[][k]][];
                        int tmp = (h|sum[][p]);
                        tmp |= sum[][np];                        dp[ff^][p][np][tmp] += dp[ff][q[][j]][q[][k]][h];
                         dp[ff^][p][np][tmp] %= mod;                         p = nex[][q[][j]][],np = nex[][q[][k]][];
                        tmp = (h|sum[][p]);
                        tmp |= sum[][np];                          dp[ff^][p][np][tmp] += dp[ff][q[][j]][q[][k]][h];
                         dp[ff^][p][np][tmp] %= mod;                    }
                }
            }
            ff^=;
        }
        LL ans = ;
        for(int i = ; i < tail1; ++i)
            for(int j = ; j < tail0; ++j)
                ans = ( ans + dp[ff][q[][i]][q[][j]][(<<n)-]) % mod;
        printf("%lld\n",ans);
    }
    return ;
}