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}即为