沉迷AC自动机无法自拔之：[UVALive 4126] Password Suspects

图片加载可能有点慢，请跳过题面先看题解，谢谢

一看到这么多模式串就非常兴奋，又是$AC$自动机
题目就是要求：经过 $n$ 个节点，把所有单词都遍历一遍的方案数，和那道题差不多嘛
所以这样设：$f[i][j][k]$ 为，走了 $i$ 个节点，当前点在 $j$，单词的经过情况为 $k$（一个二进制数）时的方案数
答案很显然是：$\sum_{i=1}^{size}f[n][i][(1<<m)-1]$
转移也很显然：$f[i+1][Son][s|val[Son]]+=f[i][j][s]$
$
$
但是这道题有点麻烦的就是，它需要输出方案，上面那样子做不太好记录路径
这里考虑反过来搞，这样转移：$f[i][j][s]+=f[i+1][Son][s|val[Son]]$，答案就变成了$f[0][0][0]$
这样做的话，就可以保证只有在有效路径上，$f$ 值才不为$0$，那么方案就很好办了
$
$

//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#define ll long long
using namespace std;

int t,n,m;

struct Trie{
   char o[26];
   int root,size;
   ll f[26][110][1<<10];
   int son[110][30],fail[110],val[110];

   void init(){
      size=1; root=0;
      memset(son,0,sizeof(son));
      memset(val,0,sizeof(val));
      memset(fail,0,sizeof(fail));
      memset(f[n],0,sizeof(f[n]));
   }

   int idx(char c){ return c-'a'; }

   void insert(char* s,int v){
      int cur=root;
      for(int i=0;s[i];i++){
         int id=idx(s[i]);
         if(!son[cur][id]) son[cur][id]=size++;
         cur=son[cur][id];
      }
      val[cur]|=1<<v; return ;
   }

   void build(){
      int que[110];
      int hd=0,tl=0;
      for(int i=0;i<26;i++)
         if(son[root][i]){
            fail[son[root][i]]=root;
            que[tl++]=son[root][i];
         }
         else son[root][i]=root;

      while(hd<tl){
         int cur=que[hd++];
         for(int i=0;i<26;i++){
            int Son=son[cur][i];
            if(Son){
               int f=fail[cur];
               while(f && !son[f][i]) f=fail[f];
               fail[Son]=son[f][i];
               val[Son]|=val[fail[Son]];
               que[tl++]=Son;
            }
            else son[cur][i]=son[fail[cur]][i];
         }
      }
   }

   ll dp(){
      for(int i=0;i<size;i++) f[n][i][(1<<m)-1]=1;
      for(int i=n-1;i>=0;i--)
         for(int j=0;j<size;j++)
            for(int s=0;s<(1<<m);s++){
               f[i][j][s]=0;
               for(int k=0;k<26;k++){
                  int Son=son[j][k];
                  int ss=s|val[Son];
                  f[i][j][s]+=f[i+1][Son][ss];
               }
            }
      return f[0][0][0];
   }

   void print(int i,int j,int s){
      if(i==n){
         for(int k=0;k<n;k++) printf("%c",o[k]);
         puts("");
         return ;
      }
      for(int k=0;k<26;k++){
         int Son=son[j][k];
         int ss=s|val[Son];
         if(f[i+1][Son][ss]){
            o[i]=k+'a';
            print(i+1,Son,ss);
         }
      }
   }

}AC;

set<string>map;

void init(){
   AC.init(),map.clear();
   int cnt=0;
   for(int i=0;i<m;i++){
      char s[15];
      scanf("%s",s);
      string S=s;
      if(!map.count(S)){
         AC.insert(s,cnt++);
         map.insert(S);
      }
   }
   m=cnt;
}

void work(){
   AC.build();
   ll ans=AC.dp();
   printf("Case %d: %lld suspects\n",++t,ans);
   if(ans<=42) AC.print(0,0,0);
}

int main(){ while(scanf("%d%d",&n,&m)&&n){ init(); work(); } return 0; }

巴特西

沉迷AC自动机无法自拔之：[UVALive 4126] Password Suspects

最新文章

热门文章