HDU 6086 Rikka with String（AC自动机+状压DP+滚动数组优化+思维）

Rikka with String

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 656 Accepted Submission(s): 236

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

题目链接：HDU 6086
这题如果不用对称，只要构造长度为$n$的字符串使得包含所有给定的字符串那就是简单的状压一下就好了，但是这里要求左右相反，看了大佬们的题解，发现其实还是将这些串“对折到”左半边长度为$L$的地方，然后再根据上面的状压+AC自动机就可以求了，考虑一个子串的出现位置：

1. 完全在左边，显然就是直接插入自动机
2. 完全在右边，显然就是按照题意得到此串在左边的形态，再插入AC自动机
3. 有$lenl$在左边，有$lenr$在右边，其中$lenl+lenr=len$，那么其实右边有$lenl$的部分是已知的，可以不用管，剩下的未知的就是$2*lenl+1…len$的位置，根据题意这段显然也是可以翻转到左边去得到其在左边的形态后跟$lenl$部分拼接，再插入AC自动机，这里的状态要记录为另一种新的状态，只能在处理长度为$L$的时候才可以用到。

然后建立AC自动机，做一下状压DP就好了，
代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 130;
namespace ac {
    struct Trie
    {
        int nxt[2], fail, st[2];
        void init()
        {
            nxt[0] = nxt[1] = -1;
            st[0] = st[1] = fail = 0;
        }
    } L[N * 3];
    int sz;
    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    inline int newnode()
    {
        L[sz].init();
        return sz++;
    }
    void ins(char s[], int len, int id, int index)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - '0';
            if (L[u].nxt[v] == -1)
                L[u].nxt[v] = newnode();
            u = L[u].nxt[v];
        }
        L[u].st[index] |= (1 << id);
    }
    void build()
    {
        L[0].fail = 0;
        queue<int>Q;
        for (int i = 0; i < 2; ++i)
        {
            int &v = L[0].nxt[i];
            if (~v)
            {
                Q.push(v);
                L[v].fail = 0;
            }
            else
                v = 0;
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            L[u].st[0] |= L[uf].st[0];
            L[u].st[1] |= L[uf].st[1];
            for (int i = 0; i < 2; ++i)
            {
                int &v = L[u].nxt[i];
                if (~v)
                {
                    Q.push(v);
                    L[v].fail = L[uf].nxt[i];
                }
                else
                    v = L[uf].nxt[i];
            }
        }
    }
}
char s[N], rs[N];
int dp[2][N * 3][1 << 6];
const int mod = 998244353;

int main(void)
{
    int TC, n, L, i, j, k;
    scanf("%d", &TC);
    while (TC--)
    {
        ac::init();
        CLR(dp, 0);
        scanf("%d%d", &n, &L);
        for (i = 0; i < n; ++i)
        {
            scanf("%s", s);
            int len = strlen(s);
            ac::ins(s, len, i, 0);//左半边
            for (j = 0; j < len; ++j)
                rs[j] = s[len - 1 - j] == '1' ? '0' : '1';
            ac::ins(rs, len, i, 0);//右半边等价映射到左半边
            for (j = 0; j < len - 1; ++j) //把超出中线的右半部分也等价映射到左半边
            {
                int lenl = j + 1, lenr = len - lenl;
                int canmap = 1;
                for (k = 0; k < min(lenl, lenr); ++k)
                {
                    if (s[j - k] == s[j + 1 + k])
                    {
                        canmap = 0;
                        break;
                    }
                }
                if (canmap)
                {
                    string str = string(s, 0, lenl);
                    for (k = 2 * lenl; k < len; ++k)
                        str = (s[k] == '1' ? '0' : '1') + str;
                    strcpy(rs, str.c_str());
                    ac::ins(rs, str.size(), i, 1);
                }
            }
        }
        ac::build();
        int now = 0, nxt = 1;
        int R = 1 << n;
        dp[0][0][0] = 1;
        for (i = 0; i < L; ++i)
        {
            CLR(dp[nxt], 0);
            for (j = 0; j < ac::sz; ++j)
            {
                for (k = 0; k < R; ++k)
                {
                    if (dp[now][j][k])
                    {
                        for (int s = 0; s < 2; ++s)
                        {
                            int v = ac::L[j].nxt[s];
                            int vst = k | ac::L[v].st[0];
                            if (i == L - 1)
                                vst |= ac::L[v].st[1];
                            dp[nxt][v][vst] = (dp[nxt][v][vst] + dp[now][j][k]) % mod;
                        }
                    }
                }
            }
            swap(now, nxt);
        }
        int ans = 0;
        for (i = 0; i < ac::sz; ++i)
            ans = (ans + dp[now][i][R - 1]) % mod;
        printf("%d\n", ans);
    }
    return 0;
}