Crazy Typewriter
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 391 Accepted Submission(s): 109
The protagonist in this problem wants to tell acmers some secrets, of course, by the typewriter.
There had been several opportunities, but the protagonist let them sliped. Now, another opportunity came, the writer started a new paragraph. The protagonist found
that he could set the possiblities of each character in happy astonishment. After the possiblities had been set, he wanted to know the exception of time at least the writer need to be mind-absent if any secret was typed out.
fewovigwnierfbiwfioeifaorfwarobahbgssjqmdowj
The first line of each case contains an integer n, no more than 15, indicating the number of secrets.
The second line contains 26 real numbers, indicating the set possibilities of 'a'-'z', respectively, the sum would be 1.0 .
Then n lines, each contains a secret, no longer than 15, which is made up by lowercase letters 'a'-'z'.
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std; const int N=;
const int SZ=;
const double eps=1e-;
double p[],A[N][N];
bool inf[N];
struct AC
{
int ch[N][];
int sz,val[N],fail[N];
void init(){
sz=;memset(val,,sizeof(val));
memset(ch[],,sizeof(ch[]));
}
void insert(char *s)
{
int rt=;
for (int i=;s[i];i++){
int c=s[i]-'a';
if (ch[rt][c]==){
ch[rt][c]=sz;
memset(ch[sz],,sizeof(ch[sz]));
sz++;
}
rt=ch[rt][c];
}
val[rt]=;
}
void getfail()
{
queue<int>q;
for (int i=;i<SZ;i++)
{
int c=ch[][i];
if (c){ q.push(c);fail[c]=; }
}
while (!q.empty())
{
int u=q.front();q.pop();
for (int i=;i<SZ;i++)
{
int c=ch[u][i];
if (!c){
ch[u][i]=ch[fail[u]][i];
}else
{
int v=fail[u];
q.push(c);
fail[c]=ch[v][i];
val[c]|=val[fail[c]];
}
}
}
}
}ac; void build_matrix()
{
int i,j;
memset(A,,sizeof(A));
for(i=;i<ac.sz;i++)
{
if(ac.val[i]){A[i][i]=;A[i][ac.sz]=;}
else
{
for(j=;j<SZ;j++){int v=ac.ch[i][j];A[i][v]+=p[j];}
A[i][i]+=-;A[i][ac.sz]=-;
}
}
} void gauss(int n)
{
int i,j,k,r;
for(i=;i<n;i++)
{
r=i;
for(j=i+;j<n;j++)
if(fabs(A[j][i])>fabs(A[r][i])) r=j;
if(fabs(A[r][i])<eps) continue;
if(r!=i) for(j=;j<=n;j++) swap(A[r][j],A[i][j]);
for(k=;k<n;k++) if(k!=i)
for(j=n;j>=i;j--) A[k][j]-=A[k][i]/A[i][i]*A[i][j];
}
memset(inf,,sizeof(inf));
for(i=ac.sz-;i>=;i--){
if(fabs(A[i][i])<eps&&fabs(A[i][ac.sz])>eps) inf[i]=;
for(j=i+;j<ac.sz;j++)
if(fabs(A[i][j])>eps&&inf[j]) inf[i]=;
}
if(inf[]) printf("Infinity\n");
else printf("%.6lf\n",A[][ac.sz]/A[][]+eps);
} int main()
{
//freopen("b.txt","w",stdout);
int n,i,j;char s[];
while(~scanf("%d",&n))
{
ac.init();
for(i=;i<SZ;i++) scanf("%lf",p+i);
for(i=;i<n;i++)
{
scanf("%s",s);ac.insert(s);
}
ac.getfail();
build_matrix();
gauss(ac.sz);
}
return ;
}
hdu 3992 AC自动机上的高斯消元求期望的更多相关文章
-
hdu 4870 rating(高斯消元求期望)
Rating Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Sub ...
-
HDU4870_Rating_双号从零单排_高斯消元求期望
原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=4870 原题: Rating Time Limit: 10000/5000 MS (Java/Other ...
-
2016ACM/ICPC亚洲区沈阳站H - Guessing the Dice Roll HDU - 5955 ac自动机+概率dp+高斯消元
http://acm.hdu.edu.cn/showproblem.php?pid=5955 题意:给你长度为l的n组数,每个数1-6,每次扔色子,问你每个串第一次被匹配的概率是多少 题解:先建成ac ...
-
[ACM] hdu 4418 Time travel (高斯消元求期望)
Time travel Problem Description Agent K is one of the greatest agents in a secret organization calle ...
-
hdu 2262 高斯消元求期望
Where is the canteen Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot ...
-
hdu 4418 高斯消元求期望
Time travel Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total ...
-
HDU 5833 (2016大学生网络预选赛) Zhu and 772002(高斯消元求齐次方程的秩)
网络预选赛的题目……比赛的时候没有做上,确实是没啥思路,只知道肯定是整数分解,然后乘起来素数的幂肯定是偶数,然后就不知道该怎么办了… 最后题目要求输出方案数,首先根据题目应该能写出如下齐次方程(从别人 ...
-
高斯消元与期望DP
高斯消元可以解决一系列DP序混乱的无向图上(期望)DP DP序 DP序是一道DP的所有状态的一个排列,使状态x所需的所有前置状态都位于状态x前: (通俗的说,在一个状态转移方程中‘=’左侧的状态应该在 ...
-
【BZOJ2137】submultiple 高斯消元求伯努利数
[BZOJ2137]submultiple Description 设函数g(N)表示N的约数个数.现在给出一个数M,求出所有M的约数x的g(x)的K次方和. Input 第一行输入N,K.N表示M由 ...
随机推荐
-
Linux用户管理.md
用户与组的概念 linux多用户,多任务的特性 Linux是一个真实的.完整的多用户多任务操作系统,多用户多任务就是可以在系统上建立多个用户,而多个用户可以在同一时间内登录同一个系统执行各自不同的任务 ...
-
【Shell脚本】怎样表示一个for循环
[Shell脚本]怎样表示一个for循环 在此说一下我常用的两个结构: 1. for i in $(seq 1 100); do echo $i done 2. for (( i = ...
-
Mega Dropdown - 带子分类的响应式下拉菜单
当你在开发一个内容很多的 Web 项目的时候,最具挑战性的部分之一是为了如果更方便用户浏览这些内容.我们都能想到的一个例子是 Amazon,无限的类别以及它们的子类别.Mega Dropdown 是带 ...
-
System.Diagnostics.Debug和System.Diagnostics.Trace 【转】
在 .net 类库中有一个 system.diagnostics 命名空间,该命名空间提供了一些与系统进程.事件日志.和性能计数器进行交互的类库.当中包括了两个对开发人员而言十分有用的类——debug ...
-
Win7 + VS2015 + CMake3.6.1-GUI编译库
CMake生成Unicode版本VC工程 Just add this line in your top CMakeLists.txt file: add_definitions(-DUNICO ...
-
Android开发--去掉标题栏
Android开发中为了尽可能美观,会去掉标题栏.去掉标题栏有三种方法. 一.在Activity代码里实现 在代码中实现以下方法: this.requestWindowFeature(Window.F ...
-
加班计时App
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.T ...
-
番外篇--Moddule Zero安装
Moddule Zero 安装 1.2.1 从模板创建 使用ABP和module-zero开始一个新项目最简单的方式是使用启动模板.详细了解请参考启动模板文档. 1.2.2 手动安装 如果你有一个预先 ...
-
12.25daily_scrum
今天是圣诞节,大家在度过了一个愉快的节日同时,同时也收到了最好的圣诞礼物,就是调试工作已经进入尾声,接下来我们组的主要任务就是M2阶段的总结了.为了更好的做好M2阶段的收官工作,我们组决定分配相当的一 ...
-
IIS 之 应用程序池
IIS(Internet Information Services),由于我使用的是Windows10系统,所以本文以其内置 10.0.14393.0 版本说明. 应用程序池 → 右键(待设置应用程序 ...