[HDU5955]Guessing the Dice Roll

Problem Description

There are N players playing a guessing game. Each player guesses a sequence consists of {1,2,3,4,5,6} with length L, then a dice will be rolled again and again and the roll out sequence will be recorded. The player whose guessing sequence first matches the last L rolls of the dice wins the game.

Input

The
first line is the number of test cases. For each test case, the first
line contains 2 integers N (1 ≤ N ≤ 10) and L (1 ≤ L ≤ 10). Each of the
following N lines contains a guessing sequence with length L. It is
guaranteed that the guessing sequences are consist of {1,2,3,4,5,6} and
all the guessing sequences are distinct.

Output

For each test case, output a line containing the winning probability of each player with the precision of 6 digits.

Sample Input

3
5 1
1
2
3
4
5
6 2
1 1
2 1
3 1
4 1
5 1
6 1
4 3
1 2 3
2 3 4
3 4 5
4 5 6

Sample Output

0.200000 0.200000 0.200000 0.200000
0.200000
0.027778 0.194444 0.194444 0.194444
0.194444 0.194444
0.285337 0.237781 0.237781 0.239102

对所有串建AC自动机，然后按照Trie图建立递推关系，转化成矩阵，用高斯消元解决带环的转移。

写起来略恶心，反正我是不想调了。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cmath>

using namespace std;

#define reg register

inline int read() {

    int res = ;char ch=getchar();bool fu=;

    while(!isdigit(ch))fu|=(ch=='-'),ch=getchar();

    while(isdigit(ch)) res=(res<<)+(res<<)+(ch^),ch=getchar();

    return fu?-res:res;

}

int T;

int n, L;

int nxt[][], fail[], danger[], tot, who[];

inline void ins(int *s, int id)

{

    int now = ;

    for (reg int i =  ; i <= L ; i ++)

        now = nxt[now][s[i]] ? nxt[now][s[i]] : nxt[now][s[i]] = ++tot;

    danger[now] = ;

    who[now] = id;

}

inline void Build()

{

    queue <int> q;

    for (reg int i =  ; i <=  ;i ++) if (nxt[][i]) q.push(nxt[][i]);

    while(!q.empty())

    {

        int x = q.front();q.pop();

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

            if (nxt[x][i]) fail[nxt[x][i]] = nxt[fail[x]][i], q.push(nxt[x][i]);

            else nxt[x][i] = nxt[fail[x]][i];

        danger[x] |= danger[fail[x]];

    }

}

long double a[][], ans[];

inline void Gauss()

{

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

    {

        int k = i;

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

            if (fabs(a[j][i]) > fabs(a[k][i])) k = j;

        if (k != i) swap(a[k], a[i]);

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

        {

            if (i == j) continue;

            long double r = a[j][i] / a[i][i];

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

                a[j][k] -= a[i][k] * r;

        }

    }

}

int main()

{

    T = read();

    while(T--)

    {

        memset(nxt, , sizeof nxt);

        memset(fail, , sizeof fail);

        memset(danger, , sizeof danger);

        tot = ;

        n = read(), L = read();

        int tmp[];

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

        {

            for (reg int j =  ; j <= L ; j ++) tmp[j] = read();

            ins(tmp, i);

        }

        Build();

        memset(a, , sizeof a);

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

        {

            a[i][i] -= 1.0;

            if (danger[i]) continue;

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

                a[nxt[i][j]][i] += 1.0 / 6.0;

        }

        a[][tot + ] = -1.0;

//        for(int i=0;i<=tot;i++,puts(""))

//            for(int j=0;j<=tot+1;j++) printf("%.2Lf ",a[i][j]);

        Gauss();

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

            if (danger[i]) ans[who[i]] = a[i][tot + ] / a[i][i];

        for (reg int i =  ; i < n ; i ++) printf("%.6Lf ", ans[i]);

        printf("%.6Lf\n", ans[n]);

    }

    return ;

}

巴特西

[HDU5955]Guessing the Dice Roll

最新文章

热门文章