1444: [Jsoi2009]有趣的游戏
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1800 Solved: 645[][][]Description
Input
注意 是0<=P, n , l, m≤ 10.
Output
Sample Input
input 1 3 2 2 1 2 1 2 AB BA AA input 2 3 4 2 1 2 1 2 AABA ABAA BAAA
Sample Output
output 1 0.25 0.50 0.25 output 2 0.31 0.33 0.37
HINT
建个AC自动机之后，直接搞出转移的矩阵然后直接高斯消元即可。(既然是套路题我就不多说了2333)
#include#define ll long longusing namespace std;#define D doubleconst int maxn=205;const D eps=1e-9;int ch[maxn][27],n,m,l,cnt,X,Y;int f[maxn],rot=0,dy[27];D a[maxn][maxn],p[27];char s[37];bool islef[maxn];inline int Id(char x){ return x-'A'+1;}inline void Ins(int x){ int now=rot; for(int i=1,C;i<=l;i++){ C=Id(s[i]); if(!ch[now][C]) ch[now][C]=++cnt; now=ch[now][C]; } dy[x]=now,islef[now]=1;}inline void getfail(){ queue q; for(int i=1;i<=m;i++) if(ch[rot][i]){ f[ch[rot][i]]=0,q.push(ch[rot][i]);} int x,v; while(!q.empty()){ x=q.front(),q.pop(); for(int i=1;i<=m;i++){ v=ch[x][i]; if(!v){ ch[x][i]=ch[f[x]][i]; continue;} q.push(v); f[v]=ch[f[x]][i]; } }}inline void build(){ a[0][cnt+1]=1; for(int i=0;i<=cnt;i++){ a[i][i]=1; if(!islef[i]) for(int j=1;j<=m;j++) a[ch[i][j]][i]-=p[j]; } /* for(int i=0;i<=cnt;i++){ for(int j=0;j<=cnt+1;j++) printf("%.2lf ",a[i][j]); puts(""); } */}inline void xy(){ for(int i=0;i<=cnt;i++){ int tmp=i; for(int j=i+1;j<=cnt;j++) if(a[j][i]>a[tmp][i]) tmp=j; if(tmp>i) for(int k=cnt+1;k>=i;k--) swap(a[i][k],a[tmp][k]); for(int j=i+1;j<=cnt;j++) if(fabs(a[j][i])>eps){ D o=a[j][i]/a[i][i]; for(int k=cnt+1;k>=i;k--) a[j][k]-=a[i][k]*o; } } for(int i=cnt;i;i--){ for(int j=i+1;j<=cnt;j++) a[i][cnt+1]-=a[i][j]*a[j][cnt+1]; a[i][cnt+1]/=a[i][i]; }}inline void solve(){ getfail(); build(); xy();}int main(){ scanf("%d%d%d",&n,&l,&m); for(int i=1;i<=m;i++) scanf("%d%d",&X,&Y),p[i]=X/(D)Y; for(int i=1;i<=n;i++){ scanf("%s",s+1); Ins(i); } solve(); for(int i=1;i<=n;i++) printf("%.2lf\n",a[dy[i]][cnt+1]); return 0;}