P1519 博彩游戏
背景
Bob最近迷上了一个博彩游戏……
描述
这个游戏的规则是这样的：
每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；
有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。
Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。
请你告诉Bob中奖的概率有多少？
每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；
有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。
Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。
请你告诉Bob中奖的概率有多少？
输入格式
第一行三个用空格隔开的数N、M和R的范围R。
其中1<=R<=9，0<N<=60，0<M<=20000。
下面M行每行一个字符串（长度小于等于20），字符串的每一位范围在1-r之间
保证必要运算都在64位整型范围内。
其中1<=R<=9，0<N<=60，0<M<=20000。
下面M行每行一个字符串（长度小于等于20），字符串的每一位范围在1-r之间
保证必要运算都在64位整型范围内。
输出格式
一行一个实数，表示中奖的概率（保留小数点后5位小数）。
测试样例1
输入
5 1 3
1
输出
0.86831
备注
数据分布：
第1个点~第10个点，每个点5分；
第11个点~第15个点，每个点10分。
第1个点~第10个点，每个点5分；
第11个点~第15个点，每个点10分。
对于样例的解释：
随机序列一共有3^5=243个，其中包含"1"的个数为211个，则概率为211/243=0.86831Bob HAN
【思路】
AC自动机+DP。
与bzoj1030一样思路都是要转化为求AC自动机上不经过单词节点的方案。不同的是这个题需要用滚动数组不然MLE <_<
尼玛tyvj上double要用%f，让我WA了千万发，我说以前怎么提交不过WTF
【代码】
#include<set>
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int N=+,L=+;
const int node = N*L;
const int sigma = ; char s[L]; int n,m,r; LL d[][node]; struct ACauto{
int ch[node][sigma],f[node],val[node],sz;
void clear() {
sz=; memset(ch[],,sizeof(ch[]));
}
void insert(char *s) {
int n=strlen(s),u=;
for(int i=;i<n;i++) {
int c=s[i]-'';
if(!ch[u][c]) {
memset(ch[sz],,sizeof(ch[sz]));
val[sz]=; ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=;
}
void get_Fail() {
queue<int> q;
f[]=;
for(int c=;c<r;c++)
if(ch[][c]) f[ch[][c]]=,q.push(ch[][c]);
while(!q.empty()) {
int qr=q.front(); q.pop();
for(int c=;c<r;c++) {
int u=ch[qr][c]; if(!u) continue;
q.push(u); int v=f[qr];
while(v&&!ch[v][c]) v=f[v];
if(val[ch[v][c]]) val[u]=;
f[u]=ch[v][c];
}
}
}
}ac;
int que[][N],cnt[];
int main() {
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
scanf("%d%d%d",&m,&n,&r);
ac.clear();
for(int i=;i<n;i++) {
scanf("%s",s); ac.insert(s);
}
ac.get_Fail();
d[][]=;
int x=;
for(int i=;i<=m;i++) {
x^=;
memset(d[x],,sizeof(d[x]));
for(int j=;j<ac.sz;j++) if(!ac.val[j]&&d[x^][j]) {
for(int c=;c<r;c++) {
int k=j; while(!ac.ch[k][c]&&k) k=ac.f[k];
d[x][ac.ch[k][c]]=d[x^][j]+d[x][ac.ch[k][c]];
}
}
}
LL ans1=,ans2=;
for(int i=;i<=m;i++) ans2*=(LL)r;
for(int i=;i<ac.sz;i++)
if(!ac.val[i]) ans1+=d[x][i];
double f=((double)ans2-(double)ans1)/(double)ans2;
printf("%.5f\n",f);
return ;
}