HDU - 2825（AC自动机+状态压缩DP（需要优化））-白红宇

HDU - 2825（AC自动机+状态压缩DP（需要优化））

阅读量：5133 次

发布时间：2019-06-13

本文共 1585 字，大约阅读时间需要 5 分钟。

求一个串至少包含k个给定的串的方案数（k个串可相互覆盖-所以只能用AC自动机了）

状态压缩使每个串唯一（1<<i第i个串），防止重复加！（WA）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #define tree int o,int l,int r#define lson o<<1,l,mid#define rson o<<1|1,mid+1,r#define lo o<<1#define ro o<<1|1#define pb push_back#define mp make_pair#define inf 0x7fffffff#define eps 1e-7#define N 105#define M 26#define mod 20090717using namespace std;int m,n,T,t,k;int ch[N][M];int v[N];int f[N],last[N],num;int d[N][M][1<<10],ans,ep[M];void clear()//Trie树初始化{ num=1; ans=0; memset(d,-1,sizeof(d)); memset(ch[0],0,sizeof(ch[0])); memset(v,0,sizeof(v)); memset(last,0,sizeof(last));}int idx(char c){ return c-'a';}void insert(char str[],int val)//建Trie树{ int len=strlen(str); int u=0; for (int i=0; i

q;//保存的节点下标 f[0]=0; for (int c=0; c

>1)+(x&1));}int dp(int u,int sub,int num){ if(sub==n) return bit(num)>=k; int &ans=d[u][sub][num]; if(ans!=-1)return ans; if(bit(num)>=k)//优化！！否则TLE（dp时也是需要优化的！） { ans=ep[n-sub];return ans; } ans=0; for(int i=0;i<26;i++) { int c=ch[u][i]; ans+=dp(c,sub+1,num+(last[c]^(last[c]&num))); ans%=mod; } return ans;}int main(){#ifndef ONLINE_JUDGE freopen("ex.in","r",stdin);#endif ep[0]=1; for(int i=1;i<=25;i++) ep[i]=(ep[i-1]*26)%mod; while(scanf("%d%d%d%*c",&n,&m,&k)==3) { if(!n&&!m&&!k)return 0; clear(); int i=0; while(m--) { scanf("%s",str); insert(str,i++); } getac(); printf("%d\n",dp(0,0,0)); } return 0;}

View Code

转载于:https://www.cnblogs.com/sbaof/p/3374792.html

你可能感兴趣的文章