Wireless Password HDU - 2825(AC自动机+状压dp 卡常)
程序员文章站
2022-06-18 14:02:46
题目链接题意:给你M个word串,问你能构造多少种长度为N的字符串,满足至少包含K个不同的word串。 1<=N<=25 1<=M<=10 1<=K<=10思路:首先想到,建AC自动机,并且给每个插入的word串一个状态,1<
题意:给你M个word串,问你能构造多少种长度为N的字符串,满足至少包含K个不同的word串。 1<=N<=25 1<=M<=10 1<=K<=10
思路:首先想到,建AC自动机,并且给每个插入的word串一个状态,1<<x x为插入的序号,即:isstr[1<<x] 就是第x个word串对应的二进制状态。(1 10 100 1000… )
建好AC自动机后就是一个状态压缩dp的题,
dp[i][j][k]表示目前走了i步,到达j号节点,且此时M个word串的状态为k的最大方案数。 状态转移方程:
dp[i][j][k]=Σdp[i-1][father][last]
father是j的父亲节点,last对应转移前的状态
dp[0][0][0]=1;//初始化
for(int i=0;i<N;i++)//用i步的状态更新i+1步的状态
{
for(int j=0;j<=tot;j++)
{
for(int k=0;k<(1<<M);k++)
{
if(dp[i][j][k])//不加这个判断会t,卡常点
{
for(int id=0;id<26;id++)
{
int u=tree[j][id];//得到孩子节点u
int temp=k | isstr[u];//temp表示转移到u时候的各word的访问状态,k|isstr[u] 得到的就是u继承了k这个状态之后的状态
dp[i+1][u][temp]=(dp[i+1][u][temp]+dp[i][j][k])%20090717;
}
}
}
}
}
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<math.h>
#include<set>
using namespace std;
#define INF 0x3f3f3f
#define LL unsigned long long
const int maxn=1e2+20;
int tree[maxn][26];//字典树
int isstr[110];//以i节点结尾的单词对应的状态
int tot;//节点总数
int fail[maxn];
int M,N,K;
char s1[15];
int num[1<<10];//预处理每个状态有几个单词 也就是二进制下有几个1,最终要大于等于K的状态才有效
LL dp[30][110][1<<10];//dp[i][j][k]:走到第i步 到达j节点 状态为k的二进制时 方案数
//dp[0][0][0]=1
void Init()
{
memset(tree,0,sizeof(tree));
memset(isstr,0,sizeof(isstr));
tot=0;
memset(fail,0,sizeof(fail));
}
void getnum()
{
for(int i=0; i<(1 << 10);i++)
{
int tmp=i;
while(tmp)
{
if(tmp & 1) num[i]++;
tmp>>=1;
}
}
}
void Insert(char *s,int x)
{
int len=strlen(s),root=0;
for(int i=0;i<len;i++)
{
int id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;
root=tree[root][id];
}
isstr[root]=1<<x;//每个字符串的压缩状态,建好AC自动机之后就使其转化成了这个点的状态,因为我们是从根节点出发,根节点到这个点的路径是唯一的,且路径就是对应的字符串
}
void getfail()
{
queue<int> q;
for(int i=0;i<26;i++)
{
if(tree[0][i])
{
q.push(tree[0][i]);
//fail[tree[0][i]]=0;
}
//else tree[0][i]=0
}
while(!q.empty())
{
int v=q.front();
q.pop();
//if(isstr[fail[v]]) isstr[v]=isstr[fail[v]]; wa点 可能这两个都是单词结尾 比如出现ABC,BC 两个状态要取并集
isstr[v]|=isstr[fail[v]];//状态合并,某个是0也不影响
for(int i=0;i<26;i++)
{
if(tree[v][i])
{
fail[tree[v][i]]=tree[fail[v]][i];
q.push(tree[v][i]);
}
else tree[v][i]=tree[fail[v]][i];
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
getnum();
while(~scanf("%d%d%d",&N,&M,&K) ){
if(!N && !M && !K) break;
Init();
for(int i=1;i<=M;i++)
{
scanf("%s",s1);
Insert(s1,i-1);
}
getfail();
for(int i=0;i<=N;i++)
{
for(int j=0;j<=tot;j++)
{
for(int k=0;k<(1<<M);k++) dp[i][j][k]=0;
}
}
dp[0][0][0]=1;
for(int i=0;i<N;i++)
{
for(int j=0;j<=tot;j++)
{
for(int k=0;k<(1<<M);k++)
{
if(dp[i][j][k])
{
for(int id=0;id<26;id++)
{
int u=tree[j][id];
int temp=k | isstr[u];//转移到u时候的状态
dp[i+1][u][temp]=(dp[i+1][u][temp]+dp[i][j][k])%20090717;
}
}
}
}
}
int sum=0;
for(int i=0;i<(1<<M);i++)
{
if(num[i]>=K)
{
for(int id=0;id<=tot;id++) sum=(sum+dp[N][id][i])%20090717;
}
}
printf("%d\n",sum%20090717);
}
system("pause");
return 0;
}
本文地址:https://blog.csdn.net/qq_46030630/article/details/108138372