IOI2018中国国家候选队论文集正式版.pdf-资料库

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第1页.png

第1页 / 共210页

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第2页.png

第2页 / 共210页

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第3页.png

第3页 / 共210页

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第4页.png

第4页 / 共210页

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第5页.png

第5页 / 共210页

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第6页.png

第6页 / 共210页

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第7页.png

第7页 / 共210页

09be4308-4a42-4770-a2fa-730be4de2f1a.pdf-第8页.png

第8页 / 共210页

IOI2018 中国国家候选队论文集教教教练练练：：：张张张瑞瑞瑞喆喆喆 2018年 4月

目录浅谈生成函数在掷骰子问题上的应用杨懋龙《后缀树结点数》命题报告及一类区间问题的优化陈江伦浅谈保序回归问题高睿泉《Fim 4》命题报告吴瑾昭解决树上连通块问题的一些技巧和工具任轩笛《Jellyﬁsh》命题报告及拓展探究梁晏成 Leafy Tree 及其实现的加权平衡树王思齐《小H爱染色》命题报告陈嘉乐一些特殊的数论函数求和问题朱震霆浅谈DFT在信息学竞赛中的应用刘承奥《完美的队列》命题报告林旭恒浅谈拟阵的一些拓展及其应用杨乾澜浅谈Splay与Treap的性质及其应用董炜隽《最小方差生成树》命题报告何中天欧拉图相关的生成与计数问题探究陈通 1 11 23 34 45 58 75 87 92 113 132 143 164 180 192

浅谈生成函数在掷骰子问题上的应用长沙市长郡中学杨懋龙浅谈生成函数在掷骰子问题上的应用长沙市长郡中学杨懋龙摘要掷骰子问题是算法竞赛中的一类常见问题。通过对这一类问题的认真研究，作者得出，这类问题都可以使用生成函数来解决。因此本文围绕掷骰子系列问题，阐述如何用生成函数来一步步解决问题，以及相较于传统做法，用生成函数解决问题的优越性。关键词：生成函数、掷骰子问题、概率与期望 1 引言掷骰子问题是算法竞赛中的一类常见问题，在近年的竞赛中多次出现。而生成函数又是解决这类问题一个有效工具，与传统方法相比具有易于计算且扩展性强等优点。但现在OI界对这种方法的研究十分稀少。第2节中，约定了一些符号。第3节中，介绍了概率生成函数的定义，以及一些性质。第4节中，介绍了该算法的基础应用。第5、6节中，结合题目介绍了一些更复杂的应用。 2 符号约定符号1. Ai表示序列A的第i个数字。符号2. A[l, r]表示序列A的第l个数字到第r个数字组成的序列。符号3. f (k)(x)为 f (x)的k阶导数。符号4. [P]为艾佛森括号，如果方括号内的条件满足则为1，不满足则为0。 3 预备知识 3.1 普通生成函数数列a0, a1, a2, . . . 的普通生成函数为： 1

浅谈生成函数在掷骰子问题上的应用 ∞ i=0 aixi A(x) = 长沙市长郡中学杨懋龙 3.2 概率生成函数如果对于数列a0, a1, a2, . . . ，存在某个离散随机变量X满足Pr(X = i) = ai，那么an(n ∈ N)的普通生成函数被称为X的概率生成函数。也就是说，如果X是非负整数集N上的离散随机变量，那么X的概率生成函数为： ∞ F(z) = E(zX) = Pr(X = i)zi 3.2.1 概率生成函数性质 i=0 因为是X是非负整数集N上的离散随机变量，所以必有 F(1) = Pr(X = i) = 1 ∞ ∞ i=0 i=0 对F(z)求导，得到所以X的期望 F(z) = i Pr(X = i) · zi−1 ∞ i Pr(X = i) E(x) = F(1) = 进一步推导可以得到所以X的方差 i=0 E(Xk) = F(k)(1), k 0 Var(X) = F(1) + F(1) − (F(1))2 3.3 border 对于一个长度为L的序列A，若A[1, i] = A[L − i + 1, L]，则称A[1, i]是A的一个border。 4 基本题型例题1. 歌唱王国1 1来源：CTSC2006 2

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

