【BZOJ4820】[SDOI2017]硬幣游戲（高斯消元）

題面

BZOJ
洛谷

題解

第一眼的感覺就是構\(AC\)自動機之后直接高斯消元算概率，這樣子似乎就是\(BZOJ1444\)了。然而點數太多了，三方的消元沒法做。
考慮如何優化點數，首先我們的所有點可以分為兩種，一種是終止節點，另外一種則不是。
既然現在要某一個串出現，因此我們唯一需要考慮的是到達終止節點的情況。設\(f_i\)表示到達第\(i\)個串的終止位置，并且沒有到達過其他終止節點的概率，也就是第\(i\)個串的答案。設\(f_0\)表示沒有到達任何一個串終止位置的概率。
那么顯然的，要到達當前位置，我們一種可行的方法就是在沒有匹配上任何一個串的串后面接上當前串，那么概率就是\(f_0*\frac{1}{2^m}\)，然而這個東西顯然會比\(f_i\)要大，因為這個終止串再接上當前串可能包含了其他的串\(j\)，而\(f_0\)表示的串沒有匹配上任何一個串，意味著\(j\)的后綴是\(i\)的前綴。那么考慮所有其他串與當前串前后綴的匹配長度\(k\)，我們可以列出方程：
\[f_0*\frac{1}{2^m}=f_i+\sum_j f_j*\frac{1}{2^{m-k}}\]
而然這樣子是\(n+1\)元，\(n\)個方程，再利用\(\sum f_i=1\)補足最后一個方程即可。
好神仙啊。

#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define ll long long #define ull unsigned long long #define MAX 320 const ull base=233; inline int read() {int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x; } int n,m;char ch[MAX]; ull h[MAX][MAX],pw[MAX]; ull geths(int x,int l,int r){return h[x][r]-h[x][l-1]*pw[r-l+1];} double g[MAX][MAX],bin[MAX]; void Guass() {for(int i=0;i<=n;++i){int p=i;for(int j=i+1;j<=n;++j)if(fabs(g[j][i])>fabs(g[p][i]))p=j;swap(g[p],g[i]);double t=g[i][i];for(int j=i;j<=n+1;++j)g[i][j]/=t;for(int j=i+1;j<=n;++j){double t=g[j][i];for(int k=0;k<=n+1;++k)g[j][k]-=g[i][k]*t;}}for(int i=n;i;--i){g[i][n+1]/=g[i][i];for(int j=i-1;j;--j)g[j][n+1]-=g[i][n+1]*g[j][i];} } int main() {n=read();m=read();pw[0]=bin[0]=1;for(int i=1;i<=m;++i)pw[i]=pw[i-1]*base,bin[i]=bin[i-1]/2;for(int i=1;i<=n;++i){scanf("%s",ch+1);for(int j=1;j<=m;++j)h[i][j]=h[i][j-1]*base+ch[j];}g[0][n+1]=1;for(int i=1;i<=n;++i){g[0][i]=1;g[i][0]=-bin[m];for(int j=1;j<=n;++j)for(int k=1;k<=m;++k)if(geths(i,1,k)==geths(j,m-k+1,m))g[i][j]+=bin[m-k];}Guass();for(int i=1;i<=n;++i)printf("%.10lf\n",g[i][n+1]);return 0; }

轉載于:https://www.cnblogs.com/cjyyb/p/10076926.html

總結

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

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