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
Source
2017 Multi-University Training Contest - Team 5
多校还是有收获的，又学到了新姿势，ac自动机+dp的一类题
题意：给出m个单词，要构造出长度为2*L的包含这全部m个单词的字符串，并且保证这个字符串非对称，其中字符只包括0和1，问一共有多少种构造方法。
思路：看了很多博客，先做了个简单版的hdu2825（建议先做一下），2825没有非对称这个条件，由于有非对称这个条件，所以我们只需要构造前一半长度为L的字符串就确定了整个串，字符串在构造的串种可能出现的位置有三种
1.出现在字符串的前一半
2出现在字符串的后一半
3.一半在前边，一半在后边
前两种情况都比较好处理，
1.把给的字符串插入到ac自动机
2.把给的字符串的反串插入到ac自动机（在字符串的后一半出现，那么其反串就会出现在前边）
比较困难的是第三种情况，我们把字符串分成两部分，但是由于必须还得是非对称串，所以前后部分是对称的要去掉，还有一点就是两边长度不一定相同，我们必须要把长度短的补长，例如：
10101
10 101，当这样分配是我们不能直接将10插入到ac自动机，我们要将10补齐为100插入到ac自动机
这个题还有一点就是卡空间，题解中给出的解决方法是将L%2，因为dp过程中前边计算过的对后边没什么用了
ac代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXNODE = 2500;
const int SIGMA_SIZE = 2;
const LL MOD = 998244353;
struct ACauto {
int next[MAXNODE][SIGMA_SIZE], fail[MAXNODE], end1[MAXNODE], end2[MAXNODE];
int root,sz;
int newnode() {
for (int i = 0; i < SIGMA_SIZE; i++)
next[sz][i] = -1;
end1[sz] = 0;
end2[sz++] = 0;
return sz - 1;
}
void init() {
sz = 0;
root = newnode();
}
void insert1(char *buf, int id) {
int len = strlen(buf);
int now = root;
for (int i = 0; i < len; i++) {
if (next[now][buf[i] - '0'] == -1)
next[now][buf[i] - '0'] = newnode();
now = next[now][buf[i] - '0'];
}
end1[now] |= (1 << id);
}
void insert2(char *buf, int id) {
int len = strlen(buf);
int now = root;
for (int i = 0; i < len; i++) {
if (next[now][buf[i] - '0'] == -1)
next[now][buf[i] - '0'] = newnode();
now = next[now][buf[i] - '0'];
}
end2[now] |= (1 << id);
}
void build() {
queue <int> Q;
fail[root] = root;
for (int i = 0; i < SIGMA_SIZE; i++) {
if (next[root][i] == -1)
next[root][i] = root;
else {
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
}
while (!Q.empty()) {
int now = Q.front();
Q.pop();
end1[now] |= end1[fail[now]];
end2[now] |= end2[fail[now]];
for (int i = 0; i < SIGMA_SIZE; i++) {
if (next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else {
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
} ac;
int n, L;
char s[30], t[30], str[60];
LL dp[2][2500][(1 << 6) + 10];
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &L);
ac.init();
for (int i = 0; i < n; i++) {
scanf("%s", s);
ac.insert1(s, i);
int len = strlen(s);
for (int j = 0; j < len; j++)
t[j] = s[len - 1 - j] == '0' ? '1' : '0';
t[len] = '\0';
ac.insert1(t, i);
for (int j = 0; j < len - 1; j++) {
string s1 = "", s2 = "";
for (int k = j; k >= 0; k--) s1 += s[k];
for (int k = j + 1; k < len; k++) s2 += s[k];
bool flag = true;
for (int k = 0; k < (int)s1.length() && k < (int)s2.length(); k++) {
if (s1[k] == s2[k]) {
flag = false;
break;
}
}
if (!flag) continue;
reverse(s1.begin(), s1.end());
for (int k = (j + 1) * 2; k < len; k++) {
s1 = (s[k] == '0' ? '1' : '0') + s1;
}
strcpy(str, s1.c_str());
ac.insert2(str, i);
}
}
ac.build();
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for (int i = 0; i < L; i++) {
for (int j = 0; j < ac.sz; j++) {
for (int S = 0; S < (1 << n); S++) {
if (dp[i%2][j][S] <= 0) continue;
for (int k = 0; k < SIGMA_SIZE; k++) {
int ni = i + 1, nj = ac.next[j][k], nS = S | ac.end1[nj];
if (i == L - 1) nS |= ac.end2[nj];
dp[ni%2][nj][nS] = (dp[ni%2][nj][nS] + dp[i%2][j][S]) % MOD;
}
dp[i%2][j][S] = 0;
}
}
}
LL ans = 0;
for (int i = 0; i < ac.sz; i++) {
ans = (ans + dp[L%2][i][(1 << n) - 1]) % MOD;
}
printf("%I64d\n", ans);
}
return 0;
}
