logo资料库

国家集训队2019论文集.pdf

发布时间：2022-06-22 发布人：admin 分类：说明书 资料大小：2.86M 资料格式：pdf 举报 版权申诉
第1页 / 共231页
第2页 / 共231页
第3页 / 共231页
第4页 / 共231页
第5页 / 共231页
第6页 / 共231页
第7页 / 共231页
第8页 / 共231页
资料共231页，剩余部分请下载后查看
    两类递推数列的性质和应用 钟子谦
    浅谈图模型上的随机游走问题 王修涵
    《小水题》命题报告 杨骏昭
    浅谈图的点着色问题 高嘉煊
    浅谈格路计数相关问题 戴言
    算法竞赛中一些数论问题的推广与高斯整数初探 李佳衡
    《基础圆方树练习题》 命题报告 范致远
    《整点计数》命题报告以及对高斯整数的若干研究 徐翊轩
    浅谈树上分治算法 张哲宇
    《组合数求和》命题报告 吴思扬
    浅谈一类简洁数据结构 王思齐
    子串周期查询问题的相关算法及其应用 陈孙立
    《公园》命题报告 吴作同
    浅谈可追溯化数据结构 孔朝哲
    浅谈杨氏矩阵在信息学竞赛中的应用 袁方舟
    IOI2019 中国国家候选队论文集 ￿￿ 教练：张瑞喆 2019 年 5 月 ￿￿
    目 录 两类递推数列的性质和应用 钟子谦 浅谈图模型上的随机游走问题 王修涵 《小水题》命题报告 杨骏昭 浅谈图的点着色问题 高嘉煊 浅谈格路计数相关问题 戴言 算法竞赛中一些数论问题的推广与高斯整数初探 李佳衡 《基础圆方树练习题》命题报告 范致远 练 教 《整点计数》命题报告以及对高斯整数的若干研究 徐翊轩 集 文 论 队 浅谈树上分治算法 张哲宇 《组合数求和》命题报告 吴思扬 浅谈一类简洁数据结构 王思齐 选 候 家 国 国 中 《公园》命题报告 吴作同 浅谈可追溯化数据结构 孔朝哲 子串周期查询问题的相关算法及其应用 陈孙立 浅谈杨氏矩阵在信息学竞赛中的应用 袁方舟 IOI2019 月 5 2019 喆 瑞 张 ： 1 年 17 27 38 55 69 89 104 122 130 141 152 165 192 202
    两类递推数列的性质和应用 福州第三中学 钟子谦 两类递推数列的性质和应用 福州第三中学 钟子谦 摘 要 线性递推数列和整式递推数列是数学中常见的两类递推数列，本文介绍了这两类递推 数列的定义、性质和有关算法，并展示了它们在信息学竞赛中的一些应用。 前言 练 教 线性递推数列被引入算法竞赛界已经有至少五年，但是一直没有得到特别广泛的普及。 整式递推数列是线性递推数列的一个自然的拓展，近两年才被引入信息学竞赛。本文希望 能够系统介绍这两类数列的性质和在信息学竞赛中的用途，使读者在思考有关问题时有迹 可循。 本文首先在第 1 节介绍了线性递推数列，接下来在第 2 节介绍了整式递推数列。对于 这两类数列，本文介绍了它们的定义、性质、有关算法和实际例题，对于线性递推数列本文 还介绍了一些与线性代数相关的应用。 文 集 喆 瑞 张 ： 月 5 年 2019 1 线性递推数列 论 队 选 候 家 国 1.1 定义 ￿ 定义 ￿ 1.1. 我们称长度有限的数列为有限数列，长度无限的数列为无限数列。 中 国 ￿ 定义 ￿ 1.2. 我们称形式幂级数 F 最高次项的次数为形式幂级数 F 的次数，记为 deg(F) （可能为 1）。特别地，我们定义零多项式的次数为负无穷大（1）。 ∑n1 ￿ 定义 ￿ 1.3. 对于有限数列 fa0; a1; a2 an1g，我们定义它的生成函数为多项式 A(x) = ∑1 i=0 aixi。对于无限数列 fa0; a1; a2 g，我们类似地定义它的生成函数为形式幂级数 A(x) = i=0 aixi。 ￿ 定义 ￿ 1.4. 对于无限数列 fa0; a1; a2 g 和有限非空数列 fr0; r1; r2 rm1g，若对于任意 p m 1，有 k=0 apkrk = 0，则称数列 r 为数列 a 的线性递归式。若 r0 = 1，我们称数 列 r 为数列 a 的线性递推式。我们称存在线性递推式的无限数列为线性递推数列。 ∑m1 1 IOI2019
    两类递推数列的性质和应用 福州第三中学 钟子谦 对于有限数列 fa0; a1; a2 an1g 和有限非空数列 fr0; r1; r2 rm1g，类似地，若对于任 k=0 apkrk = 0，则称数列 r 为数列 a 的线性递归式。若 r0 = 1， 意 m 1 p n 1，有 我们称数列 r 为数列 a 的线性递推式。 我们称这个线性递推式的阶数为它的长度减一，称数列 a 阶数最小的线性递推式为数 ∑m1 月 5 年 列 a 的最短线性递推式。 1.2 基本性质和判定方法 在生成函数的观点下看线性递归式，我们有如下结论： 2019 喆 ∑m1 定理 1.1. 对于无限数列 fa0; a1; a2 g 和有限非空数列 fr0; r1; r2 rm1g，设数列 a 和数列 r 所对应的生成函数为 A 和 R，数列 r 为数列 a 的线性递归式等价于存在次数不超过 m 2 的多项式 S 满足 AR + S = 0。 对于有限数列 fa0; a1; a2 an1g 和有限数列 fr0; r1; r2 rm1g，设数列 a 和数列 r 所对 应的生成函数为 A 和 R，数列 r 为数列 a 的线性递归式等价于存在次数不超过 m 2 的多 项式 S 满足 AR + S 0 (mod xn)。 ： 张 瑞 证明. 下面证明无限数列的情况，有限数列的情况也是类似的。 对于 k m 1，考察两侧 xk 次项的系数，我们有 [xk](A(x)R(x)) = 需要取适当的 S 使得低次项系数为 0 即可。 j=0 r jak j = 0。只 □ 练 教 接下来我们介绍几种常见的判定线性递推数列的方法。 ￿ 推论 1.1. 对于无限数列 fa0; a1; a2 g，设数列 a 所对应的生成函数为 A，a 为线性递推 数列当且仅当存在常数项为 1 的多项式 R 和多项式 S 满足 A = S R 。数列 a 的最短线性递 推式阶数就是对于这样的 R 和 S ，max(deg(R); deg(S ) + 1) 的最小可能值。 队 证明. 由定理1.1移项即得。 □ 定理 1.2. 对于一个 n n 的矩阵 M，无限数列 fI; M; M2; M3 g 是一个线性递推数列，它 的最短线性递推式阶数不超过 n。 选 候 集 文 论 证明. 考虑矩阵 M 的特征多项式 p，它满足 deg(p) = n，[xn]p(x) = 1。由 Cayley-Hamilton 定理，我们有 p(M) = 0。该定理的证明可参见参考文献 [2]，由于和本文主题关系不大，这 里略去。 中 ∑n i=0 cniMi+ j = 0， 设 p(x) = i=0 ciM j+ni = 0。所以 fc0; c1 cng 即为数列 fI; M; M2; M3 g 的一个阶数为 n 的线性 □ 即 递推式，该数列的最短线性递推式阶数不超过 n。 i=0 cniMi = 0，两边乘 M j 得 i=0 cnixi，p(M) = 0 即 ∑n ∑n 家 国 ∑n 国 IOI2019 线性递推数列还满足以下的封闭性。 2
    两类递推数列的性质和应用 福州第三中学 钟子谦 定理 1.3. 对于线性递推数列 fa0; a1; a2 g、线性递推数列 fb0; b1; b2 g、有限数列 ft0; t1 tm1g、常数 p，我们有： 月 5 年 2019 • faibig1 以上引理的证明较为简单，使用推论1.1和定理1.2即可证明，由于篇幅所限这里略去。 faig1 i=0 • ftigm1 • fai pg1 • fai+1g1 • fai + big1 • f∑i i=0 是线性递推数列。 i=0 是线性递推数列。 i=0 是线性递推数列。 i=0 是线性递推数列。 i=0 是线性递推数列。 j=0 a jbi jg1 i=0 是线性递推数列。 1.3 有关算法 1.3.1 求出一个数列的最短线性递推式 喆 瑞 张 ： 练 教 集 文 我们先考虑有限数列的情况，即我们要对一个有限数列求出最短线性递推式。假设运 算均在一个域上进行。 一种简单的做法是使用高斯消元消元出最短线性递推式，对于长度为 n 的有限数列复 杂度为 O(n3)，而使用 Berlekamp-Massey 算法可以将时间复杂度降到 O(n2)。 对于一个有限数列 fa0; a1; a2 an1g，Berlekamp-Massey 算法会对于它的每个前缀 fa0; a1; a2 aig 求出这一前缀的最短线性递推式 r(i)，设 jr(i)j 1 = li，即 li 为线性递推 式 r(i) 的阶数。我们显然有 r(1) = f1g，li1 li。 引理 1.1. 如果 r(i1) 不是 fa0; a1; a2 aig 的最短线性递推式，那么 队 论 家 li max(li1; i + 1 li1) 证明. 反证法，假设 li i li1。设 r(i1) = fp0; p1 pli1 那么由 r(i) 的定义，对于 li j i 我们都有 a j = ∑li 国 中 li∑ li1∑ 那么我们有 p jai j = 国 k=1 p j j=1 qkai jk (i li1 li) g，r(i) = fq0; q1 qli t=1 qta jt。 g。 选 候 li1∑ j=1 li1∑ li∑ = li∑ k=1 = qk p jai jk j=1 qkaik = ai k=1 3 IOI2019
    月 5 两类递推数列的性质和应用 福州第三中学 钟子谦 所以 r(i1) 就是 fa0; a1 aig 的最短线性递推式，矛盾。 □ 所以 li i + 1 li1，又由单调性即证。 事实上，引理1.1中的等号是可以取到的，以下我们给出这样的一种方案。 考虑定理1.1，令 A 为数列 a 的生成函数，R(i) 为 r(i) 的生成函数，那么就存在多项式 S (i) 使得 AR(i) S (i) (mod xi+1)，其中 deg(S (i)) li 1。 R(i1) 即可。否则，我们有 AR(i1) S (i1) + dxi (mod xi+1)。 考虑由 R(i1) 推出 R(i)。如果我们仍然有 AR(i1) S (i1) (mod xi+1)，那么令 R(i) 等于 考虑上一次增长递推式的情形，设当时存在 p < i 和 c 使得 AR(p1) S (p1) + cxp (mod xp+1)，那么将两侧乘上 xipdc1，我们有 Axipdc1R(p1) xipdc1S (p1) + dxi (mod xi+1)。 2019 将上述两式相减我们就有 A(R(i1) xipdc1R(p1)) S (i1) xipdc1S (p1) (mod xi+1)， 喆 年 所以我们令 R(i) 等于 R(i1) xipdc1R(p1) 即可。 可以发现，我们这样构造出的 R 和 S 一定满足 li = max(li1; i + 1 li1)。考虑归纳证 明，由于在 p 处增长了递推式，由归纳假设我们就有 lp = p + 1 lp1，则 li = max(li1; i p + lp1) = max(li1; i lp + 1)。 ： 我们只需要从小到大枚举 i 并如上计算 R(i) 和 li 即可，如果 li > li1 就对 p 和 c 进行 练 瑞 张 更新。时间复杂度 O(n2)。 对于无限数列的情况，我们有如下定理。 教 集 文 IOI2019 选 候 家 国 定理 1.4. 对于线性递推数列 fa0; a1; a2 g，若它的最短线性递推式阶数不超过 s，那么 fa0; a1; a2 as+s1g 的最短线性递推式即为 a 的最短线性递推式。 证明. 取最小的 t s+ s，满足 fa0; a1; a2 as+s1g 的最短线性递推式 r 不是 fa0; a1; a2 atg 的最短线性递推式，由引理1.1，我们就有 fa0; a1; a2 atg 的最短线性递推式长度至少为 t + 1 lt t + 1 s s + s + 1 s > s，矛盾。 □ 队 论 所以如果我们知道数列 a 最短线性递推式阶数的上界 s，我们只需要求出这个数列长 度为 2s 的前缀并求出它的最短线性递推式即可。 中 1.3.2 求出一个线性递推数列的某一项 国 假设我们有一个线性递推数列 fa0; a1; a2 g 满足线性递推式 fr0; r1 rm1g，考虑如何 ∑m1 ∑1 对于 k 0 求出 ak。 考虑设 G(F) = 注意到对于多项式 a; b，我们有 G(a + b) = G(a) +G(b)。由线性递推式的定义，对 t 0 i=0 xm1iri，我 我们有 们就有 G(S (x)xt) = 0 (8t 0)，又因为 G(a + b) = G(a) + G(b)，我们就有对任意多项式 T (x)，G(S (x)T (x)) = 0。 i=0 xm1iri)xt) = 0。所以设 S (x) = i=0 ai[xi]F(x)，那么我们就是要求 G(xk)。 i=0 am1i+tri = 0，即 G(( ∑m1 ∑m1 4
    两类递推数列的性质和应用 福州第三中学 钟子谦 考虑把 xk 和 S (x) 做带余除法，即设 xk = S (x)U(x) + R(x)，其中 U; R 为多项式且 deg(R) < deg(S )。我们有 G(S (x)U(x)) = 0，所以 G(xk) = G(xk S (x)U(x)) = G(R(x)) = G(xk mod S (x))。我们只需要类似快速幂地倍增 k，每次把多项式对 S (x) 取模。xk mod S (x) 的次数不超过 m 2，我们再由定义带入 a 的前 m 1 项求出 G 即可。 求两个次数 O(m) 的多项式取模结果在模域下可以做到 O(m log(m)) 的时间复杂度（可 以参见参考文献 [4]），那么这个问题就可以在 O(m log(m) log(k)) 的时间复杂度内解决。 年 月 5 1.4 常见应用 由于定理1.2，线性递推数列在与线性代数有关的问题中〸分常见，本节提出一些常见 的应用。下文中无特别说明，均假设运算在模某个大质数 p 下进行。 2019 喆 瑞 张 ： 1.4.1 求向量列和矩阵列的最短递推式 练 考虑如何求出 n 维行向量列 ft0; t1; t2 g 的线性递推式。假设考虑在模 p 意义下随机 一个 n 维列向量 v，转而计算 ft0v; t1v; t2vg 这个标量序列的最短线性递推式。 由 Schwartz-Zippel 引理（可参见参考文献 [5]），我们可以推出有至少 1 n p 的概率， ft0v; t1v; t2vg 的最短线性递推式就是 ft0; t1; t2 g 的最短线性递推式，所以我们只需要用 前述的方法求出最短线性递推式即可。 求矩阵列的最短递推式也是类似的，对于 n 行 m 列的矩阵列 ft0; t1; t2 g 的线性递推式， 考虑在模 p 意义下随机一个 n 维列向量 u 和一个 m 维行向量 v，转而计算 fut0v; ut1v; t2vg 这个标量序列的最短线性递推式。由 Schwartz-Zippel 引理，我们可以类似地推出有至少 1 n+m p 的概率它们的最短线性递推式相同。 论 文 集 教 1.4.2 求矩阵的最小多项式 家 国 ∑m ∑m n n 的矩阵 M 的最小多项式是次数最小的使得 f (M) = 0 的多项式 f 。 类似定理1.2的证明，考虑 fI; M; M2 g 的线性递推式 fr0; r1; r2 rmg，那么我们有 i=0 rmixi 即为矩阵 M 的一个零化多项式。所以矩阵 M i=0 rmiMi = 0，所以 f (x) = 的最小多项式就对应着 fI; M; M2 g 的最短线性递推式，而由定理1.2它的阶数不超过 n， 我们使用上一节中的方法求出最短线性递推式即可。 具体地，对于 n 维随机向量 u; v 我们需要求出 fuv; uMv; uM2v uM2nvg。注意到 uMi+1 = (uMi)M，而向量乘上矩阵是可以在 O(n2) 时间内计算的，所以我们可以在 O(n3) 时间内从前往后递推出 fu; uM; uM2 uM2ng，接下来再把每一项乘上 v 即可。时间复杂度 O(n3)。 国 中 如果 M 是稀疏矩阵，假设其中有 e 个非零位置，那么向量乘上 M 的结果就可以在 O(n + e) 的时间内计算，我们就可以在 O(n(n + e)) 的时间内求出 fuv; uMv; uM2v uM2nvg， 队 选 候 5 IOI2019
    月 5 两类递推数列的性质和应用 福州第三中学 钟子谦 从而在 O(n(n + e)) 的时间内求出它的最小多项式。 1.4.3 优化动态规划 一类常见的动态规划问题具有如下的递推关系式： f (i; j) = 1; j 2 [0; m))，给定 f (0; j) ( j 2 [0; m))，需要求出 f (n; j) ( j 2 [0; m))。 ∑m1 t=0 f (i 1; t)c(t; j) (i 记 F(i) 为 f (i; j) ( j 2 [0; m)) 所对应的行向量，C 为 c 所对应的 m m 矩阵，那么我们 有 F(i) = F(i 1)C (i 1)，所以 F(n) = F(0)Cn。常见的优化方法是使用矩阵乘法快速幂 求出 Cn，之后乘上 F(0) 得到结果，复杂度 O(m3 log(n))。 2019 由定理1.2我们有 fCngn 是线性递推数列，所以 fF(n)gn 也是线性递推数列，用上述的方 法求出 fF(0); F(1); F(2)g 的最短线性递推式后我们再用节1.3.2中的方法求出 F(n) 即可， 时间复杂度 O(m3 + m log(m) log(n))（求 fF(0); F(1); F(2) F(n + n 1)g 需要 O(m3) 的时 间复杂度）。 瑞 喆 年 张 ： 练 1.4.4 解稀疏线性方程组 教 集 ∑m1 有一个 n n 的满秩矩阵 A 和一个长度为 n 的行向量 b，我们需要求出一个长度为 n 的行向量 x 满足 Ax = b。 由于 A 是满秩的，我们有 x = A1b，其中 A1 表示 A 的逆矩阵。 考虑求出 fb; Ab; A2b; A3bg 的最短递推式 fr0; r1; r2 rm1g，由定理1.2这样的递推 i=0 Aibrm1i = 0，注意到 rm1 , 0（否则去 i=0 Ai1brm1i = 0，所以 瓶颈在于求 fb; Ab; A2b; A3b A2nbg。假设 A 中有 e 个非零位置，那么我们从前往后递 式一定存在且阶数不超过 n，那么我们有 掉 rm1 即为一个更短的递推式），我们在两边乘上 A1 就有 A1b = 1 i=0 Aibrm2i)。 ∑m2 ∑m1 论 文 rm1 ( 推地求出这个向量序列的时间复杂度为 O(ne)，总的时间复杂度就为 O(n(n + e))。 队 1.4.5 求稀疏矩阵行列式 国 对于输入的 n n 的满秩矩阵 A，我们需要求出 det(A)。 注意到我们可以快速地求出稀疏矩阵的最小多项式（见节1.4.2），而当矩阵的每个特征 值的几何重数均为一时最小多项式就是特征多项式。对于 n 阶矩阵，特征多项式的常数项 乘上 (1)n 即为行列式（因为行列式即全部特征值的乘积）。 国 由于 A 不一定满足该性质，考虑将输入矩阵乘上一个新的矩阵 B。我们取 B 为一个 n n 的模 p 意义下的随机对角矩阵，那么我们可以证明 AB 有至少 1 2n2n p 的概率满足该 性质1。求出 det(AB) 后注意到 det(AB) = det(A) det(B)，而 det(B) 就是对角线上各个元 中 1事实上，所有特征值的代数重数均为 1 的概率至少为 1 2n2n p ，证明可参见 [7] 定理 4.3 选 候 家 IOI2019 6
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料