伦boy好像要出这样的题？
这题好像和GT考试有点像
换成AC自动机然后暴力dp
如果总单词数再大一点就得用矩阵快速幂了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// <1030.cpp> - 06/26/16 10:41:26 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100001; const int INF=1e9; const int MOD=10007; int tot=1,s[MAXN][26],fail[MAXN]; bool key[MAXN]; void get(){ static char ch[120]; scanf("%s",ch); int l=strlen(ch),now=1; for(int i=0;i<l;i++){ if(!s[now][ch[i]-'A'])s[now][ch[i]-'A']=++tot; now=s[now][ch[i]-'A']; if(key[now])break; } key[now]=1; } queue <int> q; lol mat[MAXN][26]; lol dp[101][MAXN]; int main(){ int n=gi(),m=gi(); for(int i=0;i<26;i++)s[0][i]=1; while(n--)get(); q.push(1); while(!q.empty()){ int now=q.front();q.pop(); for(int i=0;i<26;i++){ if(!s[now][i])continue; int f=fail[now]; while(!s[f][i])f=fail[f]; fail[s[now][i]]=s[f][i]; if(key[s[f][i]])key[s[now][i]]=1; q.push(s[now][i]); } } for(int i=1;i<=tot;i++) for(int j=0;j<26;j++){ if(key[i]){mat[i][j]=i;continue;} int now=i; while(!s[now][j])now=fail[now]; mat[i][j]=s[now][j]; } dp[0][1]=1; for(int i=1;i<=m;i++) for(int j=1;j<=tot;j++) for(int k=0;k<26;k++)dp[i][mat[j][k]]=(dp[i][mat[j][k]]+dp[i-1][j])%MOD; lol ans=0; for(int i=2;i<=tot;i++)if(key[i])ans=(ans+dp[m][i])%MOD; printf("%lld",ans); return 0; } |
说点什么