题解 P3706 【[SDOI2017]硬币游戏】
Kelin
2018-04-06 22:22:57
## [题意](https://blog.csdn.net/BeNoble_/article/details/79837558)
给你一个字符串集
构造一个$01$串$S,$每个位置等概率的插入$01$
问字符串集中每个字符串最先出现在构造的串中的概率
---
怎么感觉和[$[JSOI2009]$有趣的游戏](https://blog.csdn.net/benoble_/article/details/79827083)"一模一样"
写完交一发只有$40ptsTLE,$原来这题是[$[JSOI2009]$有趣的游戏](https://blog.csdn.net/benoble_/article/details/79827083)数据范围的加强版
---
## 题解
$TLE$原因在于方程个数的$nm$的,这样显然是不行的
考虑到合法状态其实只有$n$个$,$其余的状态可以合并成一个状态——"不合法的状态"
如果能这样列出方程$,$那么复杂度就是$O(n^3)$是可以接受的
设$S$为一种不合法的状态(即没人赢)$,A=101,B=110$
>引理:构造出一个长的$l$特定$01$串的概率是$\frac1{2^l}$
**到$S+101$状态一定会停止游戏,但不一定要等到$101$加完才停止**
如果$S$的后缀是$1$或者$10$那么就会提前结束
也就是说可能会有这些情况
$$S101=(S+A)+(S'+A+01)+(S''+B+1)$$
其中$S=S'+10=S''+1$
根据上面的引理$,$可以得到方程$\frac18S=(1+\frac14)A+\frac12B$
也就是说对与每一个$S+x_i,len(x_i)=m$
如果$x_j$存在长度为$a$的后缀能匹配$x_i$的前缀$,$那么就有$\frac1{2^{m-a}}$的概率提前结束
设$pre_{a,x_i}$表示$x_i$长度为$a$的前缀$,$后缀同理
写成通式就是
$$x_i+\sum_{j=1}^n\sum_{a=1}^m[pre_{a,x_i}=suf_{a,x_j}]\frac1{2^{m-a}}x_j=\frac1{2^m}S$$
这样我们就只有$n+1$个方程了
最后再把其中一个方程替换为$\sum x_i=1$
至于如何快速匹配前缀和后缀可以~~根据套路~~使用字符串哈希
```
#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=305,sed=time(0),S=(1<<30)-1;
const double eps=1e-10,P=0.5;
typedef int arr[N];
typedef double db;
int n,m;arr pw,pre[N],suf[N];db p[N],ans[N],G[N][N];char s[N];
inline int cmp(const db x){return fabs(x)<eps?0:x<0?-1:1;}
inline void Gauss(int n){
db t;int mx;
fp(i,1,n){mx=i;
fp(j,i,n)if(cmp(G[mx][i]-G[j][i]))mx=j;
if(mx^i)swap(G[mx],G[i]);
fp(j,i+1,n)if(cmp(G[j][i])){
t=G[j][i]/G[i][i];
fp(k,i,n+1)G[j][k]-=G[i][k]*t;
}
}
fd(i,n,1){
fp(j,i+1,n)G[i][n+1]-=G[i][j]*ans[j];
ans[i]=G[i][n+1]/G[i][i];
}
}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d",&n,&m);
p[0]=pw[0]=1;
fp(i,1,m)pw[i]=pw[i-1]*sed&S,p[i]=p[i-1]*P;
fp(i,1,n){
scanf("%s",s+1);
fp(j,1,m)pre[i][j]=(pre[i][j-1]+s[j]*pw[j])&S;
fp(j,1,m)suf[i][j]=(suf[i][j-1]+s[m-j+1])*sed&S;
}
fp(i,1,n)fp(j,1,n)fp(k,1,m)
if(pre[i][k]==suf[j][k])
G[i][j]+=p[m-k];
fp(i,1,n)G[i][n+1]=-p[m],G[n+1][i]=1;G[n+1][n+2]=1;
Gauss(n+1);
fp(i,1,n)printf("%.10lf\n",ans[i]);
return 0;
}
```
当然如果你觉得慢的话我也可以用$AC$自动机来求匹配
这个嘛$,$怎么开心怎么玩是把
```
#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=305,M=1e5+5;
const double eps=1e-10,P=0.5;
typedef int arr[M];
typedef double db;
struct eg{int nx,to;}e[M];
int n,m,ce,Cnt,ch[M][2];arr fi,mx,pos,fail;db p[N],ans[N],G[N][N];char s[N];
inline void add(int u,int v){static int ce=0;e[++ce]={fi[u],v},fi[u]=ce;}
#define v (ch[u][i])
inline void ins(int p){
scanf("%s",s+1);int u=0,i;
fp(j,1,m)i=s[j]=='H',mx[!v?v=++Cnt:v]=mx[u]+1,add(u=v,p);
pos[p]=u;
}
inline void gf(){
static int q[M];int h=1,t=0,u=0,i;
fp(i,0,1)if(v)q[++t]=v;
while(h<=t)for(u=q[h++],i=0;i<2;++i)v?fail[q[++t]=v]=ch[fail[u]][i]:v=ch[fail[u]][i];
}
#undef v
inline void calc(int x){
for(int u=pos[x];u;u=fail[u])
go(u)G[v][x]+=p[m-mx[u]];
}
inline int cmp(const db x){return fabs(x)<eps?0:x<0?-1:1;}
inline void Gauss(int n){
db t;int mx;
fp(i,1,n){mx=i;
fp(j,i,n)if(cmp(G[mx][i]-G[j][i]))mx=j;
if(mx^i)swap(G[mx],G[i]);
fp(j,i+1,n)if(cmp(G[j][i])){
t=G[j][i]/G[i][i];
fp(k,i,n+1)G[j][k]-=G[i][k]*t;
}
}
fd(i,n,1){
fp(j,i+1,n)G[i][n+1]-=G[i][j]*ans[j];
ans[i]=G[i][n+1]/G[i][i];
}
}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d",&n,&m);
p[0]=1;fp(i,1,m)p[i]=p[i-1]*P;
fp(i,1,n)ins(i);gf();
fp(i,1,n)calc(i);
fp(i,1,n)G[i][n+1]=-p[m],G[n+1][i]=1;G[n+1][n+2]=1;
Gauss(n+1);
fp(i,1,n)printf("%.10lf\n",ans[i]);
return 0;
}
```