BZOJ 4820 [Sdoi2017]硬币游戏 —

做法太神了，理解不了。

自己想到的是建出AC自动机然后建出矩阵然后求逆计算，感觉可以过$40%$

用一个状态$N$表示任意一个位置没有匹配成功的概率和。

每种匹配不成功的情况都是等价的。

然后我们强制在后面加上长度为m的01串，那么这个串的概率是一定的。

然后考虑加上的这些字符还能拼成什么串，因为状态$N$的末尾是不确定的。

如果另外一个串的后缀等于这个串的前缀的话，是可能带来影响的。

所以计算出影响的概率，然后高斯消元即可。

然而有一个问题，N的概率最后消出来代表什么意思啊，是指期望的长度吗？

希望各位dalao不吝赐教。

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define mp make_pair

int n,m,s[305][305],str[605],fail[605];

char ss[305];

double a[305][305],pw[305],ans[305];

void kmp()

{

//  F(i,1,2*m) printf("%d ",str[i]); printf("\n");

    str[0]=-1;

    memset(fail,0,sizeof fail);

    for (int i=2,j=0;i<=2*m;++i)

    {

        while (j&&str[i]!=str[j+1]) j=fail[j];

        if (str[j+1]==str[i]) j++;

        fail[i]=j;

    }

//  F(i,1,2*m) printf("%d ",fail[i]);printf("\n");

}

void solve(int x)

{

    a[x][x]=1;F(i,1,m) str[i]=s[x][i];

    F(y,1,n)// if (y!=x)

    {

        F(i,1,m) str[i+m]=s[y][i]; kmp();

        int now=fail[2*m];

//      printf("now is %d\n",now);

        while (now>=m) now=fail[now];

        while (now)

        {

//          printf("Can %d\n",now);

            a[x][y]+=pw[m-now];

            now=fail[now];

        }

    }

    a[x][n+1]=-pw[m]; a[x][n+2]=0;

}

void Gauss()

{

    F(i,1,n+1)

    {

        int tmp=i;

        F(j,i+1,n+1) if (fabs(a[j][i])>fabs(a[i][i])) tmp=j;

        if (tmp!=i) F(j,1,n+2) swap(a[i][j],a[tmp][j]);

        F(j,1,n+1) if (j!=i)

        {

            double t=a[j][i]/a[i][i];

            F(k,1,n+2) a[j][k]-=t*a[i][k];

        }

//      F(i,1,n+1){F(j,1,n+2)printf("%.3f ",a[i][j]);printf("\n");}

    }

    F(i,1,n+1) ans[i]=a[i][n+2]/a[i][i];

    F(i,1,n) printf("%.10lf\n",ans[i]);

}

int main()

{

//  freopen("in.txt","r",stdin);

    scanf("%d%d",&n,&m);

    pw[0]=1;F(i,1,m)pw[i]=pw[i-1]*0.5;

    F(i,1,n){scanf("%s",ss+1);F(j,1,m) s[i][j]=(ss[j]=='H');}

    F(i,1,n) solve(i);

    F(i,1,n) a[n+1][i]=1; a[n+1][n+2]=1;

//  F(i,1,n+1){F(j,1,n+2)printf("%.3f ",a[i][j]);printf("\n");}

    Gauss();

}

巴特西

BZOJ 4820 [Sdoi2017]硬币游戏 ——期望DP 高斯消元

最新文章

热门文章