隐藏
「2017-08-14 四校联考」字符串 - AC自动机+状压动规 | Bill Yang's Blog
0%

「2017-08-14 四校联考」字符串 - AC自动机+状压动规

题目大意

    给定正整数$m$以及$n$个$01$串$s_1\sim s_n$,你需要求出长度为$2m$的反对称的包含这$n$个$01$串作为子串的$01$串的个数。对$998244353$取模。
    一个$01$串$s$是反对称的当且仅当它对于$1\le i\le\left|s\right|$都满足$s[i]\neq s[\left|s\right|-i+1]$。


题目分析

考虑,一个$01$串只可能出现在以下四种位置:

  1. 全部出现在$1\sim m$
  2. 大半部分出现在$1\sim m$,小半部分出现在$m+1\sim 2m$
  3. 小半部分出现在$1\sim m$,大半部分出现在$m+1\sim 2m$
  4. 全部出现在$1\sim m$

将每个串及其反对称串插入到AC自动机中,那么$3,4$情况便变为了$1,2$情况。
用压缩状态$s$表示每个$01$串是否被经过。
第一种情况的经过就很简单了,AC自动机上DP一下即可。
如图,注意第二种情况只可能出现在末尾位置,且对合法性不造成影响:

标记记录一下反对称的对称轴,表示可以在此处停止,然后沿着AC自动机fail链向上传递标记。
若AC自动机上的结束位置上有该标记,则可以认为此串也经过过。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=200005,mod=998244353;

struct Aho_Corasick_Automaton {
struct Tree {
int child[26];
int fail,flag,flag2;
} tree[maxn];
int cnt;
#define ch(x,i) tree[x].child[i]
#define fail(x) tree[x].fail
int newnode() {return ++cnt;}
bool check(string s,int pos) {
for(int i=pos+1; i<s.length(); i++)if(pos-(i-pos)+1<0||s[pos-(i-pos)+1]==s[i])return 0;
return 1;
}
void insert(string s,int flag) {
int now=0;
for(int i=0; i<s.length(); i++) {
int j=s[i]-'0';
if(!ch(now,j))ch(now,j)=newnode();
now=ch(now,j);
if(check(s,i))tree[now].flag2|=flag;
}
tree[now].flag|=flag;
}
void buildfail() {
queue<int> Q;
Q.push(0);
while(!Q.empty()) {
int now=Q.front();
Q.pop();
for(int i=0; i<26; i++) {
int &next=ch(now,i);
if(next) {
if(now)fail(next)=ch(fail(now),i);
tree[next].flag|=tree[fail(next)].flag;
tree[next].flag2|=tree[fail(next)].flag2;
Q.push(next);
} else next=ch(fail(now),i);
}
}
}
} acam;

int n,m,f[505][1205][1<<6];
char s[105];

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
scanf("%s",s);
acam.insert(s,1<<(i-1));
int len=strlen(s);
reverse(s,s+len);
for(int j=0; j<len; j++)s[j]=s[j]=='0'?'1':'0';
acam.insert(s,1<<(i-1));
}
acam.buildfail();
f[0][0][0]=1;
for(int i=1; i<=m; i++)
for(int j=0; j<=acam.cnt; j++)
for(int S=0; S<(1<<n); S++)
for(int k=0; k<=1; k++) {
int next=acam.tree[j].child[k],T=S|acam.tree[next].flag;
f[i][next][T]=(f[i][next][T]+f[i-1][j][S])%mod;
}
int ans=0;
for(int i=0; i<=acam.cnt; i++)
for(int S=0; S<(1<<n); S++)
if((S|acam.tree[i].flag2)==(1<<n)-1)ans=(ans+f[m][i][S])%mod;
printf("%d\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~