bzoj 2553 [BeiJing2011]禁忌——AC自动机+概率DP+矩阵

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2553

看了题解才会……

首先，给定一个串，最好的划分方式是按禁忌串出现的右端点排序，遇到能填的就填上。在 AC 自动机上就是一旦能走到一个禁忌串的终止节点，就 ans++ 并走到根去。

考虑怎么把 ans++ 也体现在矩阵乘法里。而且还要期望……

只要在矩阵里填上概率，最后就能算出期望了。体现 ans++ 的话，就是在 “从当前节点到根” 的同时给 “从当前节点到 tot ” 的概率也加上 \( \frac{1}{alphabet} \) 即可。

最后就看一下乘了 len 次之后从根走到 tot 点的值即可。

听说要开 long double 。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define db long double

using namespace std;

const int N=,K=;

int n,m,alp,tot=,c[N][K],fl[N],q[N]; db p;

char ch[N]; bool en[N];

struct Mtr{

  db a[N][N];

  Mtr(){for(int i=;i<=tot;i++)for(int j=;j<=tot;j++)a[i][j]=;};

  Mtr operator* (const Mtr &b)const

  {

    Mtr c;

    for(int i=;i<=tot;i++)

      for(int k=;k<=tot;k++)

    for(int j=;j<=tot;j++)

      c.a[i][j]+=a[i][k]*b.a[k][j];

    return c;

  }

}t,ans;

void get_fl()

{

  int he=,tl=;

  for(int j=;j<alp;j++)

    if(c[][j])q[++tl]=c[][j],fl[c[][j]]=;

    else c[][j]=;

  while(he<tl)

    {

      int k=q[++he]; if(en[fl[k]])en[k]=;

      for(int j=;j<alp;j++)

    {

      if(c[k][j])

        {

          int cr=fl[k];

          while(cr&&!c[cr][j])cr=fl[cr];

          if(c[cr][j])fl[c[k][j]]=c[cr][j];

          else fl[c[k][j]]=;

          q[++tl]=c[k][j];

        }

      else

        {

          int cr=fl[k];

          while(cr&&!c[cr][j])cr=fl[cr];

          if(c[cr][j])c[k][j]=c[cr][j];

          else c[k][j]=;

        }

    }

    }

}

int main()

{

  scanf("%d%d%d",&n,&m,&alp); p=1.0/alp;

  for(int i=;i<=n;i++)

    {

      scanf("%s",ch+);

      int d=strlen(ch+), cr=;

      for(int j=;j<=d;j++)

    {

      int w=ch[j]-'a';

      if(!c[cr][w])c[cr][w]=++tot;

      cr=c[cr][w];

    }

      en[cr]=;

    }

  get_fl(); tot++; t.a[tot][tot]=;

  for(int i=;i<tot;i++)

    for(int j=;j<alp;j++)

      {

    if(en[c[i][j]]){ t.a[i][]+=p; t.a[i][tot]+=p;}

    else t.a[i][c[i][j]]+=p;

      }

  ans=t; m--;

  while(m)

    {

      if(m&)ans=ans*t; t=t*t;m>>=;

    }

  printf("%.10Lf\n",ans.a[][tot]);

  return ;

}

巴特西

bzoj 2553 [BeiJing2011]禁忌——AC自动机+概率DP+矩阵

最新文章

热门文章