题意：长度 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=21Fgo(i,0)+21Fgo(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=n1c=1∑nFgo(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=n1c=Pi∑Fgo(fi,c)+n1Fi+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=n1c=1∑nFgo(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=n1Fi+1−n1Fgo(fi,Pi)=n1Fi+1−n1Ffi+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=n1F1+nn−1F0+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 P1P2⋯Pm，赌场就会关门并把所有赌徒赶走。
这时候需要举个例子，然后会发现就是几个倒数第 border 位的赌徒会拿钱走。而因为这个游戏是公平的，那么来的人数也就是这些人拿的钱数。