国家集训队2019论文集.zip

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,