题目大意：给你一些模板串和组成这些模板串的字符，从中随机选L个字符，每个字符都有各自被选的概率p，保证p之和为1，问抽到的串不包含模板串的概率
建一颗tire树，不能走打了tag的标记，走每条边概率已知，求走到深度L的概率，dp[i][j]表示到第i个点还能走j步的概率，转移即可
但这样做存在问题，可能某个短串是长串的子串，但是上述做法无法判断
可以建一颗tire树，从某个节点不断走fail，要求fail路径上的点都没有tag标记
其实这就是last的功能，即最近一个t串相同的ag标记的位置
莫名其妙空间开大了过不了，开小了过了，没有memset p数组过不了，memset了过了，是不是数据出的有问题，串中含有给的字符里没有的字符？
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <cmath> 9 #define min(a, b) ((a) < (b) ? (a) : (b)) 10 #define max(a, b) ((a) > (b) ? (a) : (b)) 11 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a)) 12 inline void swap(int &a, int &b) 13 { 14 long long tmp = a;a = b;b = tmp; 15 } 16 inline void read(int &x) 17 { 18 x = 0;char ch = getchar(), c = ch; 19 while(ch < '0' || ch > '9') c = ch, ch = getchar(); 20 while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); 21 if(c == '-') x = -x; 22 } 23 24 const int INF = 0x3f3f3f3f; 25 26 int t, k, n, l, ch[2000][80], fail[2000], last[2000], cnt, tag[2000], ca, vis[2000][100]; 27 double p[800], dp[2000][100]; 28 char s[200][200], base[800]; 29 int check(char c) 30 { 31 if(c >= '0' && c <= '9') return c - '0' + 1; 32 if(c >= 'A' && c <= 'Z') return c - 'A' + 11; 33 return c - 'a' + 37; 34 } 35 void insert(int x) 36 { 37 int now = 0; 38 for(register int i = 1;s[x][i] != ' ';++ i) 39 { 40 int tmp = check(s[x][i]); 41 if(ch[now][tmp]) now = ch[now][tmp]; 42 else now = ch[now][tmp] = ++ cnt; 43 } 44 ++ tag[now]; 45 } 46 47 int q[1000], he, ta; 48 49 void build() 50 { 51 he = ta = 0; 52 for(register int i = 1;i <= 62;++ i) 53 if(ch[0][i]) q[ta ++] = ch[0][i], fail[ch[0][i]] = last[ch[0][i]] = 0; 54 while(he < ta) 55 { 56 int now = q[he ++]; 57 for(register int i = 1;i <= 62;++ i) 58 { 59 int u = ch[now][i]; 60 if(!u) 61 { 62 ch[now][i] = ch[fail[now]][i]; 63 continue; 64 } 65 q[ta ++] = u; 66 int v = fail[now]; 67 while(v && !ch[v][i]) v = fail[v]; 68 fail[u] = ch[v][i]; 69 last[u] = tag[fail[u]] ? fail[u] : last[fail[u]]; 70 } 71 } 72 } 73 74 double dfs(int x, int y) 75 { 76 if(!y) return 1; 77 if(vis[x][y]) return dp[x][y]; 78 vis[x][y] = 1; 79 dp[x][y] = 0; 80 for(register int i = 1;i <= 62;++ i) 81 if(!tag[ch[x][i]] && !last[ch[x][i]]) dp[x][y] += p[i] * dfs(ch[x][i], y - 1); 82 return dp[x][y]; 83 } 84 85 int main() 86 { 87 read(t); 88 for(ca = 1;t;-- t, ++ ca) 89 { 90 memset(ch, 0, sizeof(ch)), memset(tag, 0, sizeof(tag)), cnt = 0, memset(vis, 0, sizeof(vis));memset(p, 0, sizeof(p)); 91 read(k); 92 for(register int i = 1;i <= k;++ i) scanf("%s", s[i] + 1), insert(i); 93 read(n); 94 for(register int i = 1;i <= n;++ i) 95 scanf("%s", &base[i]), scanf("%lf", &p[check(base[i])]); 96 read(l); 97 build(); 98 printf("Case #%d: %.6lf ", ca, dfs(0, l)); 99 } 100 return 0; 101 }