Brief description:
… 給定一個初始基因，基因每輪每次會在後面添加 {a, b, c ,d} 中的一個字元形成 4 個新基因。舊基因在分裂過後會損失第一個字元。。。。
有 n 組有害基因，如果出現了有害基因作為子串則丟入醫院。。
如果一個基因長度變為 0 則被丟入回收場。。
問最後分別有多少基因丟入醫院多少基因丟入回收場。。。
( .. p <= 100, n <= 100, Σ = {a,b,c,d} .. )
Analysis:
dp[i][j][k] 表示經過 i 天，當前在自動機上位置為 j，串的實際長度為 k 時的狀態。
/**********************************************************************************/
/* Problem: b179 "空罐 Cans" from CSAPC'08 Problem Setter: Akira Nanase */
/* Language: CPP (2909 Bytes) */
/* Result: AC judge by zeroserver@ZeroJudge */
/* Author: lychees at 2011-08-29 01:02:15 */
/**********************************************************************************/
/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DO(n) while(n--)
#define DO_C(n) int n____ = n; while(n____--)
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}
inline int RD(){ int x; RD(x); return x;}
const int MOD = 10007;
inline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;}
/* .................................................................................................................................. */
const int N = 1510, M = 100, L = 102, Sigma = 26, SIGMA = 4;
int dp[2][N][L]; int trie[N][Sigma], fail[N], len[N] = {1}, cnt[N], visited[N], u, cz, op, tot;
char str[M]; int n, s;
// AC-automation
#define v trie[u]
#define f trie[fail[u]]
#define Q visited
inline int New_node(){
fail[tot] = cnt[tot] = 0, RST(trie[tot]);
return tot++;
}
inline void Build(){
cz = op = u = 0; REP(c, Sigma) if (v) Q[op++] = v;
while (cz < op){
u = Q[cz++]; REP(c, Sigma)
if (v) fail[Q[op++] = v] = f, cnt[v] += cnt[fail[v]];
else v = f;
}
}
#define c str[i] - 'a'
bool _first;
inline void Insert(){
u = 0; REP_C(i, strlen(str)){
if (cnt[v]) return; //Prefix Cut ..
if (!v) len[v = New_node()] = i + 1;
u = v;
}
if (_first) _first = false, dp[0][s = u][len[u]] = 1;
else ++cnt[u];
}
#undef c
#undef f
void Init(){
RST(dp[0], trie[0]), tot = 1, _first = true, Insert(), RD(n);
DO_C(RD()) scanf("%s", str), Insert(); Build();
}
#define u Q[i]
#define f fail[u]
#define d dp[q][u][j]
void Run(){
op = 0; REP(i, tot) if (!cnt[i]) Q[op++] = i;
while (s && !cnt[s]) s = fail[s];
if (s){puts("0 1"); return;}
int p = 0, q, a = 0, b = 0;
DO(n){
q = p, p ^= 1, RST(dp[p]);
REP(i, op) FOR_1(j, len[u], 100) if (d){
REP(c, SIGMA) if (cnt[v]) INC(b, d); else INC(dp[p][v][j+1], d);
if (j > len[u]) INC(dp[p][u][j-1], d);
else if (cnt[f]) INC(b, d); else INC(dp[p][f][j-1], d);
}
INC(a, dp[p][0][0]);
}
printf("%d %d\n", a, b);
}
int main(){
//freopen("in.txt", "r", stdin);
while (scanf("%s", str) != EOF){
Init(); Run();
}
}
