写代码天天出这些sb错误我真是服了，模版都写挂
AC机+高斯不难想到，但是复杂度太高了
发现有很多非结束点到达的概率也算了，好像很没有必要可以减少
然而怎么减少就不是我会的问题了
先假设一个人赢了以后还继续抛硬币
设pi表示i串被第一个抛出的概率，这就是答案
pn+1表示一直抛都抛不出的概率
假设现在要算瞎抛一些再加上第i个串的概率，那么首先这个值就有pn+1 * (1/2^m)
假如能够再用p来表示它就可以解方程了~
如果i长度为k的前缀和j的长度为k的后缀可以匹配，那么抛出j以后，想要搞出上面那个东西就只要乘(1/2^(m-k))
hash判一下就好
#include#include #include #include #include #include using namespace std;typedef long long LL;const int maxn=310;const int maxm=310;double mp[maxn][maxn],d[maxn];void gauss(int n){ for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) if(fabs(mp[j][i])>0) { for(int k=i;k<=n;k++)swap(mp[i][k],mp[j][k]); swap(d[i],d[j]); break; } for(int j=1;j<=n;j++) { if(i==j)continue; double rate=mp[j][i]/mp[i][i]; for(int k=i;k<=n;k++)mp[j][k]-=mp[i][k]*rate; d[j]-=d[i]*rate; } }}//--------------------------------------------------------------------------------------const int hbase=13;LL hmi[maxm];char ss[maxn][maxm];LL ha[maxn][maxm];LL gethash(int w,int l,int r){ return ha[w][r]-ha[w][l-1]*hmi[r-l+1];}double dBin[maxm];int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,m; scanf("%d%d",&n,&m); dBin[0]=1;for(int i=1;i<=m;i++)dBin[i]=dBin[i-1]/2.0; hmi[0]=1;for(int i=1;i<=m;i++)hmi[i]=hmi[i-1]*hbase; for(int i=1;i<=n;i++) { scanf("%s",ss[i]+1); for(int j=1;j<=m;j++) ha[i][j]=ha[i][j-1]*hbase+(ss[i][j]=='H'); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) for(int k=1;k<=m;k++) if(gethash(i,1,k)==gethash(j,m-k+1,m)) mp[i][j]+=dBin[m-k]; mp[i][n+1]=-dBin[m]; } for(int i=1;i<=n;i++)mp[n+1][i]=1; d[n+1]=1; gauss(n+1); for(int i=1;i<=n;i++)printf("%.10lf\n",d[i]/mp[i][i]); return 0;}