POJ1625 DP+AC自动机+大数加法
发布时间:2020-12-14 02:26:42 所属栏目:大数据 来源:网络整理
导读:题目描述:给n个可用字母,组成长为m的串s,其中有w个子串t是不能在这些串s中出现的,请问这样的串s有多少种? 思路:先建立一个ac自动机,并且标记每个w的结束节点end=1,同时把fail指向end=1的点的end也改写为1。现在要计算从root走m步(不能经过end=1的点
题目描述:给n个可用字母,组成长为m的串s,其中有w个子串t是不能在这些串s中出现的,请问这样的串s有多少种? //POJ 1625 关键代码段
void build(){
queue <int> Q;
fail[root] = root;
for(int i = 0;i < n;i++)
if(nxt[root][i] == -1)
nxt[root][i] = root;
else{
fail[nxt[root][i]] = root;
Q.push(nxt[root][i]);
}
while(!Q.empty()){
int now = Q.front(); Q.pop();
for(int i = 0;i < n;i++){
if(nxt[now][i] == -1)
nxt[now][i] = nxt[fail[now]][i];
else{
fail[nxt[now][i]] = nxt[fail[now]][i];
end[nxt[now][i]] |= end[nxt[fail[now]][i]];//end的重标
Q.push(nxt[now][i]);
}
}
}
}
void solve(int step)
{
memset(dp,0,sizeof(dp));
dp[0][0][0] = 1; //大数一定会爆,用数组模拟
for(int k = 1;k <= step;k++){ //注意了,一定是把步数放在最外面统计
for(int i = 0;i < L;i++){
if(end[i]) continue; //end是不能实现字段的结束标识,不可到达
for(int j = 0;j < n;j++){
int thi = nxt[i][j];
if(end[thi]) continue;
ADD(dp[k][thi],dp[k-1][i]);
}
}
}
for(int i = 1;i < L;i++){ //这里是把所有结点上的可能加起来,不要重复加结点0
if(end[i]) continue;
ADD(dp[step][0],dp[step][i]);
}
pin(dp[step][0]);
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |