密信与计数 CCF

密信与计数 CCF"/>

密信与计数 CCF

http://118.190.20.162/view.page?gpid=T109

当时把这题写完调了一万年，没时间搞第4题了

ac自动机维护数位DP转移

注意要fail链要预处理成sqrt(n)转移，详见

#include<bits/stdc++.h>
using namespace std;const int maxl=1002;
const int mod=998244353;int n,m,k,cas,tot,dicl,ans;
int a[maxl];
int tr[maxl][26],stp[maxl],nxt[60][26],mima[60][26];
char s[60];
char dic[60][60];
int ming[maxl],mi[maxl];
int dp[1002][51][51][51];
int fail[maxl],val[maxl],last[maxl];
queue<int> q;inline void getfail()
{int u,v,cur;while(!q.empty())q.pop();fail[0]=0;for(int c=0;c<26;c++){u=tr[0][c];if(u)fail[u]=0,q.push(u),last[u]=0;}while(!q.empty()){cur=q.front();q.pop();for(int c=0;c<26;c++)if(tr[cur][c]){u=tr[cur][c];q.push(u);v=fail[cur];while(v && !tr[v][c])v=fail[v];fail[u]=tr[v][c];last[u]=val[fail[u]]?fail[u]:last[fail[u]];}}
}inline void prework()
{int x,l;scanf("%d%d",&n,&m);for(int j=0;j<26;j++)for(int i=1;i<=n;i++){scanf("%s",s);mima[i][j]=s[0]-'a';x=0;l=strlen(s);for(int k=1;k<l;k++)x=x*10+s[k]-'0';nxt[i][j]=x;}dicl=0;while(~scanf("%s",dic[dicl+1])){dicl++;l=strlen(dic[dicl]);x=0;for(int i=0;i<l;i++){if(!tr[x][dic[dicl][i]-'a'])tr[x][dic[dicl][i]-'a']=++tot;x=tr[x][dic[dicl][i]-'a'];}stp[x]=dicl;val[x]++;}getfail();//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!/*printf("%d\n",dicl);for(int i=1;i<=dicl;i++){l=strlen(dic[i]);for(int j=0;j<l;j++)printf("%c",dic[i][j]);puts("");}printf("%d\n",tr[0][0]);for(int i=1;i<=tot;i++)printf("%d ",stp[i]);puts("");*/
}inline bool jug(int l)
{int nowp=1,x;for(int i=1;i<=l;i++){ming[i]=mima[nowp][mi[i]];nowp=nxt[nowp][mi[i]];}bool flag=true;for(int i=1;i<=l;i++){x=0;for(int j=i;j<=l;j++){if(!tr[x][mi[j]])break;elsex=tr[x][mi[j]];if(stp[x])return false;}}x=0;for(int i=1;i<=l;i++){if(!tr[x][ming[i]])return false;x=tr[x][ming[i]];if(stp[x])x=0;}if(x)return false;return true;
}inline void dfs4(int k,int l)
{for(int i=0;i<26;i++){mi[k]=i;if(k==l){	if(jug(l)){++ans;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!/*for(int j=1;j<=l;j++)printf("%c",mi[j]+'a');puts("");for(int j=1;j<=l;j++)printf("%c",ming[j]+'a');puts("");*/}}elsedfs4(k+1,l);mi[k]=0;}
}inline void upd(int &x,int y) {x=(x+y)%mod;}inline int dfs(int k,int nowp,int pos1,int pos2)
{if(k>m)return (pos1==0);if(dp[k][nowp][pos1][pos2]>-1)return dp[k][nowp][pos1][pos2];dp[k][nowp][pos1][pos2]=0;int c,npos1,npos2,jj;bool flag;for(int i=0;i<26;i++){c=mima[nowp][i];if(!tr[pos1][c])continue;npos1=tr[pos1][c];if(stp[npos1]) npos1=0;npos2=pos2;c=i;while(npos2 && !tr[npos2][c])npos2=fail[npos2];npos2=tr[npos2][c];jj=npos2;flag=true;while(jj){if(stp[jj])flag=false;jj=last[jj];}//!!!!!!!!!!!!!!!!!!!!!!!/*if(npos1==0)printf("mi=%c ,ming=%c ,npos2=%d\n",i+'a',mima[nowp][i]+'a',npos2);*/if(stp[npos2] || (!flag))continue;upd(dp[k][nowp][pos1][pos2],dfs(k+1,nxt[nowp][i],npos1,npos2));}return dp[k][nowp][pos1][pos2];
}inline void mainwork()
{int nowp;/*if(m<=4){for(int l=1;l<=m;l++){ans=0;dfs4(1,l);printf("%d\n",ans);}return;}*/memset(dp,-1,sizeof(dp));//printf("%lld\n",dfs(4,1,0,0));for(int i=1;i<=m;i++)if(dp[i][1][0][0]==-1)dfs(i,1,0,0);for(int i=1;i<=m;i++)printf("%d\n",dp[m-i+1][1][0][0]);
}inline void print()
{}int main()
{int t=1;//scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();print();}return 0;
}