意甲冠军：
给n快报，和m频率。
然后进入n字母出现的概率
然后给目标字符串str
然后问m概率倍的目标字符串是敲数量。
思维：
AC自己主动机+可能性dp简单的问题。
首先建立trie图，然后就是状态转移了
dp版本号：
dp三重循环变量次数，节点数，和字母数
代码：
#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"#include"string"using namespace std;int triecont;double dp[1234][22];struct trie{ int mark,id; trie *next[27],*fail; trie() { mark=id=0; memset(next,0,sizeof(next)); fail=NULL; }};trie *root,*node[22];void init(char *v){ trie *p=root; for(int i=0;v[i];i++) { int tep=v[i]-'a'; if(p->next[tep]==NULL) { p->next[tep]=new trie(); node[triecont]=p->next[tep]; p->next[tep]->id=triecont++; } p=p->next[tep]; } p->mark++;}void getac(){ queue q; q.push(root); while(!q.empty()) { trie *p=q.front(); q.pop(); for(int i=0;i<26;i++) { if(p->next[i]==NULL) { if(p==root) p->next[i]=root; else p->next[i]=p->fail->next[i]; } else { if(p==root) p->next[i]->fail=root; else p->next[i]->fail=p->fail->next[i]; q.push(p->next[i]); } } }}int main(){ int n,m; while(scanf("%d%d",&n,&m),(n+m)) { double gl[27]; memset(gl,0,sizeof(gl)); memset(node,0,sizeof(node)); while(n--) { char x[2]; double y; scanf("%s%lf",x,&y); gl[x[0]-'a']=y; } char fuck[27]; scanf("%s",fuck); triecont=0; root=new trie(); node[triecont]=root; root->id=triecont++; init(fuck); getac(); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=m;i++) { for(int j=0;j next[k]; dp[i][p->id]+=dp[i-1][j]*gl[k]; } } } double ans=0; for(int i=0;i<=m;i++) ans+=dp[i][triecont-1]; printf("%.2f%%\n",ans*100); } return 0;} 建立可达矩阵版本号： 注意到达目标状态 那么他之后的状态的概率就都是1了
然后用高速幂加速~
#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"using namespace std;int triecont;struct trie{ int mark,id; trie *next[27]; trie *fail; trie() { mark=id=0; memset(next,0,sizeof(next)); fail=NULL; }};struct matrix{ double mat[20][20];};trie *root;void init(char *v){ trie *p=root; for(int i=0; v[i]; i++) { int tep=v[i]-'a'; if(p->next[tep]==NULL) { p->next[tep]=new trie(); p->next[tep]->id=triecont++; } p=p->next[tep]; } p->mark=1;}void getac(){ queue q; q.push(root); while(!q.empty()) { trie *p; p=q.front(); q.pop(); for(int i=0; i<26; i++) { if(p->next[i]==NULL) { if(p==root) p->next[i]=root; else p->next[i]=p->fail->next[i]; } else { if(p==root) p->next[i]->fail=root; else p->next[i]->fail=p->fail->next[i]; q.push(p->next[i]); } } }}matrix matmul(matrix a,matrix b,int n){ int i,j,k; matrix c; memset(c.mat,0,sizeof(c.mat)); for(i=0; i >=1; } return b;}int main(){ int n,m; while(scanf("%d%d",&n,&m),(n+m)) { double gl[27]; memset(gl,0,sizeof(gl)); while(n--) { char x[2]; double y; scanf("%s%lf",x,&y); gl[x[0]-'a']+=y; } triecont=0; root=new trie(); root->id=triecont++; char x[12]; scanf("%s",x); init(x); getac(); queue q; q.push(root); int used[12]; memset(used,0,sizeof(used)); matrix a,ans; memset(a.mat,0,sizeof(a.mat)); while(!q.empty()) { trie *p=q.front(); q.pop(); if(used[p->id]) continue; used[p->id]=1; if(p->mark==1) //目标状态 兴许状态都是本身 { a.mat[p->id][p->id]=1; continue; } for(int i=0;i<26;i++) { if(used[p->next[i]->id]==0) q.push(p->next[i]); a.mat[p->id][p->next[i]->id]+=gl[i]; } } /*for(int i=0;i 版权声明：本文博客原创文章，博客，未经同意，不得转载。