Rikka with String

题目链接

题意

定义antisymmetric串为任意$1 \leq i \leq |s|$，都有$s[i] != s[|s|-i+1].$
现在问有多少长度为$2L$的antisymmetric串，包含给出的$n$个串。

思路

如果没有antisymmetric的限制，那么就是一道很裸的AC自动机上的dp。现在我们考虑加了这一个条件，我们会增加怎样的限制呢。
仔细想一想，我们这个字符串，是可以通过确定一半来得到另一半的。
对于字符串只在其中一边出现的情况，我们可以建出所有串的正串和反串，然后放在AC自动机上跑就可以啦。
那么还有另一种情况，就是这个字符串是跨过中轴的，对于我们的做法，跨过中轴的也是可以处理的，只要我们确定字符伸展到这个位置时确实包含了当前要找的字符串，首先我们枚举他跨过中轴的位置，然后看两侧是否满足反对称，如果是反对称，那么在AC自动机上建出长的那一部分，去跑dp就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
#define siz 2
const int N = 5e4 + 5;
const ll mod = 998244353;

int ch[N][siz];
int fail[N];
int ed[N], ed2[N];
int sz;
int root;
int pos[N];
char nit = '0';
void init()
{
    root = 0;
    for (int i = 0; i < siz; i++)
        ch[root][i] = -1;
    fail[root] = -1;
    ed[root] = 0;
    ed2[root] = 0;
    sz = 0;
}

int newnode()
{
    sz++;
    for (int i = 0; i < siz; i++)
    {
        ch[sz][i] = -1;
    }
    fail[sz] = -1;
    ed[sz] = 0;
    ed2[sz] = 0;
//    dbg(sz);
    return sz;
}

void insert(char buf[], int &id, bool cross)
{
    int len = strlen(buf);
    int now = root;
//    dbg(len);
    for (int i = 0; i < len; i++)
    {
        if (ch[now][buf[i] - nit] == -1)
        {
            ch[now][buf[i] - nit] = newnode();
        }
        now = ch[now][buf[i] - nit];
//        dbg(i);
    }
    if (!cross)
    {
        if (ed[now] == 0)
            ed[now] |= (1 << id), pos[now] = id;
        else
        {
            id = pos[now];
        }
    }
    else
        ed2[now] |= (1 << id);
}

void getfail()
{
    fail[root] =root;
    queue<int> Q;
    for (int i = 0; i < siz; i++)
    {
        int u = ch[root][i];
        if (u != -1)
        {
            fail[u] = root;
            Q.push(u);
        }
        else
            ch[root][i] = root;
    }
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        ed[u] |= ed[fail[u]];
        ed2[u] |= ed2[fail[u]];
        for (int i = 0; i < siz; i++)
        {
            int v = ch[u][i];
            if (v == -1)
            {
                ch[u][i] = ch[fail[u]][i];
                continue;
            }
            int tmp = fail[u];
            fail[v] = ch[tmp][i];
            Q.push(v);
        }
    }
}

/*
int query(char buf[])
{
    int len = strlen(buf);
    int cnt = 0;
    int now = root;
    resetv();
    for (int i = 0; i < len; i++)
    {
        while (now != root && !ch[now][buf[i] - nit])
            now = fail[now];
        now = ch[now][buf[i] - nit];
        int tmp = now;
        while (tmp != root)
        {
            if (ed[tmp] && !vis[tmp])
            {
                cnt += ed[tmp];
                vis[tmp] = true;
            }
            tmp = fail[tmp];
        }
    }
    return cnt;
}
*/

char s[100];
char t[100];
const int S = (1 << 6) + 5;
ll dp[2][S][N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(dp, 0, sizeof(dp));
        int n, L;
        scanf("%d%d", &n, &L);
        init();
        int mxl = 0;
        int id = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", s);
            int len = strlen(s);
            mxl = max(mxl, len);
            int now = id;
            insert(s, now, 0);
            for (int i = 0; i < len; i++)
                t[i] = (s[len - i - 1] == '0')? '1' : '0' ;
            t[len] = 0;
//            puts(s);
//            puts(t);
            insert(t, now, 0);
            for (int k = 1; k < len; k++)
            {
                bool f = 1, rm = 0;
                for (int j = 1; j < len - k + 1; j++)
                {
                    if (k - j < 0)
                    {
                        rm = 1;
                        break;
                    }
                    if (s[k - j] == s[k + j - 1])
                    {
                        f = 0;
                        break;
                    }
                }
                if (!f)
                    continue;
                int clen = 0;
                if (rm)
                {
                    for (int j = len - 1; j >= k; j--)
                        t[clen++] = (s[j] == '0')? '1' : '0';
                }
                else
                {
                    for (int j = 0; j < k; j++)
                        t[clen++] = s[j];
                }
                t[clen] = 0;
//                puts(t);
                insert(t, now, 1);
            }
            if (now == id)
                id++;
        }
        getfail();
        dp[0][0][0] = 1;
        int cur = 0;
//        dbg(ch[5][1]);
        for (int i = 1; i <= L; i++)
        {
            cur ^= 1;
            memset(dp[cur], 0, sizeof(dp[cur]));
            for (int u = 0; u <= sz; u++)
                for (int k = 0; k < (1 << id); k++)
                {
                    if (dp[cur ^ 1][k][u] == 0)
                        continue;
                    for (int c = 0; c <= 1; c++)
                    {
//                        dbg(i, u, k, c);
                        int v = ch[u][c];
                        int nxt_s = k | ed[v];
                        if (i == L)
                            nxt_s = nxt_s | ed2[v];
//                        dbg(nxt_s);
                        dp[cur][nxt_s][v] += dp[cur ^ 1][k][u];
                        dp[cur][nxt_s][v] %= mod;
                    }
                }
        }
        ll ans = 0;
//        puts("over1");
        for (int i = 0; i <= sz; i++)
            ans = (ans + dp[cur][(1 << id) - 1][i]) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}