[SDOI2017]硬币游戏

Description

周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。

大家纷纷觉得这个游戏非常符合同学们的特色，但只是扔硬币实在是太单调了。

同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币，其他同学记录下正反面情况。

用\(H\)表示正面朝上， 用\(T\)表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比如\(HTT\)表示第一次正面朝上，后两次反面朝上。

但扔到什么时候停止呢？大家提议，选出\(n\)个同学， 每个同学猜一个长度为\(m\)的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利。为了保证只有一个同学胜利，同学们猜的\(n\)个序列两两不同。

很快，\(n\)个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。

Input

第一行两个数 \(n\)、\(m\)。
接下来\(n\)行，每行一个长度为\(m\)的字符串，表示第\(i\)个同学猜的序列。

Output

输出\(n\)行，第\(i\)行表示第\(i\)个同学胜利的概率。选手输出与标准输出的绝对误差不超过\(10^{-6}\)即为正确。

Sample Input

3 3
THT
TTH
HTT

Sample Output

0.3333333333
0.2500000000
0.4166666667

HINT

对于\(10\%\)的数据，\(1\leqslant n,m\leqslant 3\)；
对于\(30\%\)的数据，\(1\leqslant n,m\leqslant 18\)；
对于另外\(20\%\)的数据，\(n=2\)；
对于\(100\%\)的数据，\(1\leqslant n,m\leqslant 300\)。

我们记\(P_i\)为第\(i\)名学生获胜的概率，同时我们会发现，可能存在某些序列是所有同学都没有猜对的。那么我们记\(P_0\)为没人获胜的概率。

很显然，我们从任意一个\(P_0\)串末尾加上串\(i\)，这样\(i\)就获胜了，所以有\(P_i=\frac{1}{2^m}P_0\)

但这样存在一个问题，我们从\(P_0\)转移到\(P_i\)的时候，可能会转移到\(P_j\)，再转移到\(P_i\)。如过串\(i\)的长度为\(k\)的前缀等于串\(j\)的后缀，那么我们可能在\(P_0\)后加上\(k\)位就到了\(j\)，再接上长为\(m-k\)的串得到\(i\)，此时的概率为\(\frac{1}{2^{m-k}}P_j\)

即：

\[P_i=\frac{1}{2^m}P_0-\sum\limits_{j=1}^n\sum\limits_{k=1}^m[\mathrm{prefix}(i,k)==\mathrm{suffix}(j,k)]\frac{1}{2^{m-k}}P_j \]

其中，\(\mathrm{prefix}(i,k)\)表示串\(i\)长度为\(k\)的前缀，\(\mathrm{suffix}(j,k)\)表示串\(j\)长度为\(k\)的后缀。

怎么统计？每个串跑个KMP，暴力判断就行。

然后，为了统计\(P_i\)占\(\sum\limits_{i=1}^nP_i\)的概率，我们加一个\(\sum\limits_{i=1}^nP_i=1\)即可

那这样就有\(n+1\)个变量，\(n+1\)个方程，高斯消元就好了。

/*program from Wolfycz*/
#include
#include
#include
#include
#include
#include
#include
#include
#define Fi first
#define Se second
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
templateinline T read(T x){
    int f=1; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x<0)	putchar('-'),x=-x;
    if (x>9)	print(x/10);
    putchar(x%10+'0');
}
const int N=3e2;
double Pow[N+10];
void Get_Nxt(int *a,int *nxt,int n){
    for (int i=2,j=0;i<=n;i++){
        while (j&&a[j+1]!=a[i]) j=nxt[j];
        if (a[j+1]==a[i])   j++;
        nxt[i]=j;
    }
}
void solve(int *x,int *y,int *nxt,int n,double &p){
    int j=0;
    for (int i=1;i<=n;i++){
        while (j&&x[j+1]!=y[i]) j=nxt[j];
        if (x[j+1]==y[i])   j++;
    }
    if (x==y)   j=nxt[j];
    while (j){
        p+=Pow[n-j];
        j=nxt[j];
    }
}
void Print(double *a,int n){
    for (int i=0;i<=n;i++)
        printf("%5g%c",a[i],i==n?'\n':' ');
}
char Coin[N+10];
int A[N+10][N+10],Nxt[N+10][N+10];
double B[N+10][N+10];
void Gauss(int n){
    for (int i=0;i<=n;i++){
        if (B[i][i]==0)
            for (int j=i+1;j<=n;j++)
                if (B[j][i]!=0)
                    for (int k=i;k<=n+1;k++)
                        swap(B[i][k],B[j][k]);
        double temp=B[i][i];
        for (int j=i;j<=n+1;j++)    B[i][j]/=temp;
        for (int j=0;j<=n;j++){
            if (i==j)   continue;
            double _temp=B[j][i];
            for (int k=0;k<=n+1;k++)
                B[j][k]-=B[i][k]*_temp;
        }
    }
}
int main(){
    Pow[0]=1;
    for (int i=1;i<=N;i++)  Pow[i]=Pow[i-1]/2;
    int n=read(0),m=read(0);
    for (int i=1;i<=n;i++){
        scanf("%s",Coin+1);
        for (int j=1;j<=m;j++)
            A[i][j]=Coin[j]=='T';
        Get_Nxt(A[i],Nxt[i],m);
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            solve(A[i],A[j],Nxt[i],m,B[i][j]);
    for (int i=1;i<=n;i++){
        B[i][0]-=Pow[m];
        B[i][i]+=1;
    }
    for (int i=1;i<=n;i++)  B[0][i]=1;
    B[0][n+1]=1;
    Gauss(n);
    for (int i=1;i<=n;i++)  printf("%.10lf\n",B[i][n+1]);
    return 0;
}
Source各省省选字符串KMP数学高斯消元

相关

标签