題意：給 $n$ 個長度為 $m$ 的 01 串，一個 01 串初始為空，不斷隨機一個字符加在后面，當出現給定的 $n$ 個串中的一個時停止。分別求在 $n$ 個串處停止的概率。

考場思路歷程：

顯然建出 AC 自動機（flag++）

然后發現變成了 CF113D Museum，有個 $O((nm{)}^3)$ 的做法

考慮方程有什么特殊性質

在 trie 樹上要么往下走一步，要么往上走

也就是說是 Linear Creature 的二叉樹版。

然后發現要求任意點出發所有點的出現次數期望，不弱于原問題，無法推廣。

矩陣中有值的位置是 $O(n)$ 的。

但是是豎著放的，沒時間了沒仔細想。

正解：

既然方程的特殊性質不好優化，考慮直接想辦法求出 $n$ 個答案的方程。

設 $P_i$ 為第 $i$ 個串的期望出現次數，即概率，即答案。特別地，記 $P_0$ 為所有未終止狀態（即 AC 自動機上無標記的點）的期望長度，即期望出現次數之和。

考慮對 $P_i$ 建立方程。

無視掉走到就終止的條件，考慮所有未終止狀態，往后面按 $S_i$ 走 $m$ 步，得到了一個狀態的可重集，注意有些狀態可能不合法但也算在內（不過都在 AC 自動機上）。

從這個過程來考慮，因為限制了后面 $m$ 步的走法，這些狀態的期望出現次數之和就是 $\frac{1}{2^m}{P}_0$。

如果過程中沒有到過終止狀態，那么就是 $P_i$。否則我們枚舉第一個終止狀態以及是走了幾步達到的，設達到的串為 $S_j$（注意 $i,j$ 可以相等），是走了 $k$ 步后達到的，因為所有串長相等，所以此時一定是合法狀態。然后就在 $P_j$ 的基礎上繼續走 $m?k$ 步。

得到方程：

$$\frac{1}{2^m}{P}_0=P_i+\sum _{j=1}^n\sum _{k=1}^{m?1}[S_{i,1～k}=S_{j,m?k+1～m}]\frac{P_j}{2^{m?k}}$$

然后對每對 $i,j$ 跑個 kmp 就可以了。

什么？終止狀態的長度小于 $m?k$ 怎么辦？反正只有有限個，忽略好了。

然后再加一個 ${\sum }_{i=1}^n{P}_i=1$ 的方程來得到數值，一共有 $n+1$ 個方程和 $n+1$ 個未知數，高斯消元解出來就可以了。

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cmath> #define MAXN 305 using namespace std; char s[MAXN][MAXN]; int n,m; double pw[MAXN],a[MAXN][MAXN]; int nxt[MAXN]; void gauss(int n) {for (int i=0;i<n;i++){int pos=i;for (int j=i+1;j<=n;j++) if (fabs(a[j][i])>fabs(a[pos][i])) pos=j;if (pos>i) swap(a[i],a[pos]);for (int j=0;j<=n;j++)if (i!=j){double t=a[j][i]/a[i][i];for (int k=i;k<=n;k++) a[j][k]-=t*a[i][k];}} } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",s[i]+1);pw[0]=1;for (int i=1;i<=m;i++) pw[i]=pw[i-1]/2;for (int i=1;i<=n;i++){a[i][0]=-pw[m];a[i][i]+=1;int pos=0;for (int j=2;j<=m;j++){while (pos&&s[i][j]!=s[i][pos+1]) pos=nxt[pos];if (s[i][j]==s[i][pos+1]) nxt[j]=++pos;else nxt[j]=0;}for (int j=1;j<=n;j++){pos=0;for (int k=1;k<=m;k++){while (pos&&s[j][k]!=s[i][pos+1]) pos=nxt[pos];if (s[j][k]==s[i][pos+1]) ++pos;}if (i==j) pos=nxt[pos];for (;pos;a[i][j]+=pw[m-pos],pos=nxt[pos]);}a[n+1][i]=1;}a[n+1][n+1]=1;gauss(n+1);for (int i=1;i<=n;i++) printf("%.10f\n",a[i][n+1]/a[i][i]);return 0; }

總結

以上是生活随笔為你收集整理的【SDOI2017】硬币游戏【KMP】【概率期望】【高斯消元】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。