1. Lay eggs
   Description

Input

Output

Sample Input
5
he
she
her
hers
his
hershe
0.30 5

Sample Output
0.163 0.031 0.031 0.031 0.002

Data Constraint

Hint
The frequency of occurrence is:
2 1 1 1 0
The output can be obtained from the knowledge of probability
he she her hers his
1.000 1.000 1.000 1.000 1.000 0.300 after one
After another time 1.000 0.510 0.510 0.510 0.090
After another time 0.657 0.216 0.216 0.216 0.027
After another 0.348 0.084 0.084 0.084 0.008
0.163 0.031 0.031 0.031 0.031 0.002 after another time

Analysis: first use AC automata to find out the number of times that all strings appear, and then sort them by recurrence of probability knowledge.
Now think of all the points with the same number of occurrences as one point
Let f[i][j] denote the probability of forgetting j times in the first I rounds
Then f[i][j]=f[i-1][j-1]*(1-p)+f[i-1][j]*p
Set answer array ans []
ans[i]=f[k][1]+f[k][2]+f[k][3]+......+f[k][i-1]
Then output the ans[i] corresponding to each string

Code

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
#define N 500000
using namespace std;
queue<int> q;

struct node
{
    int nxt[26],en,fail,sce;
}trie[N];
int n,m,num,a[300],b[300],c[300];
string s[300];
double f[2000][500];

void ins(string s1,int x)
{
    int len = s1.length();
    int u = 0;
    for (int i = 0; i < len; i++)
    {
        int v = s1[i]-'a';
        if (!trie[u].nxt[v]) trie[u].nxt[v] = ++num;
        u = trie[u].nxt[v];
    }
    trie[u].en = 1;
    trie[u].sce = x;
}

void getfail()
{
    while (!q.empty()) q.pop();
    for (int i = 0; i < 26; i++)
        if (trie[0].nxt[i])
        {
            trie[trie[0].nxt[i]].fail = 0;
            q.push(trie[0].nxt[i]);
        }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
            if (trie[u].nxt[i])
            {
                trie[trie[u].nxt[i]].fail = trie[trie[u].fail].nxt[i];
                q.push(trie[u].nxt[i]);
            }
            else trie[u].nxt[i] = trie[trie[u].fail].nxt[i];
    }
}

void find(char *s1)
{
    int len = strlen(s1);
    int u = 0;
    for (int i = 0; i < len; i++)
    {
        int v = s1[i] - 'a';
        u = trie[u].nxt[v];
        for (int j = u; j; j = trie[j].fail)
            if (trie[j].en) a[trie[j].sce]++;
    }
}

int main()
{
    scanf("%d",&n);
    num=0;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        ins(s[i], i);
    }
    getfail();
    char t[1000005];
    scanf("%s", t);
    find(t);
    for (int i = 1; i <= n; i++) c[i] = a[i];
    sort(c + 1, c + n + 1);
    int tot = 0;
    c[0] = 123456789;
    for (int i = 1; i <= n; i++)
    	if (c[i] != c[i - 1]) b[++tot] = c[i];
    double p;
    scanf("%lf%d", &p, &m);
    for (int i = 1; i <= tot; i++) f[0][i] = 1;
    for (int i = 1; i <= m; i++)
    	for (int j = 1; j <= tot; j++)
    		if (j <= i) f[i][j] = f[i - 1][j] * p + f[i - 1][j - 1] * (1 - p);
    			else f[i][j] = f[i - 1][j];
    for (int i = 1; i <= n; i++)
    	for (int j = 1; j <= tot; j++)
    		if (a[i] == b[j]) printf("%.3lf ", f[m][j]);
}