浅谈生成函数在掷骰子问题上的应用长沙市长郡中学杨懋龙 (1)的意义是在一个未结束的序列后加一个数字，可能结束也可能没结束，1是初始时随机序列为空的情况。 (2)的意义是在一个未结束的序列后加上给定序列，则必定会结束，但是有可能在未加到L个数字时就已经结束了，这时一定要满足已经添加的序列是给定序列的一个border。将(1)求导并代入x = 1可得再将x = 1代入(2)可得 F(x) + G(x) = G(x) · x + G(x) F(1) = G(1) G(1) · L−i 1 m L 1 m = G(1) = L L i=1 i=1 ai · F(1) · ai · mi (3) (4) L 由(3)(4)可知F(1) = 使用KMP算法或hash便可以在O(L)的时间复杂度内求出ai并计算出F(1)。 i=1 ai · mi。 4.4 进一步思考我们可以进一步得到求方差的方法。根据Var(X) = F(1) + F(1)− (F(1))2，可知只需要知道F(1)和F(1)即可，F(1)已经知道了，那么就是要求F(1)。将(1)求二阶导并代入x = 1可得 F(x) + G(x) = G(x) + G(x) · x + G(x) F(1) = 2G(1) 再将(2)求导并代入x = 1可得 i=1 L L L i=1 i=1 G(x) = G(x) = G(1) = ai · mi · F(x) · x−i ai · mi · (F(x) · x−i − i · F(x) · x−i−1) ai · mi · (F(1) − i) 所以F(1) = 2 ·L i=1 ai · mi · (F(1) − i)。 4

浅谈生成函数在掷骰子问题上的应用长沙市长郡中学杨懋龙如果再进一步推导并归纳可以得到 F(k)(1) = k · L ai · mi k−1 (−1) j k − 1 j (i + j − 1)! (i − 1)! F(k−1− j)(1) i=1 j=0 4.5 小结使用生成函数来解决这类问题的方法通常是先定义一个概率生成函数F(x)和一个辅助生成函数G(x)，然后是在未结束的情况后加入一个数或一个给定序列，并根据实际情况来列出方程。最后通过代值和求导来解出所需要的F(1)。 5 复杂的题型例题2. 抛骰子游戏给定n个长度分别为Li的序列Ai。再给出一个标有1到m的骰子，其中抛出i的概率为Pi。然后每次抛一次骰子将骰子上的数字加入到初始为空的序列B末尾，如果给定的n个序列都是B的子串，则停止，求序列B的期望长度。保证n ≤ 15，L ≤ 20000，m ≤ 105。 5.1 分析这个问题本质还是掷骰子问题，但是变成了需要n个序列都在其中出现。 5.2 解法令Ti为Ai首次出现时随机序列的长度，那么要求的就是E( max 如果一个序列Ai是另一个序列A j的子串，那么必有Ti ≤ T j，可以将Ai去除。 Ti。 max不太好求，对其进行Min-Max容斥， Ti = i∈{1,2,...,n} Ti)。 (−1)|S|+1 min i∈S nmax i=1 Ti)，即有一个出现就结束。不妨假设S = {1, 2, . . . , n}。 S⊆{1,2,...,n} 根据期望的线性性，可以转换为求E(min i∈S 定义P(A) = Pi。 i∈A Ai[1, k] = A j[L j − k + 1, L j] 令ai, j,k = 令 fi, j为首次出现的是序列Ai且随机序列的长度为 j的概率，其普通生成函数为Fi(x)。令。辅助数列gi为随机序列长度达到i且还未结束的概率，其普通生成函数为G(x)。 5

浅谈生成函数在掷骰子问题上的应用长沙市长郡中学杨懋龙 ai, j,k · F j(x) · P(Ai[k + 1, Li]) · xLi−k,∀i ∈ S (5) (6) 可以得到如下等式： Fi(x) + G(x) = 1 + G(x) · x Li n G(x) · P(Ai)xLi = n F i (1)。 i=1 j=1 k=1 要求的便是对(5)求导并将x = 1代入得将x = 1代入(6)可得 G(1) = n Li ( j=1 k=1 n i=1 n i=1 n i=1 F i (1) = G(1) ai, j,k · 1 P(Ai[1, k]) ) · F j(1),∀i ∈ S n i=1 现在有n +1个未知数，但只有n个方程。可以发现 Fi(x)为随机序列长度的概率生成函数，所以有 Fi(1) = 1。这样就可以高斯消元求出G(1)了。同时还可以得到Fi(1)，即首次出现的序列是第i个序列的概率，如[SDOI2017]硬币游戏就是要求Fi(1)。使用hash可以在O(n2L)的时间复杂度内求出a数组并对于每组(i, j)计算出 ai, j,k· 对于每个S 在O(n3)内可以高斯消元解出G(1)。所以总时间复杂度为O(n2L + 2nn3)。 k=1 1 P(Ai[1,k]) ， Li 6 一些新的应用 6.1 模糊匹配例题3. Dice2 一个m面的公平骰子，求最后n次结果相同就结束的期望次数或者求最后n次结果全不同就结束的期望次数。保证n, m ≤ 106，且对第二问保证n ≤ m。 6.1.1 传统差分方法第一问令 fi为当前状态满足后i次相同，从当前状态到结束的期望掷骰子次数。那么要求的就是 f0。 2来源：2013 Multi-University Training Contest 5 6

资料库

IOI2018中国国家候选队论文集正式版.pdf

相关推荐

课程资源

热门标签

最新资料