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}即为数列{l,M,M2,M3……}的一个阶数为n的线性 递推式,该数列的最短线性递推式阶数不超过n。 线性生递推数列还满足以下的封闭性。 两关递推数列的性质和应用 福州第中学钟了谦 定理1.3.对于线性递推数列{a,a1,a…}、线性递推数列{bo,b1,b2…}、有限数列 {to,t1…m-1}、常数p,我们有 °{}z={a}0是线性递推数列 ·{a:p}是线性递推数列。 ·{a:+1}0是线性递推数列。 {a:+b}是线性递推数列。 {∑=0a,b=小=0是线性递推数列。 ab]o是线性递推数列。 以上引哩的证明较为简单,使用推论1.1和定1.2即可证明,由于篇幅所限这里略去。 1.3有关算法 求出一个数刎的最短线性递推式 我们先考虑有限数列的情况,即我们要对个有限数列求出最短线性递推式。假设运 算均在一个域上进行。 种简单的做法是使用高斯消元消元出最短线性递推式,对于长度为n的有限数列复 杂度为O(n3),而使用 Berlekamp-Massey算法可以将时间复杂度降到O(n2)。 对于一个有限数列{ao,a1,a2…an-n, Berlekamp-Massey算法会对于它的每个前缀 {co,a1,a2…a}求出这一前缀的最短线性递推式r,设p-1-l,即l1为线性递推 式r(的阶数。我们显然有r-1)={1},l=1≤l 引理1.1.如釆r-1)不是{ao,a1,a2…a}的最短线性递推式,那么 (l=1,i+1-l;-1) 证明.反证法,假设l≤i-l-1。设r(1={p0,1…p1},r(={q0,q1…qn} 那么山p的定义,对于4≤j≤我们都有4=-一a与 那么我们有 Pr a P>4 1k=1 k>,P14-j qkdi-k 两关递推数列的性质和应用 福州第中学钟了谦 所以r(-就是{a0,a1…a;}的最短线性递推式,矛盾。 所以l1≥i+1-11,又由单调性即证 事实上,引理1.1中的等号是可以取到的,以下我们给出这样的一种方案 考虑定理1.1,令A为数列a的生成函数,RO为r0的生成函数,那么就存在多项式 使得ARO)≡S((modx+1),其中deg(S()≤l-1 号虑由R1)推出R0。如果我们仍然有AR(D=S(-1)(mox+1),那么令R等于 即可。否则,我们有AR(1=S(-1)+dx(modx+1)。 考虑上一次增长递推式的情形,设当存在pl-1就对p和c进行 更新。时间复杂度O(n2) 对于无狠数列的情况,我们有如下定理 定理1.4.对于线性递推数列{ao,a1,a2…},若它的最短线性递推式阶数不超过s,那么 {ao,a1,a2…as+s-l}的最短线性递推式即为a的最短线性递推式。 证明.取最小的t≥s-s,满足{a0;a1,a2…as+3-1}的最短线性递推式r不是{ao,a1,a2…a} 的最短线性递推式,由引理1.1,我们就有{ao,a1,a2…a}的最短线性递推式长度至少为 1-l≥t+1-s≥s+s+1 S,矛盾 所以如果我们知道数列a最短线性递推式阶数的上界s,我们只需要求出这个数列长 度为2s的前缀并求出它的最短线性递推式即可。 1.3,2求出一个线性递推数列的某一项 假设我们有一个线性递推数列{ao,a,a2…}满足线性递推式(ro,r1…rm-1},考虑如何 对于k≥0求出ak 考虑设G(F)=∑oaxF(x),那么我们就是要求G(x) 注意到对于多项式a,b,我们有G(a+b)=G(a)+G(b)。由线性递推式的定义,对t≥0 我们有∑四0am-1-+1-0,即G(∑m=xm-1r)x)-0。所以设S(x)-∑=0xm-1,我 们就有G(S(x)x)=0(t≥0),又因为Ga+b)=G(a)+G(b),我们就有对任意多项式 T(x)、G(S(x)T(x)=0 两关递推数列的性质和应用 福州第中学钟了谦 考虑把κ和S(x)做带余除法,即设x=S(x)U(x)+R(x),其中UR为多项式且 dceg(R)<deg(S)。我们有G(S(x)U(x)=0,所以G(x)=G(x-S(x)U(x)=G(R(x)= G( xk mod s(x)。我们只需要类似快速幂地倍增k,每次把多项式对S(x)取模。 x' mod s(x) 的次数不超过m-2,我们再由定义带入a的前m-1项求出G即可。 求两个次数O(m)的多项式取模结果在模域下可以做到O(mlog(m))-时间复东度(可 以参见参考文献4),那么这个问题就可以在O(mlog(m)log(k)的时间复杂度内解决。 1.4常见应用 由于定理1.2,线性递推数列在与线性代数有关的问题中十分常见,本节提出一些常见 的应用。下文中无特别说明,均假设运算在模某个大质数p卜进行。 1.4.1求向量列和矩阵列的最短递推式 考虑如何求出n维行向量列{o,1,12…}的线性递推式。假设考虑在模p意义下随机 个n维列向量ν,转而计算{toν,t1v,l2v…}这个标量序列的最短线性递推式。 由 Schwartz-zippel引理(可参见参考文献[5]),我们可以推出有至少1-"的概率, tov,1v,2ν…}的最短线性递推式就是{to,t1,t2…}的最短线性递推式,所以我们只需要用 前述的方法求出最短线性递推式即可。 求矩阵列的最短递推式也是类似的,对于n行m列的矩阵列{to,t,t2…}的线性递推式 考虑在模p意义下随机一个n维列向量u和一个m维行向量v,转而计算{utnw,u1v,t2…} 这个标量序列的最短线性递推式。由 Schwartz- Zippel引埋,我们可以类似地推出有至少 1-2+的概率它们的最短线性递推式相同。 1.4.2求矩阵的最小多项式 nXn的矩阵M的最小多项式是次数最小的使得f(M)=0的多项式f。 类似定理1.2的证明,考虑{,M,M2…}的线性递推式{r,r1,n2…rm},那么我们有 ∑"01m=M=0,所以f(x)=∑morm-x即为矩阵M的一个零化多项式。所以矩阵M 的最小多项式就对应着{,M,M2…}的最短线性递推式,而由定理1.2它的阶数不超过n, 我们使用上一节中的方法求出最短线性递推式即可。 具休地,对于n维随机向量t,ν我们需要求出{uv,uMv,uM2y…uM2v。注意到 M+1=(uM)M,而向量乘上矩阵是可以在O(n2)时间内计算的,所以我们可以在O(n 时间内从前往后递推出{u,uM,uM2…lM2n},接下来再把每一项乘上v即可。时间复杂度 如果M是稀疏矩阵,假设其中有e个非零位置,那么向量乘上M的结果就可以在 (n+e)的时间内计算,我们就可以在O(n(n+e))的时间内求出{uv,uMv,