hdu 6086 -- Rikka with String(AC自動機 + 狀壓DP)

題目鏈接

?

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has?n?01?strings?si, and he wants to know the number of?01?antisymmetric strings of length?2L?which contain all given strings?si?as continuous substrings.

A?01?string?s?is antisymmetric if and only if?s[i]≠s[|s|?i+1]?for all?i∈[1,|s|].

It is too difficult for Rikka. Can you help her?

In the second sample, the strings which satisfy all the restrictions are?000111,001011,011001,100110.

?

Input

The first line contains a number?t(1≤t≤5), the number of the testcases.?

For each testcase, the first line contains two numbers?n,L(1≤n≤6,1≤L≤100).?

Then?n?lines follow, each line contains a?01?string?si(1≤|si|≤20).

?

Output

For each testcase, print a single line with a single number -- the answer modulo 998244353.

?

Sample Input

2

2 2

011

001

2 3

011

001

?

Sample Output

1

4

題意：反對稱：對于一個長為2*N的串s[0~2*N-1]，s[i]^s[2*N-1-i]=1 。現在有n個01串，求有多少個長為2*L的并且包含這n個串的?反對稱01串？

思路：對于一個串包含在2*L的01串中，那么這個串要么在2*L的前半部分，要么后半部分，或者跨越中間，如果在后半部分，則需要找到其在前半部分的反對稱01串，對于跨越中間的01串，則需要找到其在前面部分的串，例如：0 | 11，以豎線作為串中間，那么如果前面部分如果以00結束，那么一定含有 011這個串。把每個串的所有形式放入AC自動機對應的tire樹中，然后狀壓遞推。

代碼如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
const int mod=998244353;
const int N=2005;
struct Node{int id;Node *fail;Node *son[2];int tag1,tag2;
}node[N];
queue<Node *>q;
int tot;
int dp[2][2005][64];void insert1(string s,int id)
{int len=s.length();Node *now=&node[0];for(int i=0;i<len;i++){int x=s[i]-'0';if(now->son[x]==NULL) now->son[x]=&node[tot++];now=now->son[x];}now->tag1|=(1<<id);
}
void insert2(string s,int id)
{int len=s.length();Node *now=&node[0];for(int i=0;i<len;i++){int x=s[i]-'0';if(now->son[x]==NULL) now->son[x]=&node[tot++];now=now->son[x];}now->tag2|=(1<<id);
}
void init()
{for(int i=0;i<N;i++){node[i].id=i;node[i].fail=NULL;node[i].son[0]=node[i].son[1]=NULL;node[i].tag1=node[i].tag2=0;}
}
void setFail()
{Node* root=&node[0];q.push(root);while(!q.empty()){Node* now=q.front(); q.pop();for(int i=0;i<2;i++){if(now->son[i]){Node* p=now->fail;while(p && (!(p->son[i]))) p=p->fail;now->son[i]->fail=(p)?(p->son[i]):(root);now->son[i]->tag1|=now->son[i]->fail->tag1;now->son[i]->tag2|=now->son[i]->fail->tag2;q.push(now->son[i]);}else now->son[i]=(now!=root)?now->fail->son[i]:(root);}}
}
void print()
{Node* now=&node[0];queue<Node*>qq;qq.push(now);while(!qq.empty()){now=qq.front(); qq.pop();cout<<"Y:"<<now->id<<" ";for(int i=0;i<2;i++){if(now->son[i]) qq.push(now->son[i]),cout<<now->son[i]->id<<" ";else cout<<"NULL"<<" ";}cout<<endl;}
}
int main()
{///cout << "Hello world!" << endl;
    int t; cin>>t;while(t--){init();tot=1;int n,L; scanf("%d%d",&n,&L);for(int i=0;i<n;i++){string s; cin>>s;insert1(s,i);string t=s;reverse(t.begin(),t.end());int len=s.length();for(int j=0;j<len;j++)t[j]=(char)((t[j]-'0')^1+'0');insert1(t,i);int mnLen=min(len,L);for(int j=0;j<mnLen;j++){int f=1;for(int l=j,r=j+1; l>=0&&r<len; l--,r++){if((s[l]^s[r])==0) { f=0; break; }}if(!f) continue;t=s.substr(0,j+1);for(int k=2*j+2;k<len;k++){t=(char)((s[k]-'0')^1+'0')+t;}insert2(t,i);}}///print();
       setFail();memset(dp,0,sizeof(dp));dp[0][0][0]=1;int cn=0,stu=(1<<n);for(int i=0;i<L;i++){int c=cn^1;memset(dp[c],0,sizeof(dp[c]));for(int j=0;j<tot;j++){for(int s=0;s<stu;s++){if(!dp[cn][j][s]) continue;if(i<L-1)for(int k=0;k<2;k++){int x=node[j].son[k]->id;int tag=node[x].tag1;dp[c][x][s|tag]=(dp[c][x][s|tag]+dp[cn][j][s])%mod;}elsefor(int k=0;k<2;k++){int x=node[j].son[k]->id;int tag=node[x].tag1|node[x].tag2;dp[c][x][s|tag]=(dp[c][x][s|tag]+dp[cn][j][s])%mod;}}}cn=c;}int ans=0;for(int i=0;i<tot;i++){ans=(ans+dp[cn][i][stu-1])%mod;}printf("%d\n",ans);}return 0;
}

?

?