【JZOJ5167】下蛋爷

Description

Solution

首先我们假设知道每个单词出现的次数，那么对于相同的出现次数只保留一个。

例如出现次数为： a1,a2,a2,a2,a3 ，只保留 a1,a2,a3 。

将它们排序后，我们的到一个从大到小的序列，那么这个序列第 i 次阅读后面i个就有可能被遗忘。

设 Fi,j 为第 i 次阅读，j记住的概率，则如果前面那次阅读的后面一个 j+1 记住，那么本轮 j 将不会被遗忘，则有Fi,j=Fi−1,j+1。

如果 i−1 次阅读时 j+1 遗忘了，那么有 (Fi−1,j−Fi−1,j+1)⋅p 的概率会记住（表示 i−1 次j能记住且 j+1 记不住的概率）。

总的转移式为： Fi,j=Fi−1,j+1+(Fi−1,j−Fi−1,j+1)⋅p 。

求每个单词出现的次数，kmp卡卡常可能会过（没试过）。当然AC自动机是首选。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define rep(i,x) for(int i=ls[x];i;i=nx[i])
#define N 210
#define K 1010
#define M 200010
using namespace std;
double f[K][N];
char s[N][];
char ss[K*K];
int wz[N];
int nn=;
int tr[M][],dep[M],tot=,fail[M],up[M],b[M];
struct node{
    int x,wz;
}a[N];
bool cmp(node x,node y){
    return x.x>y.x;
}
void insert(int x)
{
    int l=strlen(s[x]+),rt=;
    fo(i,,l)
    {
        int ch=s[x][i]-'a'+;
        if(!tr[rt][ch]) tr[rt][ch]=++tot;
        dep[tr[rt][ch]]=dep[rt]+,rt=tr[rt][ch];
    }
    tr[rt][]=;
    b[rt]=x;
}
void makefail()
{
    queue<int> q;
    q.push();
    while(!q.empty())
    {
        int x=q.front(),p=;
        q.pop();
        fo(i,,)
        {
            int v=tr[x][i];
            if(!v) continue;
            int j=fail[x];
            while(j && !tr[j][i]) j=fail[j];
            fail[v]=tr[j][i];
            q.push(v);
            if(!fail[v]) fail[v]=;
            up[v]=b[fail[v]]?fail[v]:up[fail[v]];
        }
    }
}
void query()
{
    int l=strlen(ss+);
    int rt=;
    fo(i,,l)
    {
        int j=ss[i]-'a'+;
        while(rt!= && !tr[rt][j]) rt=fail[rt];
        rt=tr[rt][j];
        if(!rt) rt=;
        int p=rt;
        while(p>) a[b[p]].x++,p=up[p];
    }
}
int main()
{
    int n,q;
    scanf("%d",&n);
    fo(i,,n)
    {
        scanf("%s",s[i]+);
        insert(i),a[i].wz=i;
    }
    makefail();
    scanf("%s",ss+);
    query();
    sort(a+,a+n+,cmp);
    a[].x=-;
    fo(i,,n)
    {
        if(a[i].x!=a[i-].x) nn++;
        wz[a[i].wz]=nn;
    }
    double p;
    scanf("%lf %d",&p,&q);
    fo(i,,nn-) f[][i]=;
    f[][nn]=p;
    fo(i,,q)
    {
        f[i][nn]=f[i-][nn]*p;
        fo(j,,nn-)
        f[i][j]=f[i-][j+]+(f[i-][j]-f[i-][j+])*p;
    }
    fo(i,,n) printf("%.3lf ",f[q][wz[i]]);
}