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