浅谈生成函数在掷骰子问题上的应用 长沙市长郡中学 杨懋龙
给定一个长度为L的序列A。然后每次掷一个标有1到m的公平骰子并将其上的数字加入
到初始为空的序列B的末尾，如果序列B中已经出现了给定序列A，即A是B的子串，则停止，
求序列B的期望长度。L ≤ 10
5
。
4.1 分析
掷骰子问题的基础形式是给出一个序列和一个骰子，然后不断地掷骰子生成一个随机
序列，直到给定序列在随机序列中出现才停止，并求期望的掷骰子次数。
4.2 一种非生成函数方法
令E
i
表示当前满足A[1, i]是B的后缀，到首次满足A[1, i + 1]是B的后缀的期望掷骰子次
数。那么需要求的便是
P
n−1
i=0
E
i
。
定义 f
i, j
为在A[1, i]后加入数字 j组成的新序列的最长非自身border长度。那么可以得到
方程
E
i
= 1 +
1
m
m
X
j=1
j , A
i+1
i
X
k= f
i, j
E
k
解方程可以得到
E
i
= m + (m − 1)
i−1
X
k=1
E
k
−
m
X
j=1
j , A
i+1
f
i, j
−1
X
k=1
E
k
这样时间复杂度是O(nm)的。主要的问题是在求
P
m
j=1
[ j , A
i+1
]
P
f
i, j
−1
k=1
E
k
，而这个可以优
化的。根据比较A[1, i]与其最长非自身border的式子，可以发现两式子之间只有O(1) 个 f
i, j
不
同，所以每次只需要重新维护这O(1)个值即可。这样时间复杂度就降为了O(n)。
可以发现这个方法十分复杂，并且扩展性低。而下面介绍的生成函数方法则会比这个
方法优越许多。
4.3 生成函数方法
令a
i
表示A[1, i]是否是A的一个border，a
i
为1表示是，0为不是。
令 f
i
为结束时随机序列长度为i的概率，其概率生成函数为F(x )。令辅助数列g
i
为随机序
列长度达到i且还未结束的概率，其普通生成函数为G(x)。
我们需要求的便是F
0
(1)。
通过分析可以得到如下等式：
F(x) + G(x) = 1 + G(x) · x (1)
G(x) ·
1
m
x
!
L
=
L
X
i=1
a
i
· F(x) ·
1
m
x
!
L−i
(2)
3
评论0
最新资源