2013-05-15 16:04:31| 人氣494| 回應0 | 上一篇 | 下一篇

[UVA][AC自動機DP] 10835 - Playing with Coins

Input

Each test case starts with a positive integer N (1<=N<=50) which means the number of flips and K (0<=K<=50) indicating the number of sub-patterns. Nest K lines will contain the sub-patterns which will be a sequence of H and T. All sub-patterns have same length and it will be at most 10. Input is terminated by N=K=0. This case should not be processed. There can be at most 100 test cases.

Output

Output of each test case should consist of a line starting with “Case #: “where ‘#’ is the test case number. It should be followed by the probability of getting patterns which will not contain any of the given K sub-patterns. If the probability is non-zero, then print it in the form of “a/b” where a, b are properly reduced. If the probability is zero, then print “0” simply.

Sample Input Output for Sample Input

3 1

3 2

0 0

Case 1: 5/8

Case 2: 1/2

Case 3: 0

Problem setter: Md. Kamruzzaman

Special Thanks: Jimmy Mårdell

題目意思：
求一個長度為 n (僅有 'H', 'T' 兩個字母)不包含任何給定的 pattern.

AC自動機 DP。
將遞增序列忽略，先當成任意字串由給定的字母集構成的。
將輸入的限制當作一個字串，將這些限制建成一棵 Trie，
並且建成 AC自動機，其中要標記字串的前綴是否存在某一個字串的結尾。

而最後由遞迴公式 dp[len][node]去更新dp[len+1][Next[node]]
釐清一點：Next[node] 可能需要走失敗指針。
len 是走的步數(又或者當作字串長度)，node 是節點編號。
設定 dp[0][root] = 1，模擬 AC自動機匹配的方式進行，
為了要生成遞增序列，更新的時候試圖增加比當前結尾還大的字符，
但在 dp 表格中不想存放結尾字符，只有在 root 會發生問題，
其餘的節點都可以拿當前節點所代表的字符表示。

因此一開始增加所有字符插入 Trie 中，而這些字符不是限制。

#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[2], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[105]; // [string length]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
// 'H' 1, 'T' 0
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = (str[i] == 'H');
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 2; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 2; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
long long gcd(long long a, long long b) {
    if(a == 0) return b;
    if(b == 0) return a;
    long long t;
    while(a%b)
        t = a, a = b, b = t%b;
    return b;
}
void dp(Node *root, int len) {
    queue<Node*> Q;
    Node *nd, *p;
    root->dp[0] = 1;
    int k, i, j;
    long long ans, ret = 0;
    for(k = 0; k <= len; k++) {
        Q.push(root);
        ans = 0;
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for(i = 0; i < 2; i++) {
                if(nd->next[i] != NULL) {
                    if(nd->next[i]->eos)
                        continue;//not safe
                    nd->next[i]->dp[k+1] = nd->next[i]->dp[k+1] + nd->dp[k];
                    Q.push(nd->next[i]);
                } else {
                    p = nd;
                    while(p != root && p->next[i] == NULL)
                        p = p->fail;
                    p = p->next[i];
                    if(p == NULL) // error message
                        puts("NULL");
                    if(p->eos)
                        continue;//not safe
                    p->dp[k+1] += nd->dp[k];
                }
            }
            ans += nd->dp[k];
        }
        if(k == len)
            ret += ans;
    }
    ans = 1LL<<len;// ret/ans
    long long g = gcd(ret, ans);
    ans /= g, ret /= g;
    if(ret == 0)
        puts("0");
    else
        printf("%lld/%lld\n", ret, ans);
}
int main() {
    int n, p, i;
    int cases = 0;
    char pattern[105];
    while(scanf("%d %d", &n, &p) == 2) {
        if(n == 0 && p == 0)
            break;
        Node *root = new Node();
        for(i = 0; i < p; i++) {
            scanf("%s", pattern);
            insertTrie(pattern, root, 1);
        }
        pattern[0] = 'H', pattern[1] = '\0';
        insertTrie(pattern, root, 0);
        pattern[0] = 'T', pattern[1] = '\0';
        insertTrie(pattern, root, 0);
        printf("Case %d: ", ++cases);
        buildACautomation(root);
        dp(root, n);
        freeTrie(root);
    }
    return 0;
}

我要檢舉

#10835#Playing with Coins#AC自動機#DP

台長： Morris

您可能對以下文章有興趣

[UVA] 1197 - The Suspects

[UVA] 10416 - Folding My T-Shirt

[UVA][井字遊戲盤面判斷] 10363 - Tic Tac Toe

[UVA] 400 - Unix ls

人氣(494) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][模擬] 758 - The Same Game
此分類上一篇:[UVA][數學] 1363 - Joseph's Problem

回應(0)

HHH	THH
HHT	THT
HTH	TTH
HTT	TTT

H	HHH, HHT, HTH, HTT, THH, THT, TTH, TTT
HH	HHH, HHT, THH
HT	HHT, HTH, HTT, THT
TTH	TTH