1444: [Jsoi2009]有趣的游戏
分析：
如果一个点回到0号点，那么会使0号点的概率增加，而0号点的概率本来是1，不能增加，所以这题用期望做。
设$x_i$表示经过i的期望次数，然后初始可以知道$x_0=0$，又因为末尾节点只会经过一次，所以末尾节点的概率就是期望。
然后建出AC自动机，高斯消元。
参考sengxian
代码：
Gauss
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
const double eps = 1e-;
int ch[N][], val[N], fail[N], id[N], q[N], Index;
int n, L, m;
char s[N];
double A[N][N], p[N]; void Insert(int x) {
int now = ;
for (int i = ; i < L; ++i) {
int c = s[i] - 'A';
if (!ch[now][c]) ch[now][c] = ++Index;
now = ch[now][c];
}
val[now] = , id[x] = now;
}
void bfs() {
int L = , R = ;
for (int c = ; c < m; ++c) if (ch[][c]) q[++R] = ch[][c];
while (L <= R) {
int u = q[L ++];
for (int c = ; c < m; ++c) {
int v = ch[u][c];
if (!v) ch[u][c] = ch[fail[u]][c];
else {
fail[v] = ch[fail[u]][c];
val[v] |= val[fail[v]];
q[++R] = v;
}
}
}
}
bool Gauss(int n) {
for (int k = ; k <= n; ++k) {
int r = k;
for (int i = k + ; i <= n; ++i) if (A[i][k] > A[r][k]) r = k;
if (r != k) for (int j = ; j <= n + ; ++j) swap(A[r][j], A[k][j]);
for (int i = k + ; i <= n; ++i) {
if (fabs(A[i][k]) > eps) {
double t = A[i][k] / A[k][k];
for (int j = ; j <= n + ; ++j) A[i][j] -= A[k][j] * t;
}
}
}
for (int i = n; i >= ; --i) {
for (int j = i + ; j <= n; ++j) A[i][n + ] -= A[j][n + ] * A[i][j];
A[i][n + ] /= A[i][i];
}
return ;
}
int main() {
n = read(), L = read(), m = read();
for (int i = ; i < m; ++i) {
int u = read(), v = read();
p[i] = 1.0 * u / v;
}
int cnt = ;
for (int i = ; i < n; ++i) {
scanf("%s", s);
for (int j = ; j < L; ++j)
if (p[s[j] - 'A'] <= eps) { cnt ++; break; }
Insert(i);
}
if (cnt == n) {
for (int i = ; i <= n; ++i) puts("0.00"); return ;
}
bfs();
A[][Index + ] = -;
for (int i = ; i <= Index; ++i) {
A[i][i] = -1.0;
if (val[i]) continue;
for (int c = ; c < m; ++c) A[ch[i][c]][i] += p[c];
}
Gauss(Index);
for (int i = ; i < n; ++i) {
double p = A[id[i]][Index + ];
if (fabs(p) <= eps) puts("0.00");
else printf("%.2lf\n", p);
}
return ;
}
迭代+矩阵
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
struct Node {
double a[N][N];
Node() { memset(a, , sizeof(a)); }
} A;
int ch[N][], val[N], fail[N], id[N], q[N], Index;
int n, L, m;
char s[N];
double p[N]; Node operator * (const Node &A,const Node &B) {
Node C;
for (int k = ; k <= Index; ++k)
for (int i = ; i <= Index; ++i)
for (int j = ; j <= Index; ++j)
C.a[i][j] += A.a[i][k] * B.a[k][j];
return C;
}
void Insert(int x) {
int now = ;
for (int i = ; i < L; ++i) {
int c = s[i] - 'A';
if (!ch[now][c]) ch[now][c] = ++Index;
now = ch[now][c];
}
val[now] = , id[x] = now;
}
void bfs() {
int L = , R = ;
for (int c = ; c < m; ++c) if (ch[][c]) q[++R] = ch[][c];
while (L <= R) {
int u = q[L ++];
for (int c = ; c < m; ++c) {
int v = ch[u][c];
if (!v) ch[u][c] = ch[fail[u]][c];
else {
fail[v] = ch[fail[u]][c];
val[v] |= val[fail[v]];
q[++R] = v;
}
}
}
}
int main() {
n = read(), L = read(), m = read();
for (int i = ; i < m; ++i) {
int u = read(), v = read();
p[i] = 1.0 * u / v;
}
for (int i = ; i < n; ++i) {
scanf("%s", s);
Insert(i);
}
bfs();
for (int i = ; i <= Index; ++i) {
if (val[i]) A.a[i][i] = ;
else for (int c = ; c < m; ++c) A.a[i][ch[i][c]] += p[c];
}
for (int i = ; i <= ; ++i) A = A * A;
for (int i = ; i < n; ++i) printf("%.2lf\n", A.a[][id[i]]);
return ;
}