bzoj 1444 [Jsoi2009]有趣的游戏

Description

Input

注意 是0<=P

Output

Sample Input

Sample Output

HINT

 30%的数据保证, n ≤ 2. 50%的数据保证, n ≤ 5. 100%的数据保证, n , l, m≤ 10.

Source

【分析】

AC自动机+矩阵乘法

本来概率这么奇奇怪怪的东西是不能暴算的...但是精度要求很低，矩阵乘法暴算2^50基本可以得到解。

【代码】

//bzoj 1444 [Jsoi2009]有趣的游戏
#include
#include
#include
#include
#include
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int mxn=105;
char s[mxn];
queue  q;
double g[mxn];
int n,m,len,num=1;
struct matrix
{double a[mxn][mxn];matrix operator * (const matrix &x) const{matrix res;fo(i,1,num)fo(j,1,num){res.a[i][j]=0.0;fo(k,1,num)res.a[i][j]+=a[i][k]*x.a[k][j];}return res;}
}ans,S;
struct AC_auto
{int son[15],fail,dang;
}a[mxn];
inline void trie(int id)
{int x=1;scanf("%s",s+1);fo(i,1,len){int c=s[i]-'A'+1;if(!a[x].son[c])a[x].son[c]=(++num);x=a[x].son[c];}a[x].dang=id;
}
inline void build()
{fo(i,1,m){int x=a[1].son[i];if(x) q.push(x),a[x].fail=1;else a[1].son[i]=1;}while(!q.empty()){int x=q.front();q.pop();int fail=a[x].fail;fo(i,1,m){int y=a[x].son[i];if(!y) a[x].son[i]=a[fail].son[i];else q.push(y),a[y].fail=a[fail].son[i];}}
}
int main()
{int i,j,k,u,v,now=0;scanf("%d%d%d",&n,&len,&m);fo(i,1,m){scanf("%d%d",&u,&v);g[i]=(double)u/(double)v;}fo(i,1,n) trie(i);build();fo(i,1,num)fo(j,1,m) if(a[i].son[j])ans.a[i][a[i].son[j]]+=g[j];fo(i,1,num) if(a[i].dang){fo(j,1,num) ans.a[i][j]=0.0;ans.a[i][i]=1.0;}int czy=50;while(czy--){S=ans;M(ans.a);ans=S*S;}fo(i,1,num) g[a[i].dang]=ans.a[1][i];fo(i,1,n) printf("%.2lf\n",g[i]);return 0;
}
/*
3 4 2
1 2
1 2
AABA
ABAA
BAAA
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！