# 某岛

… : "…アッカリ～ン . .. . " .. .
July 3, 2012

## ZeroJudge b179. 空罐 Cans

### Brief description:

… 给定一个初始基因，基因每轮每次会在后面添加 {a, b, c ,d} 中的一个字符形成 4 个新基因。旧基因在分裂过后会损失第一个字符。。。。

( .. 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]);
}

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();
}
}
`