思路与算法

记R(s)为逆序并逐位取反。任意长度2m的反对称串唯一写成H+R(H)，其中H长m。一个要求串P完全位于任一半，等价于H中出现P或R(P)；把这两个串都插入AC自动机，并将终点标记同一个要求位。跨中点出现时，设P左侧有k个字符，则H后缀必须同时等于U=P[0:k]和V=R(P[k:])。若较短者不是较长者的后缀则不可能；否则只要求H以较长者结尾，且k、|P|-k均不超过m。这个较长串一定是P或R(P)的前缀，所以它已经是Trie结点，不新增状态，在该结点标记crossMask。AC的inMask与crossMask分别沿fail传播。DP逐位生成H，状态为当前AC结点及曾在H内部匹配到的要求掩码，只把inMask加入历史掩码。生成m位后才把最终结点的crossMask并入，判断是否满足全部要求。

正确性说明

反对称性确定右半，故枚举所有H恰好枚举所有目标串。完全位于右半的P经逆补码映回左半成为R(P)，与左半内P都被AC终点标记精确识别。跨中点的P对应唯一分割k，左右两段转换后都是H的后缀条件；两个后缀可同时存在当且仅当短者为长者的后缀，因此所标crossMask条件等价且没有遗漏。AC状态的fail链恰好表示当前H全部可用前缀后缀，传播crossMask便能判断跨中点条件。DP的历史掩码只累计半内出现，不能提前累计跨界条件；最终再加入crossMask正好涵盖三类位置。每个H只有一条二进制生成路径，掩码合并不会重复计数。

复杂度

令L为最大要求串长、V为Trie结点数，V<=2nL+1<=1201。插入与AC初始化O(nL+V)，枚举跨界分割并比较字符串O(nL²)。滚动DP时间O(mV2^n)，初始化O(V2^n)，空间O(V2^n+nL)。全部运算模998244353，两个已取模值相加不超过int32上限。

易错点

跨中点条件只在生成完整左半后判断，不能像普通匹配一样永久累计。P和R(P)标记同一要求位，重复要求仍须把对应位都标上。超过总长2m的模式必不可能出现；跨界两段也各不能超过m。两个中点字符互补，不能假设跨中点能产生连续同字符段。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
string rc(string s) {
    reverse(s.begin(), s.end());
    for (char &c : s)
        c ^= 1;
    return s;
}
struct Node {
    int to[2], fail, in, cross;
    Node() : to{0, 0}, fail(0), in(0), cross(0) {
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    vector<Node> a(1);
    auto insert = [&](const string &s, int mask) {
        int u = 0;
        for (char c : s) {
            int d = c - '0';
            if (!a[u].to[d]) {
                a[u].to[d] = a.size();
                a.emplace_back();
            }
            u = a[u].to[d];
        }
        a[u].in |= mask;
    };
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        insert(s[i], 1 << i);
        insert(rc(s[i]), 1 << i);
    }
    for (int i = 0; i < n; i++)
        for (int k = 1; k < (int)s[i].size(); k++) {
            if (k > m || (int)s[i].size() - k > m)
                continue;
            string u = s[i].substr(0, k), v = rc(s[i].substr(k));
            if (u.size() < v.size())
                swap(u, v);
            if (u.compare(u.size() - v.size(), v.size(), v))
                continue;
            int q = 0;
            for (char c : u)
                q = a[q].to[c - '0'];
            a[q].cross |= 1 << i;
        }
    vector<int> q;
    for (int c = 0; c < 2; c++)
        if (a[0].to[c])
            q.push_back(a[0].to[c]);
    for (size_t j = 0; j < q.size(); j++) {
        int u = q[j], f = a[u].fail;
        a[u].in |= a[f].in;
        a[u].cross |= a[f].cross;
        for (int c = 0; c < 2; c++) {
            int v = a[u].to[c];
            if (v) {
                a[v].fail = a[f].to[c];
                q.push_back(v);
            } else
                a[u].to[c] = a[f].to[c];
        }
    }
    int V = a.size(), M = 1 << n;
    vector<int> dp(V * M), ndp(V * M);
    dp[0] = 1;
    for (int j = 0; j < m; j++) {
        fill(ndp.begin(), ndp.end(), 0);
        for (int u = 0; u < V; u++)
            for (int mask = 0; mask < M; mask++)
                if (dp[u * M + mask])
                    for (int c = 0; c < 2; c++) {
                        int v = a[u].to[c], z = v * M + (mask | a[v].in);
                        ndp[z] += dp[u * M + mask];
                        if (ndp[z] >= MOD)
                            ndp[z] -= MOD;
                    }
        dp.swap(ndp);
    }
    int ans = 0;
    for (int u = 0; u < V; u++)
        for (int mask = 0; mask < M; mask++)
            if ((mask | a[u].cross) == M - 1) {
                ans += dp[u * M + mask];
                if (ans >= MOD)
                    ans -= MOD;
            }
    cout << ans << '\n';
}