\(\mathscr{Description}\)
Link.
给定 \(n\) 个长度为 \(m\) 且两两不同的字符串 \(S_{1..n}\), 字符集 \(|\Sigma|=2\). 各位置独立在 \(\Sigma\) 中均匀随机, 生成一个足够长的字符串 \(T\), 对于每个 \(S_i\), 求 \(S_i\) 在 \(T\) 中第一次出现位置最靠前的概率.
\(n,m\le300\).
\(\mathscr{Solution}\)
感觉一直知道 PGF 但基本没有上手用过 qwq.
比较套路啦, 令 \(F_i(x)\) 表示 \(S_i\) 出现位置最靠前时, 其概率关于 \(|T|\) 的 PGF; \(G(x)\) 表示没有任何 \(S\) 出现时, 其概率关于 \(|T|\) 的 PGF. 我们的目标是求所有 \(F_i(1)\).
"\(T_i\) 被放出来的概率" = "\(|T|=i-1\) 时没有结束的概率":
\[G(x)+\sum_iF_i(x)=1+xG(x). \]"从一个未结束状态向后再恰好延伸出一个 \(S_i\) 的概率" = "在放的过程中所有戛然而止 (某个 \(S_j\) 出现了) 的时候再向后强行补满未出现字符的概率":
\[2^{-m}x^mG(x)=\sum_{j=1}^n\sum_{k=1}^m[S_i[:k]=S_j[m-k+1:]]2^{k-m}x^{m-k}F_j(x). \]一起令 \(x=1\):
\[\begin{cases} G(1)+\sum_iF_i(1)=1+G(1),\\ 2^{-m}G(1)=\sum_j\sum_k[S_i[:k]=S_j[m-k+1:]]2^{k-m}F_j(1)&\forall i. \end{cases} \]直接对总共 \(n+1\) 个变量消元即可. 复杂度 \(\mathcal O(n^2(n+m))\).
\(\mathscr{Code}\)
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
typedef unsigned long long ULL;
const int MAXN = 300;
const ULL BASE = 127;
int n, m;
ULL hpw[MAXN + 5], hsh[MAXN + 5][MAXN + 5];
double mat[MAXN + 5][MAXN + 5], pwr[MAXN + 5], ans[MAXN + 5];
inline void init() {
hpw[0] = 1;
rep (i, 1, m) hpw[i] = hpw[i - 1] * BASE;
pwr[0] = 1;
rep (i, 1, m) pwr[i] = 0.5 * pwr[i - 1];
}
inline ULL calc(const int i, const int l, const int r) {
return hsh[i][r] - hpw[r - l + 1] * hsh[i][l - 1];
}
inline void gauss() {
rep (i, 0, n) {
int p = i;
rep (j, i + 1, n) if (fabs(mat[p][i]) < fabs(mat[j][i])) p = j;
if (i != p) std::swap(mat[p], mat[i]);
rep (j, i + 1, n) {
double t = mat[j][i] / mat[i][i];
rep (k, i, n + 1) mat[j][k] -= t * mat[i][k];
}
}
per (i, n, 0) {
ans[i] = mat[i][n + 1] / mat[i][i];
rep (j, 0, i - 1) mat[j][n + 1] -= ans[i] * mat[j][i];
}
}
int main() {
scanf("%d %d", &n, &m), init();
rep (i, 1, n) {
static char str[MAXN + 5];
scanf("%s", str + 1);
rep (j, 1, m) hsh[i][j] = hsh[i][j - 1] * BASE + str[j];
}
rep (i, 1, n) {
mat[i][0] = -pwr[m];
rep (j, 1, n) {
rep (k, 1, m) if (calc(i, 1, k) == calc(j, m - k + 1, m)) {
// printf("%d %d %d\n", i, j, k);
mat[i][j] += pwr[m - k];
}
}
}
rep (i, 1, n + 1) mat[0][i] = 1.;
gauss();
rep (i, 1, n) printf("%.12f\n", ans[i]);
return 0;
}