国家集训队2019论文集.pdf

所需积分/C币:45 2019-09-16 17:24:30 2.86MB PDF
148
收藏 收藏
举报

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)。 考虑上一次增长递推式的情形,设当存在p<i和c使得ARP)≡S(-1)+cx ( mod xp+1),那么将两侧乘上x-pdc-1,我们有Axdc-1Rp1)≡x-palc-lS(p1)+dx2 mod x 将上述两式相减我们就有A(R-1)-xndc1R(p1)≡S(-1)- x'pdc Is(p1)(modx+1), 所以我们令R等于R(-1)-x-cR(p)即可。 可以发现,我们这样构造出的R和S一定满足l=max(1-1,i+1-l-1)。考虑归纳证 明,由于在p处增长了递推式,归纳假设我们就有lp=p+1-ln-1,则l=max(l-1 P+lp-1)=max(l-1,-ln+1)。 我们只需要从小到大枚举i并如上计算R(和l即可,如果l1>l-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,mM2y…uM2"w}, 5 两关递推数列的性质和应用 福州第中学钟了谦 从而在O(n(n+c)的时间内求出它的最小多项式 1.4.3优化动态规划 类常见的动态规划问题具有如下的递推关系式:f(i,)=∑m=f(-1,1)c(,j(≥ 1,j∈O,m).给定f(0,)(j∈0,m),需要求出f(n,)(i∈O,m) 记F(i)为f(i,j(∈[0,m)所对应的行向量,C为c所对应的m×m矩阵,那么我们 有F()=F(-1)C(≥1),所以F(m)=F(0)C。常见的优化方法是使用矩阵乘法快速幂 求出Cn,之后乘上F(0)得到结果,复杂度O(m3log(n) 由定理12我们有{C"ln是线生爍推数列,所以{F(m)}n也是线性递推数列,用上述的方 法求出{F(0),F(1),F(②2)……}的最短线性递推式后我们再用节1.3.2中的方法求出F(m)即可, 时间复杂度O(m2+mlog(m)log(n)(求{F(0),F(1),F(2)…F(n+n-1)需要O(m3)的时 复杂度)。 1.4.4解稀疏线性方程组 有一个n×n的满秩矩阵A和一个长度为n的行向量b,我们需要求出一个长度为n 的行向量x满足Ax=b。 由于A是满秩的,我们有x=A-1b,其中A-1表示A的逆矩阵。 考虑求出{,Ab,A2b,A3b…}的最短递推式{ro,n1,r2…rm1},巾定理1.2这样的递推 式一定存在且阶数不超过n,那么我们有∑Abm21=0,注意到rm1≠0(否则去 掉rm1即为一个更短的递推式),我们在两边乘上A-就有∑0A1brm1-7=0,所以 A-b=-(2 A'brm-2-i) 瓶颈在于求{b,Ab,A2b,A3b…Ab}。假设A中有e个非零位置,那么我们从前往后递 推地求出这个向量序列的时间复杂度为O(ne),总的时间复杂度就为O(nmn+e) 1.4.5求稀疏矩阵行列式 对于输入的nn的满秩矩阵A,我们需要求出det(A)。 注意到我们可以快速地求出稀疏矩阵的最小多项式(见节1.4.2),而当怎阵的每个特征 值的几何重数均为一时最小多项式就是特征多项式。对于n阶矩阵,特征多项式的常数项 乘上(-1)"即为行列式(因为行列式即全部特征值的乘积)。 由于A不一定满足该性质,考虑将输入矩阵灭上一个新的矩阵B。我们取B为一个 n×n的模p意义下的随机对角矩阵,那么我们可以证明AB有至少1-2的概率满足该 性质1。求出det(AB)后注意到det(AB)=det(A)det(B),而det(B)就是对角线上各个元 事实⊥,所有特征值的代数重数均为1的概率至少为1-22=,证明可参见团]定理43 两关递推数列的性质和应用 福州第中学钟了谦 素的乘积,相除即可得到det(A)的值。 设A中有e个非零位置,该做法的时间复杂度即为O(n(n+e) 1.4.6求稀疏矩阵秩 对于输入的n×m的矩阵A,我们需要求出ramk(A)。 注紊到一个n×n矩阵的秩即为矩阵的阶数n减去特征值0的代数重数,所以如果我 们求出了这个矩阵的特祉多项式f(x),只需要除去其中的所有因子x,剩余多项式的次数 就是矩阵的秩。如果矩阵的特征多项式等于最小多项式乘上一个x的次幂,那么我们只需 要求出最小多项式并除去其中的所有因子x即可。 考虑先把矩阵A转化为一个n×n的对称矩阵。我们在模p意义下随机生成一个m×m 的对角矩阵D1,矩阵AD1A7就是一个n×n的对称矩阵,)且它的秩有至少1-的概率 与矩阵A相同2。接着我们在模p意义下随机生成一个n×n的对角矩阵D2,D2AD1AD2 这一矩阵就有至少1-4概率满足特征多项式等于最小多项式乘上一个x的次幂3。我们 求出它的最小多项式并计算即可。 求最小多项式时我们需要对一个向量乘上D2AD1AD2,由于D2,D1,A,AT都是稀疏的, 我们只需要依次乘入即可。设A中有c个非零位置,该做法的时间复杂度为O(n(n+e) 例题 例题1. Gapless Filling with Tetrominoes4 有一个n行4列的网格,你需要用π个俄罗斯方块(即大小为四的格子联通块)来覆 盖它,毎个格子必须被覆盖恰好一次。输岀方案数对输入的质效p取模的值。1≤n≤10°, 2≤p≤109+9。 考虑状态压缩动态规划,记fS]表小当前考虑了前t行,最后三行的格子中当前没 被覆盖的集合为S,转移时可以枚举最下方的格子在行t中的俄罗斯方块集合,fm]的 值即为所求的答案。 由于第二维的状态数较多,官方题解的做法是找出所有可达的状态并使用矩阵乘法转 移。类似节1.4-3,由定理L2我们有{fl。为线性递推数列,我们使用节1.3.1中的算法 求出它的最短线性递推式并使用节1.3.2中的算法转移即可,这个做法明显不劣于官方题解 的做法(如果官方题解的做法将第二维大小压缩为了k,那么我们就得到∫一个O(k)阶线 性递推式)。实际测试中求出了一个34阶递推式。 2设NA)为A的零空间,首先江意到N(A)sN(AD1A),然后取N(AD1A)的一组基并利用 Schwartz- Zippel引理可 证明其有高概率在N(A)内,所以就有N(AD1A)=N(A) 3证玥可参凡7定理47 4来源: Bytedance Camp2019Day3 Division a, roblem G,有改动 两关递推数列的性质和应用 福州第中学钟了谦 例题2. F. rpected valei 有一张简单无向连通平面图,有一枚棋子开始在1号点,每步祺子会从与当前点相连 的边中等概率选择一条移到岀边指向的点,求棋孑到达〃号点的期望步数,对输入的质数 卩取模输出。1≤n≤2000,103<p<1.01×109。 由欧拉定理的推论,我们有该图的边数m不超过3n-6。8 我们记f为从x点出发到达n点的期望步数,dx为点x的度数,那么我们就有 +∑()Ea(x≠n) fx 其屮E为图的边集。注意到这个方程组对应的系数矩阵只有O(n+m)个位置非零,我们 套用节1.44中的做法即可,复杂度O(n2) 另外本短也有一个不同的做法,可以参见参考文献9。 2整式递推数列6 21定义 我们同定义1.1样定义有限数列、无限数列、形式幂级数的次数和生成函数。设运算 在域K上进行。 定义2.1.对于无限数列{a0,a1,a2…}和有限非空多项式数列(Po,P1,P2…Pn1},若 P非零且对于任意p≥m-1,有∑=an=kP(p)=0,则称数列P为数列a的整式递推 式。我们称存在整式递推式的无限数列为整式递推数列。 对于有限数列{,a1,(2…an-1}和有限非空多项式数列{Po,P1,P2…Pm-},若Po非 零且对于任意m-1≤p≤n-1,有∑=an=PA(p)=0,则称数列P为数列a的整式递推 式 我们称整式递推式{ro,n1,r2…rmn)的阶数为m-1,次数为 max-a deg(r) 定义22.我们称一个形式幂级数A(x)为微分有限的当且仅当存在多项式数列 Q(x),Q1(x)…Qn-1(x),满足Qm-1≠0且∑bQ(x)A(x)=0(其中A0(x)为A(x)关 于x的i阶导数)。我们称一个形式幂级数A(x)为代数形式幂级数当且仅当它在K(x)8上 是代数的(即A(x)为系数在K(x)内的多项式方程的根)。 5来源: ndar gaiuullin cortes1, Probe f,有筒化 oP-recursive sequences 7D-finite 8K二的有理分式域 8

...展开详情
试读 127P 国家集训队2019论文集.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
国家集训队2019论文集.pdf 45积分/C币 立即下载
1/127
国家集训队2019论文集.pdf第1页
国家集训队2019论文集.pdf第2页
国家集训队2019论文集.pdf第3页
国家集训队2019论文集.pdf第4页
国家集训队2019论文集.pdf第5页
国家集训队2019论文集.pdf第6页
国家集训队2019论文集.pdf第7页
国家集训队2019论文集.pdf第8页
国家集训队2019论文集.pdf第9页
国家集训队2019论文集.pdf第10页
国家集训队2019论文集.pdf第11页
国家集训队2019论文集.pdf第12页
国家集训队2019论文集.pdf第13页
国家集训队2019论文集.pdf第14页
国家集训队2019论文集.pdf第15页
国家集训队2019论文集.pdf第16页
国家集训队2019论文集.pdf第17页
国家集训队2019论文集.pdf第18页
国家集训队2019论文集.pdf第19页
国家集训队2019论文集.pdf第20页

试读结束, 可继续阅读

45积分/C币 立即下载 >