Luogu

LOJ

分析

首先你需要看懂这篇题解。

设 $f_{i,j}$ 表示长度为 $i$ 时出现 $j$ 结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。

设 $f_{i,j}$ 的概率生成函数为 $F_i(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。

设 $a_{i,j,k}$ 表示 $s_{i}[1..k]$ 是否等于 $s_j[m-k+1..m]$ 。

可以得到这样一个式子
$$
G(x)\left(\frac{x}{2}\right)^m=\sum_{k=1}^m\left(\frac{x}{2}\right)^{m-k}\sum_{j=1}^n F_j(x)a_{i,j,k}
$$
把 $x=1$ 代入并化简得到
$$
G(1)=\sum_{k=1}^m2^k\sum_{j=1}^nF_i(1)a_{i,j,k}
$$
这样子相当于 $n+1$ 个变量 $n$ 个方程，似乎解不出的样子。

但是冷静分析后发现，还有这样一个式子
$$
\sum_{i=1}^nF_i(1)=1
$$
那么就可以高斯消元了。

至于 $a$ 怎么求，可以用 hash 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef unsigned long long ull;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300+10;
const ull BASE=2;

char str[N];
int n,m,s[N][N],a[N][N][N];
ull pw[N],h[N][N];
double pw2[N],A[N][N],B[N],C[N];

inline ull gethash(int id,int l,int r) {
    return h[id][r]-h[id][l-1]*pw[r-l+1];
}

inline void Gauss(int n) {
    for (re int i=1;i<=n;++i) {
        int p=i;
        for (re int j=i+1;j<=n;++j)
            if (fabs(A[j][i])>fabs(A[p][i])) p=j;
        if (i!=p) swap(A[i],A[p]),swap(B[i],B[p]);
        for (re int j=1;j<=n;++j) {
            if (i==j) continue;
            double rate=A[j][i]/A[i][i];
            for (re int k=1;k<=n;++k) A[j][k]-=rate*A[i][k];
            B[j]-=rate*B[i];
        }
    }
    for (re int i=1;i<=n;++i) C[i]=B[i]/A[i][i];
} 

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) {
        scanf("%s",str+1);
        for (re int j=1;j<=m;++j) s[i][j]=str[j]=='T';
    }

    for (re int i=pw2[0]=1;i<=m;++i) pw2[i]=pw2[i-1]*2;
    for (re int i=pw[0]=1;i<=m;++i) pw[i]=pw[i-1]*BASE;
    for (re int i=1;i<=n;++i) {
        h[i][0]=1;
        for (re int j=1;j<=m;++j) h[i][j]=h[i][j-1]*BASE+s[i][j];
    }

    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            for (re int k=1;k<=m;++k)
                a[i][j][k]=gethash(i,1,k)==gethash(j,m-k+1,m);

    for (re int i=1;i<=n;++i) {
        for (re int j=1;j<=n;++j)
            for (re int k=1;k<=m;++k)
                A[i][j]+=pw2[k]*a[i][j][k];
        A[i][n+1]=-1,B[i]=0;
    }
    for (re int i=1;i<=n;++i) A[n+1][i]=1;
    A[n+1][n+1]=0,B[n+1]=1;

    Gauss(n+1);
    for (re int i=1;i<=n;++i) printf("%.10lf\n",C[i]);
    return 0;
}
最后修改：2021 年 03 月 23 日 10 : 00 PM
© 允许规范转载