题意:
有 n 个人, 每个人有一个长为 L 的由 1~6 组成的数串, 现在扔一个骰子, 依次记录扔出的数字, 如果当前扔出的最后 L 个数字与某个人的数串匹配, 那么这个人就算获胜, 现在问每个人获胜的概率是多少.
n,l<=10
思路: 对于无限型的概率
首先显然有一个暴力做法是对于 n 个串建出 AC 自动机和转移矩阵后跑若干次矩乘快速幂 DP 使得答案趋于稳定后可以将结果看做答案
正解是高斯消元
每个点对于它的后继有 1/6 的概率跑到, 计算贡献后累加
边界条件: 题目给出的 n 个串没有后继
游戏开始时必定会转移到根节点, 等价于有一个虚的节点 (不需要建立方程) 对根有 100% 的 1 的贡献
剩下的就是高斯消元模板了
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<cmath>
- #include<iostream>
- #include<algorithm>
- #include<map>
- #include<set>
- #include<queue>
- #include<vector>
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef pair<int,int> PII;
- typedef vector<int> VI;
- #define fi first
- #define se second
- #define MP make_pair
- #define N 11000
- #define M 210
- #define MOD 1000000007
- #define eps 1e-8
- #define pi acos(-1)
- double a[M][M];
- int nxt[M][7],fa[M],c[M],d[N],q[N],b[N],flag[N],n,l,cnt;
- int read()
- {
- int v=0,f=1;
- char c=getchar();
- while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
- while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
- return v*f;
- }
- void build(int k)
- {
- int u=1;
- for(int i=1;i<=l;i++)
- {
- if(!nxt[u][b[i]]) nxt[u][b[i]]=++cnt;
- u=nxt[u][b[i]];
- }
- c[k]=u;
- d[u]=k;
- }
- void acauto()
- {
- int t=0; int w=1; q[1]=1;
- while(t<w)
- {
- int u=q[++t];
- // printf("%d\n",u);
- for(int i=1;i<=6;i++)
- {
- if(nxt[u][i])
- {
- int son=nxt[u][i];
- int p=fa[u];
- if(u==1) fa[son]=1;
- else fa[son]=nxt[p][i];
- q[++w]=son;
- }
- else
- {
- int p=fa[u];
- if(u==1) nxt[u][i]=1;
- else nxt[u][i]=nxt[p][i];
- }
- }
- }
- }
- void init()
- {
- /* for(int i=1;i<=cnt;i++)
- {
- fa[i]=flag[i]=d[i]=0;
- for(int j=1;i<=6;j++) nxt[i][j]=0;
- }
- memset(q,0,sizeof(q));
- for(int i=1;i<=cnt;i++)
- for(int j=0;j<=cnt;j++) a[i][j]=0;
- for(int i=1;i<=n;i++) c[i]=0;*/
- memset(a,0,sizeof(a));
- memset(nxt,0,sizeof(nxt));
- memset(fa,0,sizeof(fa));
- memset(c,0,sizeof(c));
- memset(d,0,sizeof(d));
- //memset(q,0,sizeof(q));
- memset(b,0,sizeof(b));
- cnt=1;
- }
- void test()
- {
- for(int i=1;i<=cnt;i++)
- {
- for(int j=1;j<=cnt+1;j++) printf("%.2lf",a[i][j]);
- printf("\n");
- }
- printf("\n");
- }
- int main()
- {
- freopen("hdoj5955.in","r",stdin);
- freopen("hdoj5955.out","w",stdout);
- int cas;
- scanf("%d",&cas);
- while(cas--)
- {
- init();
- scanf("%d%d",&n,&l);
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=l;j++) scanf("%d",&b[j]);
- build(i);
- }
- acauto();
- for(int i=1;i<=cnt;i++)
- {
- a[i][cnt+1]=0;
- a[i][i]=-1.0;
- if(d[i]) continue;
- for(int j=1;j<=6;j++)
- {
- int v=nxt[i][j];
- a[v][i]+=1.0/6.0;
- // printf("%d %d\n",i,v);
- }
- }
- a[1][cnt+1]=-1.0;
- // test();
- for(int i=1;i<=cnt;i++)
- {
- int K=i;
- for(int j=i+1;j<=cnt;j++)
- if(fabs(a[j][i])>fabs(a[K][i])) K=j;
- if(K!=i)
- for(int j=1;j<=cnt+1;j++) swap(a[i][j],a[K][j]);
- for(int j=i+1;j<=cnt;j++)
- {
- double f=a[j][i]/a[i][i];
- for(int k=i;k<=cnt+1;k++) a[j][k]-=f*a[i][k];
- }
- }
- for(int i=cnt;i>=1;i--)
- {
- for(int j=i+1;j<=cnt;j++)
- a[i][cnt+1]-=a[i][j]*a[j][cnt+1];
- a[i][cnt+1]=a[i][cnt+1]/a[i][i];
- }
- // test();
- for(int i=1;i<=n;i++)
- if(i<n) printf("%.6lf",a[c[i]][cnt+1]);
- else printf("%.6lf\n",a[c[i]][cnt+1]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2794697.html