含高斯消元模板

2016沈陽區(qū)域賽http://acm.hdu.edu.cn/showproblem.php?pid=5955

Guessing the Dice Roll

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1632????Accepted Submission(s): 480

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

?

Source 2016ACM/ICPC亞洲區(qū)沈陽站-重現(xiàn)賽（感謝東北大學(xué)）

?

Recommend jiangzijing2015 題意： 有n個人猜擲骰子的序列。給定序列長度是l。只要n個人中的一個序列出現(xiàn)了，這個人就贏了游戲結(jié)束。問他們獲勝的概率是多少。 思路： 沒有想到是AC自動機。但是其實他本質(zhì)就是在一個自動機的不同狀態(tài)之間轉(zhuǎn)轉(zhuǎn)轉(zhuǎn)，看最后轉(zhuǎn)到哪個狀態(tài)上去。 對這幾個序列建立了AC自動機之后，就可以列出他們互相之間轉(zhuǎn)移的概率方程了。然后解方程就可以得到每個人獲勝的概率。 矩陣中的第\(j\)行表示的就是關(guān)于\(j\)這個狀態(tài)的方程。\(a[j][i]\)表示由狀態(tài)\(i\)轉(zhuǎn)移到狀態(tài)\(j\)的概率。 \(a[i][i]\)本身應(yīng)該放在方程的右邊，所以他是\(-1\) 根節(jié)點是比較特殊的，我們需要再設(shè)置一個虛擬節(jié)點，虛擬節(jié)點到根節(jié)點的概率是1，他也應(yīng)該作為根節(jié)點初始時的概率放在右邊。 1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstdlib> 5 #include<cstring> 6 #include<algorithm> 7 #include<queue> 8 #include<set> 9 using namespace std; 10 typedef long long LL; 11 #define N 100010 12 #define pi 3.1415926535 13 14 int n, l, t; 15 const int maxn = 105; 16 struct trie{ 17 int son[7]; 18 int ed; 19 int fail; 20 }AC[maxn]; 21 int tot = 0; 22 int fp[11]; 23 24 void build(int s[], int id) 25 { 26 int now = 0; 27 for(int i = 0; i < l; i++){ 28 if(AC[now].son[s[i]] == 0){ 29 AC[now].son[s[i]] = ++tot; 30 } 31 now = AC[now].son[s[i]]; 32 } 33 AC[now].ed = id; 34 fp[id] = now; 35 } 36 37 void get_fail() 38 { 39 queue<int>que; 40 for(int i = 1; i <= 6; i++){ 41 if(AC[0].son[i] != 0){ 42 AC[AC[0].son[i]].fail = 0; 43 que.push(AC[0].son[i]); 44 } 45 } 46 47 while(!que.empty()){ 48 int u = que.front(); 49 que.pop(); 50 for(int i = 1; i <= 6; i++){ 51 if(AC[u].son[i] != 0){ 52 AC[AC[u].son[i]].fail = AC[AC[u].fail].son[i]; 53 que.push(AC[u].son[i]); 54 } 55 else{ 56 AC[u].son[i] = AC[AC[u].fail].son[i]; 57 } 58 } 59 } 60 } 61 62 double a[maxn][maxn], x[maxn]; 63 const double eps = 1e-10; 64 int equ, var; 65 void gauss() 66 { 67 equ = var = tot + 1; 68 int i,j,k,col,max_r; 69 for(k=0,col=0;k<equ&&col<var;k++,col++) 70 { 71 max_r=k; 72 for(i=k+1;i<equ;i++) 73 { 74 if(fabs(a[i][col] )>fabs(a[max_r][col] ) ) max_r=i; 75 } 76 if(fabs(a[max_r][col])<eps ) return; 77 if(k!=max_r) 78 { 79 for(j=col;j<=var;j++) swap(a[k][j],a[max_r][j] ); 80 } 81 for(j=col+1;j<=var;j++) a[k][j]/=a[k][col]; 82 83 a[k][col]=1; 84 85 for(i=0;i<equ;i++) if(i!=k) 86 { 87 for(j=col+1;j<=var;j++) a[i][j]-=a[k][j]*a[i][col]; 88 89 a[i][col]=0; 90 } 91 } 92 for(i=0;i<equ;i++) x[i]=a[i][var]; 93 return; 94 } 95 96 int main() 97 { 98 scanf("%d", &t); 99 while(t--){ 100 for(int i = 0; i <= tot; i++){ 101 AC[i].fail = 0; 102 AC[i].ed = 0; 103 for(int j = 0; j < 7; j++){ 104 AC[i].son[j] = 0; 105 } 106 } 107 tot = 0; 108 109 scanf("%d%d", &n, &l); 110 for(int i = 1; i <= n; i++){ 111 int tmp[11]; 112 for(int j = 0; j < l; j++){ 113 scanf("%d", &tmp[j]); 114 } 115 build(tmp, i); 116 } 117 get_fail(); 118 119 memset(a, 0, sizeof(a)); 120 memset(x, 0, sizeof(x)); 121 for(int i = 0; i <= tot; i++)a[i][i] = -1.0; 122 for(int i = 0; i <= tot; i++){ 123 if(AC[i].ed == 0){ 124 for(int j = 1; j <= 6; j++){ 125 int to = AC[i].son[j]; 126 a[to][i] += 1.0 / 6; 127 } 128 } 129 130 } 131 132 a[0][tot + 1] = -1.0;//虛擬節(jié)點 133 gauss(); 134 for(int i = 1; i <= n; i++){ 135 printf("%.6f", x[fp[i]]); 136 if(i == n){ 137 printf("\n"); 138 } 139 else{ 140 printf(" "); 141 } 142 } 143 144 //cout<<"yes"<<endl; 145 } 146 147 return 0; 148 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wyboooo/p/9951242.html

總結(jié)

以上是生活随笔為你收集整理的hdu5955 Guessing the Dice Roll【AC自动机】【高斯消元】【概率】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。