「JoyOI1519」博彩游戏
背景 Background
Bob最近迷上了一个博彩游戏……
描述 Description
这个游戏的规则是这样的：
每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；
有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。
Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。
请你告诉Bob中奖的概率有多少？
输入格式 InputFormat
第一行三个用空格隔开的数N、M和R的范围R。
其中1<=R<=9，0<N<=60，0<M<=20000。
下面M行每行一个字符串（长度小于等于20），字符串的每一位范围在1-r之间
保证必要运算都在64位整型范围内。
输出格式 OutputFormat
一行一个实数，表示中奖的概率（保留小数点后5位小数）。
数据范围和注释 Hint
数据分布：
第1个点~第10个点，每个点5分；
第11个点~第15个点，每个点10分。
对于样例的解释：
随机序列一共有3^5=243个，其中包含”1″的个数为211个，则概率为211/243=0.86831
题解
此题n的范围为100
ac自动机+dp，做法和bzoj1030相同。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(!(ch>='0'&&ch<='9')) {if(ch=='-')f=-1;ch=getchar();} while((ch>='0'&&ch<='9')) {x=x*10+(ch-'0');ch=getchar();} return x*f; } int n,m,r,sz=1; char s[25]; ll ans1,ans2=1,f[105][400005]; int a[400005][10],point[400005],q[400005]; bool danger[400005]; void ins() { int now=1,c,l=strlen(s); for(int i=0;i<l;i++) { c=s[i]-'0'; if(a[now][c])now=a[now][c]; else now=a[now][c]=++sz; } danger[now]=1; } void acmach() { int t=0,w=1,now; q[0]=1;point[1]=0; while(t<w) { now=q[t++]; for(int i=1;i<=r;i++) { if(!a[now][i])continue; int k=point[now]; while(!a[k][i])k=point[k]; point[a[now][i]]=a[k][i]; if(danger[a[k][i]]) danger[a[now][i]]=1; q[w++]=a[now][i]; } } } void dp(int x) { for(int i=1;i<=sz;i++) if(!danger[i]&&f[x-1][i]) for(int j=1;j<=r;j++) { int k=i; while(!a[k][j])k=point[k]; f[x][a[k][j]]+=f[x-1][i]; } } int main() { n=read();m=read();r=read(); for(int i=1;i<=r;i++)a[0][i]=1; for(int i=1;i<=m;i++) { scanf("%s",s); ins(); } acmach(); f[0][1]=1; for(int i=1;i<=n;i++)dp(i); for(int i=1;i<=n;i++) ans2*=r; for(int i=1;i<=sz;i++) if(!danger[i])ans1+=f[n][i]; printf("%.5lf",double(ans2-ans1)/ans2); return 0; } |
Subscribe
计数器 9855254
OI 课件=>
OI 课件=>