4820: [Sdoi2017]硬币游戏

链接

分析:

  期望dp+高斯消元。

  首先可以建出AC自动机,Xi表示经过节点i的期望次数,然后高斯消元,这样点的个数太多,复杂度太大。但是AC自动机上末尾节点只有n个,并且只有n个有用。所以考虑优化一下。

  一个串内部的转移是没有必要的,考虑转移到结尾节点的转移。

  当前的一个串S如果加入一个字符串T,变成ST,那么一定会结束,因为T这个字符串出现了。但是可能在T的某个前缀就出现了, 即存在一个字符串的后缀是T的前缀,那么统计出这样的转移,然后高斯消元。

  加了eps后WA了?

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
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 = ;
char s[N][N];
int p[N][N], n, m;
double mi[N], A[N][N]; void init(char *s,int *p) {
for (int i = ; i <= m; ++i) {
int j = p[i - ];
while (j && s[j + ] != s[i]) j = p[j];
if (s[j + ] == s[i]) j ++;
p[i] = j;
}
}
double Calc(char *a,char *b,int *p,bool f) {
int j = ;
for (int i = ; i <= m; ++i) {
while (j && b[i] != a[j + ]) j = p[j];
if (b[i] == a[j + ]) j ++;
}
if (f) j = p[j];
double res = ;
while (j) res += mi[m - j], j = p[j];
return res;
}
void Gauss() {
for (int k = ; k <= n; ++k) {
int r = k;
for (int i = k + ; i <= n; ++i) if (fabs(A[i][k]) > fabs(A[r][k])) r = i;
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]) > ) {
double t = A[i][k] / A[k][k];
for (int j = ; j <= n + ; ++j) A[i][j] -= t * A[k][j];
}
}
}
for (int i = n; i >= ; --i) {
for (int j = i + ; j <= n; ++j) A[i][n + ] -= A[i][j] * A[j][n + ];
A[i][n + ] /= A[i][i];
}
}
int main() {
n = read(), m = read();
for (int i = ; i <= n; ++i) {
scanf("%s", s[i] + );
init(s[i], p[i]);
}
mi[] = ;
for (int i = ; i <= m; ++i) mi[i] = mi[i - ] * 0.5;
for (int i = ; i <= n + ; ++i) A[][i] = ;
for (int i = ; i <= n; ++i) {
A[i][] = -mi[m]; A[i][i] = 1.0;
for (int j = ; j <= n; ++j)
A[i][j] += Calc(s[i], s[j], p[i], i == j); // 计算字符串i转移到j的概率,即求i的前缀等于j的后缀
}
Gauss();
for (int i = ; i <= n; ++i) printf("%.10lf\n",A[i][n + ]);
return ;
}
04-28 20:45