[UVA][AC自動機DP] 10835 - Playing with Coins
Problem F
Playing with Coins
Input:
Standard
Input
Output: Standard Output
Jack and Jill like to play with coins. They are interested in the patterns generated after n times flip of a coin. As you know, in case of a fair coin if you flip the coin 3 times, you can get either of the following patterns.
|
HHH |
THH |
|
HHT |
THT |
|
HTH |
TTH |
|
HTT |
TTT |
The numbers of different patterns increase exponentially with the increase of number of flips. Jack and Jill categorizes all the patterns considering the sub-patterns they have –
|
H |
HHH, HHT, HTH, HTT, THH, THT, TTH, TTT |
|
HH |
HHH, HHT, THH |
|
HT |
HHT, HTH, HTT, THT |
|
TTH |
TTH |
It is not always possible to examine each pattern. So, some intelligent technique is necessary to do such task. The problem you need solve for Jack and Jill is to find the probability of getting patterns which will not contain any of the previously defined sub-patterns.
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 HH 3 1 HT 3 2 T H 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 <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;
}