[luogu3706]硬币游戏

（可以参考洛谷4548，推导过程较为省略）

定义$g_{i}$表示随机$i$次后未出现给定字符串的概率，$f_{k,i}$表示随机$i$次后恰好出现$s_{k}$（指第$k$个字符串）的概率，设两者的生成函数分别为$G(x)$和$F_{k}(x)$

同样，考虑如何去表示$P(前i个字符中未出现给定字符串且最后m个字符为s_{t})$：

1.通过$g_{i}$，此时即为$\frac{g_{i}}{2^{m}}$；

2.通过$f_{k,i}$（注意虽然最后$m$个字符为$s_{t}$，但可能之前$s_{k}$出现了），枚举第一个出现$s_{k}$的位置$i+j$（右端点），同时必然要有$s_{t}$的前$j$个字符等于$s_{k}$末尾$j$个字符，此时转移的系数为$\frac{1}{2^{m-j}}$

记$S_{t,k}=\{j|s_{t}[0,j)=s_{k}[m-j,m)\}$，两者相等即$\forall 1\le t\le n,\frac{g_{i}}{2^{m}}=\sum_{k=1}^{n}\sum_{j\in S_{t,k}}\frac{f_{k,i+j}}{2^{m-j}}$，写成生成函数的形式即$\forall 1\le t\le n,G(x)=\sum_{k=1}^{n}\sum_{j\in S_{t,k}}\frac{2^{j}F_{k}(x)}{x^{j}}$

关于$S_{i,j}$的计算可以使用AC自动机或哈希，复杂度为$o(n^{2}m)$（虽然AC自动机可以$o(nm)$构建，但枚举$j$还是要$o(n^{2}m)$的）

答案即求$F_{k}(1)$，代入$x=1$后可以得到$n$个等式，但同时新增$G(1)$，再利用$\sum_{k=1}^{n}F_{k}(1)=1$就是恰好$n+1$个等式和变量，高斯消元即可，时间复杂度为$o(n^{3})$

（代码中的写法是以$G(1)$为常数去表示$F_{k}(1)$，再累加求出$G(1)$）

（另外精度问题很是神奇，可能数据中$n$和$m$的并不太大？）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 305

 4 #define eps 1e-10

 5 vector<int>v[N];

 6 queue<int>q;

 7 int V,n,m,nex[N*N],len[N*N],ch[N*N][31];

 8 double sum,mi[N],vis[N*N],a[N][N],ans[N];

 9 char s[N];

10 void add(int p){

11     int k=1;

12     for(int i=0;i<m;i++){

13         if (!ch[k][(s[i]=='T')]){

14             ch[k][(s[i]=='T')]=++V;

15             len[V]=len[k]+1;

16         }

17         k=ch[k][(s[i]=='T')];

18         v[p].push_back(k);

19     }

20 }

21 void build(){

22     nex[1]=1;

23     for(int i=0;i<2;i++)

24         if (ch[1][i]){

25             nex[ch[1][i]]=1;

26             q.push(ch[1][i]);

27         }

28     while (!q.empty()){

29         int k=q.front();

30         q.pop();

31         for(int i=0;i<2;i++)

32             if (ch[k][i]){

33                 int j=nex[k];

34                 while ((j>1)&&(!ch[j][i]))j=nex[j];

35                 if (ch[j][i])j=ch[j][i];

36                 nex[ch[k][i]]=j;

37                 q.push(ch[k][i]);

38             }

39     }

40 }

41 void guess(){

42     for(int i=1;i<=n;i++){

43         int t=-1;

44         for(int j=i;j<=n;j++)

45             if (abs(a[i][j])>=eps){

46                 t=j;

47                 break;

48             }

49         for(int j=i;j<=n;j++)swap(a[i][j],a[t][j]);

50         double s=a[i][i];

51         for(int j=i;j<=n+1;j++)a[i][j]/=s;

52         for(int j=i+1;j<=n;j++){

53             double s=a[j][i];

54             for(int k=i;k<=n+1;k++)a[j][k]-=s*a[i][k];

55         }

56     }

57     for(int i=n;i;i--){

58         ans[i]=a[i][n+1];

59         for(int j=1;j<i;j++){

60             a[j][n+1]-=ans[i]*a[j][i];

61             a[j][i]=0;

62         }

63     }

64 }

65 int main(){

66     scanf("%d%d",&n,&m);

67     V=1;

68     for(int i=1;i<=n;i++){

69         scanf("%s",s);

70         add(i);

71     }

72     build();

73     mi[0]=1;

74     for(int i=1;i<=m;i++)mi[i]=mi[i-1]*2;

75     for(int i=1;i<=n;i++){

76         for(int j=0;j<m;j++)vis[v[i][j]]=mi[j];

77         a[i][n+1]=1;

78         for(int j=1;j<=n;j++)

79             for(int k=v[j].back();k>1;k=nex[k])a[i][j]+=vis[k];

80         for(int j=0;j<m;j++)vis[v[i][j]]=0;

81     }

82     guess();

83     for(int i=1;i<=n;i++)sum+=ans[i];

84     for(int i=1;i<=n;i++)printf("%.6f\n",ans[i]/sum);

85 }

巴特西

[luogu3706]硬币游戏

最新文章

热门文章