文章目录 一、前言 二、问题引入 1、递推公式 2、通项公式 三、卢卡斯定理 1、定义 2、证明 1)引理1 2)引理2 3)卢卡斯定理 四、卢卡斯定理相关题集整理 一、前言 有人问我,你这些东西应该是你当时做 ACM 竞赛时候的东西了,现在都毕业十年了,为什么还在搞这些啊?公众号很赚钱吗? 我想说的是,《夜深人静写算法》这个公众号(暂时)不是为了赚钱。要不是因为情怀,我可能早就弃坑公众号了。 有时候,既然开始了,就一直做下去吧,不然当时为什么要开始呢?就像既然谈恋爱了,就一直爱下去吧,毕竟曾经爱过。既然无法逃离沉没成本的枷锁,就当记录自己逝去的青春吧。 这周要更新的内容,还是目前工作中对我来说,毫无用处的东西,纯粹是为了刷题爽,一直刷题一直爽的 卢卡斯定理。 二、问题引入 【例题1】给定