无限猴子 歌唱王国 题解

王国 题解"/>

无限猴子 歌唱王国 题解

无限猴子

题目

题意：长度 n n n 的 01 模式串出现的期望长度。

F i F_i Fi​ 表是模 P P P 为 i i i 时的期望长度。

F i = 1 2 F g o ( i , 0 ) + 1 2 F g o ( i , 1 ) + 1 F_i = \frac {1}{2} F_{go(i,0)}+\frac {1}{2} F_{go(i,1)} + 1 Fi​=21​Fgo(i,0)​+21​Fgo(i,1)​+1

递推即可。

歌唱王国

题目

题意：值域 n n n 长度 m m m 的模式串出现的期望长度。

上一题加强版。
F i = 1 n ∑ c = 1 n F g o ( i , c ) + 1 F_i = \frac {1}{n} \sum_{c =1}^{n} F_{go(i,c)} + 1 Fi​=n1​c=1∑n​Fgo(i,c)​+1

g o ( i , P i ) = i + 1 go(i,P_i) = i+1 go(i,Pi​)=i+1，对于 c ≠ P i c \ne P_i c=Pi​， g o ( i , c ) = g o ( f i , c ) go(i,c)=go(f_i, c) go(i,c)=go(fi​,c)。

此处直接递推复杂度过高，列两个式子相消即可。

F i = 1 n ∑ c ≠ P i F g o ( f i , c ) + 1 n F i + 1 + 1 (1) F_i = \frac {1}{n} \sum_{c \ne P_i} F_{go(f_i,c)} + \frac{1}{n} F_{i+1} + 1\tag{1} Fi​=n1​c=Pi​∑​Fgo(fi​,c)​+n1​Fi+1​+1(1)

而

F f i = 1 n ∑ c = 1 n F g o ( f i , c ) + 1 (2) F_{f_i}=\frac {1}{n}\sum_{c = 1}^{n}F_{go(f_i,c)}+1\tag{2} Ffi​​=n1​c=1∑n​Fgo(fi​,c)​+1(2)

( 1 ) − ( 2 ) (1) - (2) (1)−(2) 得：

F i − F f i = 1 n F i + 1 − 1 n F g o ( f i , P i ) = 1 n F i + 1 − 1 n F f i + 1 (3) F_{i} - F_{f_i} = \frac {1}{n} F_{i+1} - \frac{1}{n} F_{go(f_i,P_i)}=\frac {1}{n} F_{i+1} - \frac{1}{n} F_{f_{i+1}}\tag{3} Fi​−Ffi​​=n1​Fi+1​−n1​Fgo(fi​,Pi​)​=n1​Fi+1​−n1​Ffi+1​​(3)

至此，可以用待定系数法递推。代码。

进一步观察：

由 F 0 = 1 n F 1 + n − 1 n F 0 + 1 F_{0} = \frac{1}{n} F_1 + \frac {n-1}{n} F_{0} + 1 F0​=n1​F1​+nn−1​F0​+1

得 F 1 − F 0 = − n F_1 - F_0 = -n F1​−F0​=−n

结合 ( 3 ) (3) (3) 可得

F i − F f i = n ( F i − 1 − F f i − 1 ) = ⋯ = − n i F_{i}-F_{f_i} = n (F_{i-1} - F_{f_{i-1}}) = \cdots = -n^{i} Fi​−Ffi​​=n(Fi−1​−Ffi−1​​)=⋯=−ni

边界是 F m = 0 F_m = 0 Fm​=0，而 F m − F f m = − n m F_m-F_{f_m} = -n^m Fm​−Ffm​​=−nm

得 F f m = n m F_{f_m} = n^m Ffm​​=nm

类似可得 F f f m = n m + n f m F_{f_{f_m}} = n^m + n^{f_m} Fffm​​​=nm+nfm​

一直跳 f f f 即可求得 F 0 F_0 F0​。

此题还存在一种形象理解方法：

有一家赌场。这家赌场有一个显示屏，每秒出现一个字符。如果赌徒花 x x x 元去猜，猜对了将返还 n x nx nx 元，猜错了不返还。容易看出，这个游戏是公平的，这家赌场并不会盈利。

在每一秒显示屏显示字符之前都会有很多赌徒进入赌场来赌博。这些赌徒们的行为如下：带 1 1 1 块钱来赌场，赌会出现 P 1 P_1 P1​，若赌对则继续拿 n n n 块钱赌 P 2 P_2 P2​，以此类推，一旦赌错就离场。而一旦有赌徒赌对了 P 1 P 2 ⋯ P m P_1P_2\cdots P_m P1​P2​⋯Pm​，赌场就会关门并把所有赌徒赶走。

这时候需要举个例子，然后会发现就是几个倒数第 border 位的赌徒会拿钱走。而因为这个游戏是公平的，那么来的人数也就是这些人拿的钱数。

代码