「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自动机上的结束位置上有该标记，则可以认为此串也经过过。

---

代码

#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;
}