JSOI交給隊員ZYX一個任務,編制一個稱之為“文本生成器”的電腦軟件:該軟件的使用者是一些低幼人群,他們現在使用的是GW文本生成器v6版。該軟件可以隨機生成一些文章―――總是生成一篇長度固定且完全隨機的文章—— 也就是說,生成的文章中每個字節都是完全隨機的。如果一篇文章中至少包含使用者們了解的一個單詞,那麼我們說這篇文章是可讀的(我們稱文章a包含單詞b,當且僅當單詞b是文章a的子串)。但是,即使按照這樣的標准,使用者現在使用的GW文本生成器v6版所生成的文章也是幾乎完全不可讀的。 ZYX需要指出GW文本生成器 v6生成的所有文本中可讀文本的數量,以便能夠成功獲得v7更新版。你能幫助他嗎?
輸入文件的第一行包含兩個正整數,分別是使用者了解的單詞總數N (<= 60),GW文本生成器 v6生成的文本固定長度M;以下N行,每一行包含一個使用者了解的單詞。 這裡所有單詞及文本的長度不會超過100,並且只可能包含英文大寫字母A..Z 。
一個整數,表示可能的文章總數。只需要知道結果模10007的值。
畢竟是自己做的第一道AC自動機題,還是小小地慶祝一下吧……
我們假設在Trie樹中表示單詞結尾的節點為結尾點。
在添加失配邊後,Trie樹就轉化成一個有向圖,問題也就轉化成:從起點出發,走m步,至少路過一個結尾點的方案數。
這就可以用動態規劃來實現了。具體方法如下:
用f[i][j][0]表示走i步到達j點不經過結尾點的方案數,用f[i][j][1]表示走i步到達j點經過結尾點的方案數。
我們很容易可以想到狀態轉移方程。(詳見程序)
最終答案為∑(i)f[m][i][1],注意每次計算後都要取模。
#include#include #include #include #include #include #include #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define pa pair #define mod 10007 using namespace std; int t[6010][26],f[110][6010][2],v[6010],go[6010]; int n,m,tot; char s[110]; queue q; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void insert() { scanf("%s",s+1); int len=strlen(s+1),now=1; F(i,1,len) { int x=s[i]-'A'; if (!t[now][x]) t[now][x]=++tot; now=t[now][x]; } v[now]=1; } inline void bfs() { q.push(1); while (!q.empty()) { int x=q.front(),y,j;q.pop();v[x]|=v[go[x]]; F(i,0,25) { j=go[x]; while (j&&!t[j][i]) j=go[j]; if (t[x][i]) { go[y=t[x][i]]=j?t[j][i]:1; q.push(y); } else t[x][i]=j?t[j][i]:1; } } } inline void dp() { f[0][1][0]=1; F(i,0,m) F(j,1,tot) F(k,0,25) F(l,0,1) { if (v[t[j][k]]) (f[i+1][t[j][k]][1]+=f[i][j][l])%=mod; else (f[i+1][t[j][k]][l]+=f[i][j][l])%=mod; } } int main() { n=read();m=read();tot=1; F(i,1,n) insert(); bfs(); dp(); int ans=0; F(i,1,tot) (ans+=f[m][i][1])%=mod; printf("%d\n",ans); return 0; }