链接
https://cn.vjudge.net/problem/UVA-1076
题解
这是一道world final题 方案数就直接AC自动机上状压dp，
f
i
j
k
f_{ijk}
fijk表示长度为
i
i
i，当前走到了第
j
j
j个结点，每个串有没有包含为
k
k
k(二进制状压)的方案数 输出方案比较蛋疼，我是记录了每个方案是由哪个方案转移过来的，最后一遍
d
f
s
dfs
dfs，各种
s
t
l
stl
stl瞎搞就出来了（说起来容易，做起来还是很考验代码能力的）
联想
其实吧，所谓
A
C
AC
AC自动机上的状压
d
p
dp
dp，听起来很长，好像挺
6
6
6一样，但其实
A
C
AC
AC自动机只是提供了一个偏序关系(把串的长度考虑进去)，定义了一种转移顺序，去掉
A
C
AC
AC自动机的话，这题就只是个状压
d
p
dp
dp入门级题目 还有一种题目是算期望或者算概率的，那种题的串可能会达到无限长，但是
A
C
AC
AC自动机在其中起的作用还是定义“如何转移”，最后用一个高斯消元算一算就完了。 所以说其实
A
C
AC
AC自动机只是一种工具，说到底这些"AC自动机上的xxx"题目，就还是一些普通算法题套到数据结构上去罢了。
代码
#include <bits/stdc++.h>
#define maxn 110
#define cl(x) memset(x,0,sizeof(x))
using namespace std
;
typedef long long ll
;
ll f
[30][maxn
][2019];
vector
<int> num
[maxn
];
vector
< vector
<int> > g
[30][maxn
][2019];
struct ACautomaton
{
int trie
[maxn
][30], tot
, fail
[maxn
], tail
[maxn
];
void init()
{
memset(trie
,0,sizeof(trie
));
memset(fail
,0,sizeof(fail
));
memset(tail
,0,sizeof(tail
));
tot
=1;
}
int insert(int *r
, int len
)
{
auto pos
=1;
for(auto i
=1;i
<=len
;i
++)
pos
= trie
[pos
][r
[i
]] ? trie
[pos
][r
[i
]] : trie
[pos
][r
[i
]]=++tot
;
tail
[pos
]++;
return pos
;
}
void build()
{
queue
<int> q
;
int u
, v
, f
;
q
.push(1);
while(!q
.empty())
{
u
=q
.front(); q
.pop();
for(auto i
=1;i
<=26;i
++)
if(trie
[u
][i
])
{
v
=trie
[u
][i
];
for(f
=fail
[u
];f
and !trie
[f
][i
];f
=fail
[f
]);
fail
[v
] = f
? trie
[f
][i
] : 1;
tail
[v
]+=tail
[fail
[v
]];
q
.push(v
);
}
}
}
int move(int pos
, int c
)
{
for(;pos
and !trie
[pos
][c
];pos
=fail
[pos
]);
return pos
? trie
[pos
][c
] : 1;
}
}aca
;
void dfs(int i
, int j
, int k
, vector
<string
>& lis
, string now
)
{
if(i
==0)
{
lis
.emplace_back(now
);
return;
}
for(auto v
:g
[i
][j
][k
])
{
char t
[2];
t
[0]=char(v
[2]+'a'-1);
t
[1]='\0';
dfs(i
-1,v
[0],v
[1],lis
,string(t
)+now
);
}
}
int main()
{
int n
, m
, i
, j
, k
, alpha
, kase(0), r
[maxn
];
char s
[maxn
];
while(scanf("%d%d",&n
,&m
), (n
or m
))
{
aca
.init();
for(i
=0;i
<maxn
;i
++)num
[i
].clear();
for(i
=1;i
<=m
;i
++)
{
scanf("%s",s
+1);
auto len
=strlen(s
+1);
for(auto i
=1;i
<=len
;i
++)r
[i
]=s
[i
]-'a'+1;
auto pos
= aca
.insert(r
,len
);
num
[pos
].emplace_back(i
);
}
aca
.build();
cl(f
);
f
[0][1][0]=1;
for(i
=0;i
<=n
;i
++)for(j
=1;j
<=aca
.tot
;j
++)for(k
=0;k
<(1<<m
);k
++)g
[i
][j
][k
].clear();
for(i
=0;i
<n
;i
++)
{
for(j
=1;j
<=aca
.tot
;j
++)
{
for(k
=0;k
<(1<<m
);k
++)
{
if(f
[i
][j
][k
]==0)continue;
for(alpha
=1;alpha
<=26;alpha
++)
{
auto to
= aca
.move(j
,alpha
), sta(k
);
for(auto pos
=to
;pos
>1;pos
=aca
.fail
[pos
])
{
for(auto x
: num
[pos
])sta
|= 1<<(x
-1);
}
f
[i
+1][to
][sta
] += f
[i
][j
][k
];
if(f
[i
][j
][k
]<=42)g
[i
+1][to
][sta
].emplace_back( vector
<int>{j
,k
,alpha
} );
}
}
}
}
ll
ans(0ll);
for(i
=1;i
<=aca
.tot
;i
++)
{
ans
+= f
[n
][i
][(1<<m
)-1];
}
printf("Case %d: %lld suspects\n",++kase
,ans
);
if(ans
<=42)
{
vector
<string
> lis
;
for(i
=1;i
<=aca
.tot
;i
++)
dfs(n
,i
,(1<<m
)-1,lis
,"");
sort(lis
.begin(),lis
.end());
for(auto s
:lis
)cout
<<s
<<endl
;
}
}
return 0;
}
