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][c]
#define f trie[fail[u]][c]
#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();
    }
}

External link:

http://zerojudge.tw/ShowProblem?problemid=b179

Posted by xiaodao
Category: Online Judge