设dp[u][L]为当前在结点u，再走L步合法的概率。
如果当前结点不是单词结点，并不能判定该结点一定合法，还应该沿着失配边往回走，因为可能失配边往回走的过程中出现了不合法的，不过这里不需要专门往回走，只要看last就可以知道往回走的过程中是否有单词结点了。
都发现了这一点了，居然还是WA了。。。本来判定就慢。。。还坑多。。。万恶的uva。。。。
先留代码，明天再调。。。
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100100; const int INF=1e9+10; int K,N,L; double pro[maxn]; double dp[510][120]; bool vis[510][120]; char s[1200][1200]; const int cn=10+26+26; int idx[maxn]; struct Trie { int ch[maxn][cn]; int End[maxn]; int f[maxn]; int last[maxn]; int rt,tot; int newnode() { ++tot; memset(ch[tot],-1,sizeof(ch[tot])); End[tot]=0; return tot; } void init() { tot=-1; rt=newnode(); } void insert(char *s) { int len=strlen(s); int u=rt; REP(i,0,len-1){ int c=idx[s[i]]; if(ch[u][c]==-1) ch[u][c]=newnode(); u=ch[u][c]; } End[u]++; } void build() { queue<int> q; f[rt]=rt;last[rt]=rt; REP(c,0,N-1){ if(~ch[rt][c]) f[ch[rt][c]]=rt,q.push(ch[rt][c]); else ch[rt][c]=rt; } while(!q.empty()){ int u=q.front();q.pop(); REP(c,0,N-1){ if(~ch[u][c]) f[ch[u][c]]=ch[f[u]][c],q.push(ch[u][c]); else ch[u][c]=ch[f[u]][c]; if(End[f[u]]) last[u]=f[u]; else last[u]=last[f[u]]; } } } double dfs(int u,int L) { if(vis[u][L]) return dp[u][L]; vis[u][L]=1; double &res=dp[u][L]; if(End[u]||last[u]) return res=0; if(L==0) return res=1; res=0; REP(c,0,N-1){ int v=ch[u][c]; res+=pro[c]*dfs(v,L-1); } return res; } };Trie ac; int main() { freopen("in.txt","r",stdin); int T;cin>>T; REP(casen,1,T){ scanf("%d",&K); REP(i,1,K){ scanf("%s",s[i]); } scanf("%d",&N); double p;char c; REP(i,0,N-1){ cin>>c>>p; idx[c]=i; pro[i]=p; } ac.init(); REP(i,1,K) ac.insert(s[i]); ac.build(); scanf("%d",&L); MS0(vis); printf("Case #%d: %.6f ",casen,ac.dfs(ac.rt,L)); } return 0; } /** 2 1 a 2 a 0.5 b 0.5 2 2 ab ab 2 a 0.2 b 0.8 2 */
--------------
是我英语不好还是题目真坑。。。刚想关电脑睡觉，睡前把刚才第一次写的代码改了一下提交，居然过了。。。。一开始我没看到题目的“Valid characters are all alphanumeric characters”这句话，于是建立初始化字典树的时候把cn设为64(最多的情况10+26+26)，但是题目明明说了“Valid characters are all alphanumeric characters”给定的字符包括所有模版串用到的字符？。。。于是我只把cn开成了N。。。
本来就没必要改。。。按原来那样写常数大了一点，但复杂度明显不会超，牺牲一些运行效率却能大大增加代码准确性，而且可以避开题目潜在的坑。。。和数组开大点是一个道理。。
不过重点还是前面的失配边。。。
#include<bits/stdc++.h> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100100; const int INF=1e9+10; int K,N,L; double pro[maxn]; double dp[510][120]; bool vis[510][120]; char s[maxn]; const int cn=10+26+26; int idx(char c) { if(isdigit(c)) return c-'0'; else if(isupper(c)) return 10+c-'A'; else return 10+26+c-'a'; } struct Trie { int ch[maxn][cn]; int End[maxn]; int f[maxn]; int last[maxn]; int rt,tot; int newnode() { ++tot; memset(ch[tot],-1,sizeof(ch[tot])); End[tot]=0; return tot; } void init() { tot=-1; rt=newnode(); } void insert(char *s) { int len=strlen(s); int u=rt; REP(i,0,len-1){ int c=idx(s[i]); if(ch[u][c]==-1) ch[u][c]=newnode(); u=ch[u][c]; } End[u]++; } void build() { queue<int> q; f[rt]=rt;last[rt]=rt; REP(c,0,cn-1){ if(~ch[rt][c]) f[ch[rt][c]]=rt,q.push(ch[rt][c]); else ch[rt][c]=rt; } while(!q.empty()){ int u=q.front();q.pop(); REP(c,0,cn-1){ if(~ch[u][c]) f[ch[u][c]]=ch[f[u]][c],q.push(ch[u][c]); else ch[u][c]=ch[f[u]][c]; if(End[f[u]]) last[u]=f[u]; else last[u]=last[f[u]]; } } } double dfs(int u,int L) { if(vis[u][L]) return dp[u][L]; vis[u][L]=1; double &res=dp[u][L]; if(End[u]||last[u]) return res=0; if(L==0) return res=1; res=0; REP(c,0,cn-1){ int v=ch[u][c]; res+=pro[c]*dfs(v,L-1); } return res; } };Trie ac; int main() { freopen("in.txt","r",stdin); int T;cin>>T; REP(casen,1,T){ scanf("%d",&K); ac.init(); REP(i,1,K){ scanf("%s",s); ac.insert(s); } ac.build(); scanf("%d",&N); REP(i,0,cn-1) pro[i]=0; double p;char c; REP(i,1,N){ cin>>c>>p; pro[idx(c)]=p; } scanf("%d",&L); MS0(vis); printf("Case #%d: %.6f ",casen,ac.dfs(ac.rt,L)); } return 0; } /** 2 1 a 2 a 0.5 b 0.5 2 2 ab ab 2 a 0.2 b 0.8 2 */