P4548 [CTSC2006] 歌唱王国

很有趣的期望题目。可以使用概率意义求解，也可以使用概率生成函数 PGF 求解，还可以直接 DP 求解。

概率意义

很巧妙啊。

概率意义解法确实很巧妙。设字符集大小为 $c$。假设这里是一个赌场，每一个时刻都有一个赌徒。赌博方式是，赌徒在 $t$ 时刻用 $x$ 枚钱币赌下一秒出现 $y$，赌对了则返还 $cx$ 枚钱币。这显然是一个公平赌博游戏。赌徒最开始在下一秒赌出现 $a_1$，赌错了则立刻跑路，赌对了则用获得所有钱币，继续赌下秒出现 $a_2$，以此类推。直到最终出现出现了整个名字 $a$，此时赌场关闭。整个过程结束。

考虑结束前出现的整个名字 $a$。根据上述过程容易发现，只有 在这段字符串的 Border 对应的后缀（假设包含原串）出现赌徒会获得收益，并且设 Border 长度为 $x$，那么对应位置的赌徒获得的收益为 $c^x$。其余位置的赌徒收益均为 $0$。

此时关键来了，由于是公平赌博游戏，所以赌场的赚与赔是不受赌徒与赌场采用的策略影响的。意味着赌场期望收益为 $0$。又因为赌场向获得收益的赌徒支付了 $\displaystyle \sum_{i\in \operatorname{Border}(S)} c^i$，所以期望有 $\displaystyle \sum_{i\in \operatorname{Border}(S)} c^i$ 个赌徒才会出现赌场关闭的情况。所以得出答案就是 $\displaystyle \sum_{i\in \operatorname{Border}(S)} c^i$。

概率生成函数 PGF

这个也挺牛的。感觉很像 P1393 Mivik 的标题 中生成函数的解法。

我们介绍概率生成函数 PGF：

$$F(x)=\sum_{i=0}^{+\infty} P(X=i)x^i$$

比较显然的一点是 $F(1)=1$。我们如何与期望建立联系？我们似乎需要在系数上再乘上一个 $i$。比较妙的是，我们考虑对 $F(x)$ 求导得到 $F’(x)$：

$$F'(x)=\sum_{i=1}^{+\infty}P(X=i)\cdot i x^{i-1}$$

我们就得到了 $F’(1)=E(X)$。总结一下，我们得到 $F(1)=1,F’(1)=E(X)$。

考虑原问题，设 $f(i)$ 表示在 $i$ 时刻结束的概率，$g(i)$ 表示在 $i$ 时刻仍不结束的概率。与之对应，设 $F(x)$ 为 $f(i)$ 的 PGF，$G(x)$ 为 $g(i)$ 的 PGF。接下来的步骤和 P1393 Mivik 的标题 一样的套路。先列出关系式再进行一些变换。

考虑在当前情况下再加入一个字符，那么接下来要么结束，要么不结束，得到：

$$\begin{align} G(x)x+1=F(x)+G(x) \end{align}$$

考虑在当前情况下直接加入一个名字，但是因为 Border 的缘故，过程中可能会提前结束。们构造 $H(x)$ 表示 Border 长度集合构成的数列对应的 OGF，中间对每一项分别乘上 $\displaystyle (\frac{x}{c})^{n-i}$。得到关系：

$$\begin{align} G(x)\cdot (\frac{x}{c})^n=F(x)H(x) \end{align}$$

接下来利用 PGF 的性质，进行一些变换。直接对 $(1)$ 式两边求导得到：

$$\begin{align} G'(x)x+G(x)=F'(x)+G'(x)\notag \end{align}$$

由于 PGF 的良好性质，我们要求的就是 $F’(1)$，于是直接将 $x=1$ 代入得：

$$\begin{align} G'(1)+G(1)&=F'(1)+G'(1)\notag\\ F'(1)&=G(1)\notag\\ \end{align}$$

令人意想不到的等式！继续将 $x=1$ 带入 $(2)$ 式：

$$\begin{align} G(1)\cdot (\frac{1}{c})^n=F(1)H(1)\notag \end{align}$$

有 $F(x)=1$（注意 $G(1)$ 显然不等于 $1$），于是得到；

$$\begin{align} G(1)\cdot (\frac{1}{c})^n=H(1)\notag\\ G(1)=\sum_{i\in \operatorname{Border}(S)} c^i\notag\\ \end{align}$$

得到了和利用 概率意义 所推出来一模一样的式子。只需做一遍 KMP 求出所有 Border ，然后计算即可，时间复杂度为 $\mathcal O(n)$。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,mod=1e4;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T,c,n;
int pw[N];
int a[N],ne[N];
inline void adj(int &x){x+=x>>31&mod;}
inline void solve()
{
    read(n);
    for(int i=1;i<=n;i++)read(a[i]),ne[i]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&a[i]!=a[j+1])j=ne[j];
        if(a[i]==a[j+1])j++;
        ne[i]=j;
    }
    int ans=0;
    for(int i=n;i;i=ne[i])adj(ans+=pw[i]-mod);
    printf("%04d\n",ans);
}
int main()
{
    read(c,T);
    c%=mod;
    n=1e5,pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=1ll*pw[i-1]*c%mod;
    while(T--)solve();
    return  0;
}

DP

方法与 P6835 [Cnoi2020] 线形生物 几乎一样，可以直接看这里。过程求出所有 Border 再 DP 即可，此处不再赘述。