概率生成函数学习笔记

本文参考：bztMinamoto和露迭月巨佬的博客

前置知识：对生成函数有一定了解，有概率期望的一定基础。

定义：一个生成函数F(x)，第i位表示某某为i的概率。

例题：[CTSC2006]歌唱王国

题意：

给定一个长度为 $L$ 的序列 $A$ 。然后每次掷一个平骰子（有m种值）并将其上的数字加入到初始为空的序列 $B$ 的末尾，如果序列 $B$ 中已经出现了给定序列 $A$ ，即 $A$ 是 $B$ 的子串，则停止。

题解：

设 $f_i$ 为 $i$ 时间停止的概率， $g_i$ 为 $i$ 时间不停止的概率， $F(x)$ , $G(x)$ 分别为它们的生成函数。

$F(x)+G(x)=1+G(x)x$

这其实是 $f_i+g_i=1+g_{i-1}$

考虑对这个式子做出变形，两边同时求导 $F′(x)+G′(x)=G(x)+G′(x)x$

对 $x$ 取 $1$ , $F′(1)=G(1)$

考虑求出 $G(1)$

介绍一个东西 $border$ :对于一个长度为 $n$ 的序列 $A$ ，若 $A[1,i]=A[n−i+1,n]$ ，则称 $A[1,i]$ 是 $A$ 的一个 $border$

定义 $a_i$ = $A[1,i]$ 是 $border$

$G(x)(\frac{1}{m}x)^m=\sum_{i=1}^{m}a_iF(x)(\frac{1}{m}x)^{m−i}$

将 $x=1$ 带入

$G(i)=\sum_{i=1}^{m}m^iai$

$ai$ 用 $hash$ 或 $kmp$ 求出即可。

代码:

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
const int N=1e5+5,P=1e4;
inline int add(int x,int y){return x+y>=P?x+y-P:x+y;}
inline int mul(int x,int y){return 1ll*x*y%P;}
int n,p,res,pos,bin[N],nxt[N],a[N];
signed main()
{
    p=read(),bin[0]=1;
    for(int i=1;i<=100000;i++)bin[i]=mul(bin[i-1],p);
    int T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        nxt[0]=nxt[1]=0;
        for(int i=2,j=0;i<=n;i++)
        {
            while(j&&a[j+1]!=a[i])j=nxt[j];
            j+=(a[j+1]==a[i]);
            nxt[i]=j;
        }
        pos=n,res=0;
        while(pos)
        {
            res=add(res,bin[pos]);
            pos=nxt[pos];
        }
        printf("%04lld\n",res);
    }
    return 0;
}

例题：[CTSC2006]歌唱王国

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
const int N=305;
const int P=1e9+7;
const double eps=1e-10;
double a[N][N],b[N];
char s[N];
int n,m,bin[N],h[N][N];
inline int Hash(int i,int l,int r){return ((h[i][r]-1ll*h[i][l-1]*bin[r-l+1])%P+P)%P;}
void Gauss(int n)
{
    for(int i=1;i<=n;i++)
    {
        if(a[i][i]>-eps&&a[i][i]<eps)
        {
            for(int j=i+1;j<=n;j++)if(a[j][i]<-eps||a[j][i]>eps)
            {
                for(int k=i;k<=n+1;k++)swap(a[i][k],a[j][k]);
                break;
            }
        }
        double t=1.0/a[i][i];
        for(int j=i;j<=n+1;j++)a[i][j]*=t;
        for(int j=i+1;j<=n;j++)
        {
            t=a[j][i];
            for(int k=i;k<=n+1;k++)a[j][k]-=a[i][k]*t;
        }
    }
    for(int i=n-1;i;i--)
        for(int j=i+1;j<=n;j++)a[i][n+1]-=a[j][n+1]*a[i][j];
}
int main()
{
    n=read();m=read();
    bin[0]=b[0]=1;
    for(int i=1;i<=m;i++)bin[i]=1ll*bin[i-1]*2%P,b[i]=b[i-1]*2;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)h[i][j]=(1ll*h[i][j-1]*2+(s[j]=='H'))%P;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            for(int k=1;k<=m;k++)(Hash(i,1,k)==Hash(j,m-k+1,m))?a[i][j]+=b[k]:0;
        a[i][n+1]=-1;
    }
    for(int i=1;i<=n;i++)a[n+1][i]=1;
    a[n+1][n+2]=1;
    Gauss(n+1);
    for(int i=1;i<=n;i++)printf("%.8lf\n",a[i][n+2]);
    return 0;
}