诺诺的魔法日记

“算法与数据结构”

放我写的一些关于算法和数据结构的内容。

[P4942] 小凯的数字 题解

题目描述小凯有一天突发奇想,写下了一串数字:l(l+1)(l+2)...(r-1)r例如:l=2, r=5时,数字为:2345l=8, r=12时数字为:89101112小凯很喜欢数字9,所以他...

并查集(Disjoint-Set)

前言去写了并查集的题,就来写了。正文简单描述一下并查集是干嘛的吧,我们可以把它想象成家族。刚刚开始的时候,每个人各成帮派,后面有一些帮派结盟,互相合并,当然一个人只可能在一个帮派里,盟主可不允许...

卢卡斯定理 (Lucas' Theorem)

前言最近刷模板题,然后刷到了卢卡斯定理,AK了就来写了。阅读本文你需要的知识组合计数,MOD运算正文卢卡斯定理用于求解大组合数取模的问题,正常的组合数通过递推或者公式计算出,但大组合数会很慢。但...

乘法逆元 (Multiplicative Inverse Modulo)

前言在算法题里,为了避免高精运算带来的种种不方便(高精实现不同影响效率,难对算法本身进行准确评估),所以经常需要对答案进行取模,我们都知道(a × b) mod c = ((a mo...

矩阵快速幂 (Matrix Square Exponentiation)

前言这个算法是很久很久之前我学习的,最近在Luogu看到了一题矩阵加速递推的斐波那契数列居然是绿题...正文我们需要先了解一下矩阵是一个什么东西。矩阵在数学中,矩阵(Matrix)是一个按照长方...

快速幂 (Exponentiation By Squaring)

前言这个算法是很久很久之前我学习的,最近在Luogu看到了一题矩阵加速递推的斐波那契数列居然是绿题...正文我们都知道,一个数可以变成数个2的n次方之和,a=b+c,d^a = d^b &tim...