96、OI（信奥）中的数论-2020.06.09.rar

CSP-J CSP-S NOI初赛（2022.08.02）C.pdf

CSP2020入门组初赛试题解析（单项选择题）

信奥中的数学 数论 第3讲 质数与合数（二）-2022.06.30（有作业）.pdf

CCF中学生计算机程序设计提高篇（完整版） 第1章树及其应用 1.1 树的相关概念及其性质..... 1.2 树的存储及遍历法.... 1.3 最近公共祖先(LCA) 1.4 树的简单应用 1.6 树的应用实例 本章小结 第2章二叉树及其应用 2.1 二叉树的概念及其性质. 2.2 二叉树的存储方法 2.3 二叉树的遍历 2.4 树、森林与二叉树的转化. 2.5 哈夫曼树及其应用 2.6 二叉堆及其应用 2.7 二叉排序树及其应用.. 本章小结 第3章集合与并查集 3.1 集合与并查集...... 3.2 并查集的基本操作 3.3并查集的应用 本章小结 第4章图及其应用 4.1 图的基本概念 4.2 图的存储方法 4.3 图的遍历 4.4 图的连性问题 4.5 无向图的生成树 4.6 最短路径 4.7 有向图的基本应用....... 本章小结 第5章二分图及其应用 5.1 二分图的判定 5.2 二分图的匹配 5.3 二分图的最大匹配 5.4 二分图的最佳匹配....... 5.5 二分图的应用 本章小结 …………

CSP-J CSP-S NOI初赛（2022.06.13）B.pdf

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,