题目来源：NOI2018模拟测试赛（二十六）

题解：

首先由于这是个01串，所以反对称串的意思就是这个字符串的后半部分是前半部分的反转且翻转结果；

一个串出现有三种情况：在前半部分，在后半部分或穿过中间；

对于前两种情况，由于n很小，可以直接在AC自动机跑状压DP，对于第三种情况特殊处理一下，就是对于所有子串的所有前缀，判断以这个前缀为结尾能否构造出这个串，有则累加答案就好了，具体见代码。

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 #define mod 998244353

 using namespace std;

 typedef long long ll;

 typedef double db;

 struct ac{

     int fa,fail,son[],s,t;

 }t[];

 int n,m,nw,tmp,ans=,len,cnt=,num[],f[][][];

 char s[];

 void ins(char *s,int len,int id){

     int nw=;

     for(int i=;i<=len;i++){

         if(!t[nw].son[s[i]-'']){

             t[nw].son[s[i]-'']=++cnt;

             num[cnt]=s[i]-'';

             t[cnt].fa=nw;

         }

         nw=t[nw].son[s[i]-''];

     }

     t[nw].s|=(<<id-);

 }

 void AC(){

     queue<int>q;

     for(int i=;i<=;i++){

         if(t[].son[i]){

             q.push(t[].son[i]);

             t[t[].son[i]].fail=;

         }

     }

     while(!q.empty()){

         int u=q.front();

         q.pop();

         t[u].s|=t[t[u].fail].s;

         for(int i=;i<=;i++){

             if(t[u].son[i]){

                 t[t[u].son[i]].fail=t[t[u].fail].son[i];

                 q.push(t[u].son[i]);

             }else t[u].son[i]=t[t[u].fail].son[i];

         }

     }

 }

 int getfa(int u){

     int ret=;

     for(int nw=u;nw;nw=t[nw].fa){

         u=t[u].son[num[nw]^];

         ret|=t[u].s;

     }

     return ret;

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         scanf("%s",s+);

         len=strlen(s+);

         ins(s,len,i);

         reverse(s+,s+len+);

         for(int j=;j<=len;j++){

             s[j]=((s[j]-'')^)+'';

         }

         ins(s,len,i);

     }

     AC();

     f[][][]=;

     for(int tt=;tt<=m;tt++){

         nw^=;

         memset(f[nw],,sizeof(f[nw]));

         for(int i=;i<=cnt;i++){

             for(int j=;j<(<<n);j++){

                 for(int k=;k<=;k++){

                     f[nw][t[i].son[k]][j|t[t[i].son[k]].s]=(f[nw][t[i].son[k]][j|t[t[i].son[k]].s]+f[nw^][i][j])%mod;

                 }

             }

         }

     }

     for(int i=;i<=cnt;i++){

         tmp=getfa(i);

         for(int j=;j<(<<n);j++){

             if((tmp|j)==(<<n)-){

                 ans=(ans+f[nw][i][j])%mod;

             }

         }

     }

     printf("%d",ans);

     return ;

 }

巴特西

【XSY2989】字符串

题解：

代码：

最新文章

热门文章