[BZOJ2553][BEIJING2011]禁忌(AC自动机,概率动态规划,矩阵快速幂)

发布于 2018-03-24  65 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2553][BEIJING2011]禁忌(AC自动机,概率动态规划,矩阵快速幂)

Description

Magic Land上的人们总是提起那个传说:他们的祖先John在那个东方岛屿帮助Koishi与其姐姐Satori最终战平。而后,Koishi恢复了读心的能力……
如今,在John已经成为传说的时代,再次造访那座岛屿的人们却发现Koishi遇到了新麻烦。
这次她遇到了Flandre Scarlet——她拥有可以使用禁忌魔法而不会受到伤害的能力。
为了说明什么是禁忌魔法及其伤害,引入以下概念:
1.字母集A上的每个非空字符串对应了一个魔法。其中A是包含了前alphabet个小写字母的集合。
2.有一个集合T,包含了N个字母集A上的字符串T中的每一串称为一个禁忌串(Taboo string)
3.一个魔法,或等价地,其对应的串s因为包含禁忌而对使用者造成的伤害按以下方式确定:

把s分割成若干段,考虑其中是禁忌串的段的数目,不同的分割可能会有不同的数目,其最大值就是这个伤害。

由于拥有了读心的能力,Koishi总是随机地使用Flandre Scarlet的魔法,可以确定的是,她的魔法正好对应字母集A上所有长度为len的串。
但是,Flandre Scarlet所使用的一些魔法是带有禁忌的,由于其自身特性,她可以使用禁忌魔法而不受到伤害,而Koishi就不同了。可怜的Koishi每一次使用对方的魔法都面临着受到禁忌伤害的威胁。
你现在需要计算的是如果Koishi使用对方的每一个魔法的概率是均等的,那么每一次随机使用魔法所受到的禁忌伤害的期望值是多少。

Tag

AC自动机,概率动态规划,矩阵快速幂

解决思路

首先,如果一个串包含了其它的串,那么这个串的分割方式一定不会更优,所以先去掉这些包含了其它串的字符串。
然后怎么分割呢?其实就贪心地从头往后匹配,如果当前已经遇到一个完整的在字符集合中的字符串就权值 +1,然后重新开始匹配。由于我们已经去掉了包含关系,所以这样做是对的。
然后考虑如何转移。设 F[i][j] 表示生成到第 i 位,当前在 AC 自动机的第 j 位置,那么向它的每一个字符集内的儿子等概率转移,若儿子不是字符串集合末尾,则直接转移;否则,不向儿子转移转而向根节点 0 号转移,这意味着找到了一个匹配,所以要从头开始匹配,并且同时要把这个期望转移到答案中。
考虑到生成串的长度比较大而字符集大小和字符串总长都比较小,所以用矩阵快速幂优化转移。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=10;
const int maxLen=20;
const int maxNode=maxN*maxLen;
const int maxAlpha=27;
const int inf=2147483647;

class Trie
{
public:
    int end,fail;
    int son[maxAlpha];
};

class Matrix
{
public:
    ld M[maxNode][maxNode];
};

int n,len,alpha,nodecnt;
char str[maxLen];
Trie T[maxNode];
int Queue[maxNode];
Matrix Ans,Ret;

void Insert(char *str);
void GetFail();
void Mul1();
void Mul2();

int main()
{
    scanf("%d%d%d",&n,&len,&alpha);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        Insert(str);
    }
    GetFail();//构建AC自动机
    ld dx=(ld)1/(ld)alpha;//等概率转移
    for (int i=0;i<=nodecnt;i++)
    {
        if (T[i].end) for (int j=0;j<alpha;j++) T[i].son[j]=0;//当是单词末尾,则不需要转移
        if (T[i].end) continue;
        for (int j=0;j<alpha;j++)
            {
                if (T[T[i].son[j]].end) Ret.M[i][0]+=dx,Ret.M[i][nodecnt+1]+=dx;//当儿子是单词末尾,则向根节点转移,同时转移到一个保存答案的地方
                else Ret.M[i][T[i].son[j]]+=dx;//否则,等概率转移
            }
    }
    Ret.M[nodecnt+1][nodecnt+1]=1;//这里用矩阵中的nodecnt+1这一位保存答案
    Ans.M[0][0]=1;//矩阵快速幂转移
    while (len)
    {
        if (len&1) Mul1();
        Mul2();
        len=len>>1;
    }
    printf("%.10lf\n",(double)Ans.M[0][nodecnt+1]);//输出答案
    return 0;
}

void Insert(char *str)
{
    int len=strlen(str+1);
    int now=0;
    for (int i=1;i<=len;i++)
    {
        if (T[now].son[str[i]-'a']==0) T[now].son[str[i]-'a']=++nodecnt;
        now=T[now].son[str[i]-'a'];
        if (T[now].end) break;
    }
    T[now].end=1;
    return;
}

void GetFail()
{
    int h=0,t=0;
    for (int i=0;i<alpha;i++) if (T[0].son[i]) Queue[++h]=T[0].son[i];
    while (t!=h)
    {
        int u=Queue[++t];
        for (int i=0;i<alpha;i++)
            if (T[u].son[i])
            {
                T[T[u].son[i]].fail=T[T[u].fail].son[i];
                Queue[++h]=T[u].son[i];
                T[T[u].son[i]].end|=T[T[T[u].fail].son[i]].end;
            }
            else T[u].son[i]=T[T[u].fail].son[i];
    }
    return;
}

ld Baup[maxNode][maxNode];

void Mul1()
{
    int sz=nodecnt+1;
    for (int i=0;i<=sz;i++) Baup[0][i]=Ans.M[0][i],Ans.M[0][i]=0;
    for (int j=0;j<=sz;j++)
        for (int k=0;k<=sz;k++)
            Ans.M[0][j]=Ans.M[0][j]+Baup[0][k]*Ret.M[k][j];
    return;
}

void Mul2()
{
    int sz=nodecnt+1;
    for (int i=0;i<=sz;i++) for (int j=0;j<=sz;j++) Baup[i][j]=Ret.M[i][j],Ret.M[i][j]=0;
    for (int i=0;i<=sz;i++)
        for (int j=0;j<=sz;j++)
            for (int k=0;k<=sz;k++)
                Ret.M[i][j]=Ret.M[i][j]+Baup[i][k]*Baup[k][j];
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2553][BEIJING2011]禁忌(AC自动机,概率动态规划,矩阵快速幂)


HNCJ OIer