题解 P3706 【[SDOI2017]硬币游戏】

Kelin · 2018-04-06 22:22:57 · 题解

题意

给你一个字符串集

构造一个01串S,每个位置等概率的插入01

问字符串集中每个字符串最先出现在构造的串中的概率

怎么感觉和[JSOI2009]有趣的游戏"一模一样"

写完交一发只有40ptsTLE,原来这题是[JSOI2009]有趣的游戏数据范围的加强版

题解

考虑到合法状态其实只有$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;
}