2015
04-14

# Crazy Typewriter

There was a crazy typewriter before. When the writer is not very sober, it would type characters randomly, one per second, the possiblities of characters may differ.
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

There are several cases, no more than 15.
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’.

There are several cases, no more than 15.
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’.

2
0.5000 0.5000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000
ab
aa

3.000000

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cmath>

using namespace std;

const double eps = 1e-8;
const int N = 1005;
const int C = 26;

int Map[256];
int c;
double A[205][205];
bool inf[205];
double prob[C];

void init() {
for (int i = 0; i < C; i++) {
Map[i + 'a'] = i;
}
}

void gauss() {
int i, j, k, r;
for (i = 0; i < c; i++) {
r = i;
for (j = i + 1; j < c; j++)
if (fabs(A[j][i]) > fabs(A[r][i])) r = j;
if (fabs(A[r][i]) < eps) continue;
if (r != i) for (j = 0; j <= c; j++) swap(A[r][j], A[i][j]);

for (k = 0; k < c; k++) if (k != i)
for (j = c; j >= i; j--)
A[k][j] -= A[k][i] / A[i][i] * A[i][j];
}
}

struct AC {
struct Node {
bool out;
int id;
Node* ch[C];
Node* fail;

void init() {
out = 0;
memset(ch, 0, sizeof(ch));
fail = 0;
}
};

Node* root, * null, * it;
Node D[N * 10];
int sz;

Node* get_Node() {
it->init();
it->id = sz++;
it++;
return it - 1;
}

void init() {
it = D;
sz = 0;
null = new Node;
null->init();
root = get_Node();
for (int i = 0; i < C; i++)
null->ch[i] = root;
root->fail = null;
}

Node* cur = root;
for (int i = 0; str[i]; i++) {
if (!cur->ch[Map[str[i]]])
cur->ch[Map[str[i]]] = get_Node();
cur = cur->ch[Map[str[i]]];
}
cur->out = 1;
}

void set_fail() {
int st = 0, ed = 0;
que[ed++] = root;
while (st < ed) {
Node* cur = que[st++];
for (int i = 0; i < C; i++) {
Node* t = cur->fail;
if (!cur->ch[i]) {
while (t != null && !t->ch[i]) t = t->fail;
cur->ch[i] = t->ch[i];
continue;
}
que[ed++] = cur->ch[i];
while (t != null && !t->ch[i]) t = t->fail;
cur->ch[i]->fail = t->ch[i];
cur->ch[i]->out |= t->ch[i]->out;
}
}
}

void gao() {
c = sz;
for (int i = 0; i < sz; i++)
fill(A[i], A[i] + sz + 1, 0);

for (int i = 0; i < sz; i++) {
A[i][i] = 1;
A[i][sz] = 0;
continue;
}
A[i][sz] = 1;
for (int j = 0; j < C; j++) {
A[i][t] -= prob[j];
}
}

gauss();

memset(inf, 0, sizeof(inf));

for (int i = c - 1; i >= 0; i--) {
if (fabs(A[i][i]) < eps && fabs(A[i][c]) > eps) inf[i] = 1;
for (int j = i + 1; j < c; j++)
if (fabs(A[i][j]) > eps && inf[j]) inf[i] = 1;
}

if (inf[0])
puts("Infinity");
else {
if (fabs(A[0][0]) < eps)
puts("0.000000");
else
printf("%.6f\n", A[0][sz] / A[0][0]);
}

}

}ac;

char str[100];

int main() {
int n;
init();
while (~scanf("%d", &n)) {
for (int i = 0; i < 26; i++) {
scanf("%lf", &prob[i]);
}
ac.init();
for (int i = 0; i < n; i++) {
scanf("%s", str);
}
ac.set_fail();
ac.gao();
}
return 0;
}

1. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

2. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

3. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

4. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

5. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

6. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

7. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

8. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

9. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

10. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

11. 如果一个工厂查出的废品越来越多越来越大，说这工厂监管很到位，决心很大，成绩也很大……这工厂是不是该关门了？如果一个地方查出来的腐败越来越多越来越大，说这地方政府监管很到位，决心很大，成绩也很大，那……我就不说了。

12. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

13. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。