国家集训队2019论文集.zipIOI国家集训队2019论文集，目录：钟子谦 - 《两类递推数列的

文件名称: 国家集训队2019论文集.zip

所属分类: 专业指导

开发工具:

文件大小: 2mb

下载次数: 0

上传时间: 2020-04-04

提供者: huangy*******

下载 (2mb)

不能下载？报告错误

详细说明：IOI国家集训队2019论文集，目录：钟子谦 - 《两类递推数列的性质和应用》王修涵 - 《浅谈图模型上的随机游走问题》杨骏昭 - 《“小水题”命题报告》高嘉煊 - 《浅谈图的点着色问题》戴言 - 《浅谈格路计数相关问题》李佳衡 - 《算法竞赛中一些数论问题的推广与高斯整数初探》范致远 - 《“基础圆方树练习题”命题报告》徐翊轩 - 《“整点计数”命题报告以及对高斯整数的若干研究》张哲宇 - 《浅谈树上分治算法》吴思扬 - 《“组合数求和”命题报告》王思齐 - 《浅谈一类简洁数据结构》陈孙立 - 《子串周期查询问题的相关算法及其应用》吴作同两关递推数列的性质和应用福州第中学钟了谦两类递推数列的性厉和应用福州第三中学钟子谦摘要线性递推数列和整式递搾数列是数学中常见的两类递推数列,本文介绍了这两类递推数列的定义、性质和有关算法,并展示了它们在信息学竞赛中的一些应用。前言线性递推数列被引入算法竞赛界凵经有至少互年,但是直没有得到特别广泛的普及整式递推数列是线性递推数列的一个自然的拓展,近两年才被引入信息学竞赛。本文希望能够系统介绍这两类数列的性质和在信息学竞赛中的用途,使读者在思考有关问题时有迹可循本文首先在第1节介绍了线性递推数列,接下来在第2节介绍了整式递推数列。对于这两类数列,本文介绍了它们的定义、性质、有关算法和实际例题,对于线性递推数列本文还介绍了些与线性代数相关的应用。 1线性递推数列 1.1定义定义1.1.我们称长度有限的数列为有限数列,长度无限的数列为无限数列。定义1.2.我们称形式幂级教F最高次项的次数为形式幂级数F的次数,记为deg(F) (可能为α)。特别地,我们定义零多项式的次数为负无穷大(-0)。定义13.对于有限数列{a0,a1,a2…an-1},我们定义它的生成函数为多项式A(x) ∑=ax。对于无限数列{ao,a1,a2…},我们类似地定义它的生成函数为形式幂级数A(x) 定义1.4.对于无限效列{0,a1,u2…}和有限非空数列{ro,r1,r2…rm-n},若对于任意卩≥m-1,有∑ank=0,则称数列r为数列a的线性递归式。若ro=1,我们称数列r为数列a的线性递推式。我们称存在线性递推式的无限数列为线性递推数列两关递推数列的性质和应用福州第中学钟了谦对于有限数列{a0,a1,a2…an-l和有限非空教列{ro,r1,r2…rm-1},类似地,若对于任意m-1≤卩≤n-1,有∑四=an-k-0,则称数列r为数列a的线性递归式。若10-1 我们称数列r为数列a的线性递推式。我们称这个线性递推式的阶数为它的长度减一,称数列a阶数最小的线性递推式为数列a的最短线性递推式。 12基本性质和判定方法在生成函数的观点下看线性递归式,我们有如下结论定理11.对于无限数列{a,a1,a2…}和有限非空数列{ro,n1,r2…rm-1},设数列a和数列 r所对应的生成函数为A和R,数列r为数列a的线性递归式等价于存在次数不超过m-2 的多项式S满足AR+S=0。对于有限数列{a0,a1,a2…an-1}和有限数列{r,r1,r2…Fm-1},设数列a和数列r所对应的生成函数为A和R,数列厂为数列a的线性递归式等价于存在次数不超过m-2的多项式S满足AR+S≡0(modx)。证明.下面证明无限数列的情况,有限数列的情况也是类似的对于k≥m-1,考察两侧x次项的系数,我们有[x(x)R(x)=∑mbra-=0。只需要取适当的S使得低次项系数为0即可接下来我们介绍儿种常见的判定线性递推数列的方法。推论1.1.对于无限数列{a,a1,a2∵},设数列a所对应的生成函数为A,a为线性递推数列当且仅当存在常敖项为1的多项式R和多项式S满足A=是。数列a的最短线性递推式阶数就是对于这样的R和S,max(deg(R),deg(S)+1)的最小可能值。证明.由定理1.1移项即得定理1.2.对于一个nXn的矩阵M,无限数列{,M,M2,M3…)是一个线性递推数列,它的最短线性递推式阶数不超过n 证明.考虑矩阵M的特征多项式p,它满足deg(p)=n,xlp(x)=1。 I Cayley-Hamilton 定理,我们有p(M)=0。该定理的证明可参见参考文献2],由于和本文主题关系不大,这里略厶。设p(x)=∑=0Cnx,P(M)=0即∑:0Cm-M=0,两边乘M得∑=0CnM+!=0 即∑0c;M件+=0。所以{c,C1…cn}即为

(系统自动生成,下载前可以参看下载内容)