【bzoj5451】字符串

Source

bzoj5451

Hint

请先思考后再展开

把每个串和其逆反串塞到ac自动机里面,就可以跑一个 $O(m2^n|S|)$ 的dp

Solution

请先思考后再展开

想到这东西后很自闭,不知道怎么处理在中间的情况
假设这个串,左边部分为a,右边为b
$a<b,那么逆反串长为b的前缀即可$
$a>b,那么当前串长为a的前缀即可$
于是我们可以给节点子树打上一个d标记,最后统计答案的时候判断 $d_x&S=2^n-1$
时间复杂度不变

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(ll &x,const int y) {x=x<y?x:y;}
const int MAX_N=6e2+10;
const ll MOD=998244353;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
int bin[30],n,m,ans=0;
char str[MAX_N];int ln;bool okay[2][MAX_N];
struct ACM
{
struct Nod{int son[2],fail,d,tg;}p[MAX_N*2];int id;
int f[2][MAX_N*2][1<<7];
ACM(){memset(p,0,sizeof p);memset(f,0,sizeof f);id=1;}
void insert(int nowid,int op)
{
int x=1;
for(int i=1;i<=ln;i++)
{
int to=str[i]-'0';
if(!p[x].son[to]) p[x].son[to]=++id;
x=p[x].son[to];p[x].d|=bin[nowid-1]*okay[op][i];
}
p[x].tg|=bin[nowid-1];
}
queue<int> q;
void solve()
{
q.push(1);p[1].fail=0;
while(q.size())
{
int x=q.front();q.pop();
for(int t=0;t<=1;t++)
{
int y=p[x].son[t];if(!y) continue;q.push(y);
int tmp=p[x].fail;while(tmp and !p[tmp].son[t]) tmp=p[tmp].fail;
p[y].fail=p[tmp].son[t];if(p[y].fail==0) p[y].fail=1;
if(p[y].fail==y) puts("error");
p[y].tg|=p[p[y].fail].tg;p[y].d|=p[p[y].fail].d;
}
}
f[0][1][0]=1;
for(int i=0,now=1;i<m;i++,now^=1)
{
memset(f[now],0,sizeof f[now]);
for(int x=1;x<=id;x++) for(int S=0;S<bin[n];S++) for(int t=0;t<=1;t++)
{
int tmp=x;while(tmp and !p[tmp].son[t]) tmp=p[tmp].fail;int y=p[tmp].son[t];y=max(y,1);
add(f[now][y][S|p[y].tg],f[now^1][x][S]);
}
}
for(int x=1;x<=id;x++) for(int S=0;S<bin[n];S++) if((S|p[x].d)==bin[n]-1) add(ans,f[m&1][x][S]);
}
}acm;
bool check(int l,int r)
{
for(;l<=r;l++,r--) if(str[l]==str[r]) return 0;
return 1;
}
void main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
n=qread(),m=qread();
for(int i=1;i<=n;i++)
{
scanf("%s",str+1),ln=strlen(str+1);
memset(okay,0,sizeof okay);for(int j=1;j<=ln-j;j++) okay[0][ln-j]=check(ln-2*j+1,ln),okay[1][ln-j]=check(1,2*j);
acm.insert(i,0);reverse(str+1,str+ln+1);for(int j=1;j<=ln;j++) str[j]=(str[j]=='0'?'1':'0');acm.insert(i,1);
}
acm.solve();write(ans);
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/58a4.html
转载请注明出处,谢谢!