BZOJ 2553: [BeiJing2011]禁忌 – [AC自动机/DP/矩阵乘法]


题目传送门
>原文链接<

题解 :

对输入的子串建立Trie图,这样我们就可以直接在图上DP了。

  • 方程 :F[i][j]表示已经说了i个字符,在图上j点的概率。

  • 转移 :若son不是危险节点,F[i+1][son]+=F[i][j]\times temp 其中temp是说son这个字符的概率,等于\frac{1}{alphabet}

  • son是危险节点,那么走到它相当于匹配了一次禁忌串,可以统计答案再从根重新开始走

    由于匹配到每个危险节点的答案贡献都是1,那么期望可以通过计算概率和得到。

    但是len太大了,O(len)跑不下来。

    因为这是一张图,每次都走一步,我们可以考虑用邻接矩阵做矩阵乘法优化。

    每乘一次边表相当于走了一步。

    这样为了方便统计答案,我们需要建立一个虚拟汇点,每次向根转移的同时也转移到它。最后读取答案的时候直接读取它即可。

    注意本题卡精度,必须用long \;double,尤其是temp = 1/alphabet中的1也要强制转long\;double

代码 :

#include 
#include 
#include 
using namespace std;
#define f3 long double
const int N = 110;
char s[N];
int n, len, alphabet;
struct Mat {
    f3 a[N][N];
    Mat() {memset(a, 0, sizeof a);}
    f3* operator [] (int cur) {return a[cur];}
    void operator *= (Mat &b) {
        Mat c;
        for(int i = 0; i <= n; i ++ )
        for(int j = 0; j <= n; j ++ )
        for(int k = 0; k <= n; k ++ ) 
        c[i][j] += a[i][k]*b[k][j];
        *this = c;
    }
    Mat operator ^ (int y) {
        Mat I;
        for(int i = 0; i <= n; i ++ ) I[i][i] = 1;
        for(;y;y>>=1, *this *= *this) if(y&1) I *= *this;
        return I;
    }
}f;
struct Aho_Corasick_Automaton {
    int cnt, ch[N][26], fail[N];
    bool flg[N], vis[N]; queue q;
    void insert() {
        int p = 0;
        for(int i = 1; s[i]; i ++ ) {
            int &son = ch[p][s[i]-'a'];
            if(!son) son = ++cnt;
            p = son;
        }
        flg[p] = 1;
    }
    void getFail() {
        for(int i = 0; i < alphabet; i ++ ) if(ch[0][i]) q.push(ch[0][i]);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < alphabet; i ++ ) {
                if(ch[u][i]) fail[ch[u][i]] = ch[fail[u]][i], q.push(ch[u][i]);
                else ch[u][i] = ch[fail[u]][i];
            }
            flg[u] |= flg[fail[u]];
        }
    }
    void getF() {
        f3 tmp = (f3)1.0/alphabet;
        q.push(0); vis[0] = 1;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < alphabet; i ++ ) {
                if(!vis[ch[u][i]]) vis[ch[u][i]] = 1, q.push(ch[u][i]);
                if( flg[ch[u][i]]) f[u][n] += tmp, f[u][0] += tmp;
                else f[u][ch[u][i]] += tmp;
            }
        }
        f[n][n] = 1;
    }
}Trie;
int main() {
    scanf("%d%d%d", &n, &len, &alphabet);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%s", s+1);
        Trie.insert();
    }
    n = Trie.cnt+1;
    Trie.getFail();
    Trie.getF();
    printf("%.7f\n", (double)(f^len).a[0][n]);
    getchar(), getchar();
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注