schtonn

前置知识

矩阵快速幂，聪明的头脑。

引入

这篇文章旨在记录丰富的矩阵快速幂应用。

前置知识

取模

引入

对于 \(p\in\mathbb{P},a\in\mathbb{N}^+\) 且 \((a,p)=1\)，也就是 \(p\) 为素数且正整数 \(a\) 与 \(p\) 互质，有： \[a^{p-1}\equiv1\pmod p\]

前置知识

KMP，trie

引入

往简单了说，AC自动机其实就是在字典树上搞KMP思想。它能够快速实现在一个文本串中匹配多个模式串。

前置知识

字符串，图论基础

引入

trie-字典树，就是一棵可以拿来当字典用的树，它的思考和实现都非常简单。例如，hello，her，hers，his 生成的字典树如下：

前置知识

复数域的运算，基础运算记号。

引入

FFT-快速傅里叶变换是一种能够快速实现 DFT 和 IDFT 的算法，常用于快速求多项式相乘。

前置知识

矩阵快速幂。这是一点比较复杂的应用。

前置知识

矩阵快速幂，扩展欧几里得求逆元，基本的找规律能力。

题面

(luogu P2020)

。。。我最近写数学越来越多了，人都麻了

前置知识

好像没啥，看得懂公式就行了。

引入

一般的生成函数会和某个数列 \(a_0,a_1,\dots,a_n\) 建立关系，它是一个多项式函数，其中每一项的系数等于对应数列每一位的值，这样的函数有时候也叫形式幂级数。

前置知识

同余，逆元等数论基础。

引入

我们来看这样一个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？——《孙子算经》

即： \[ \left\{ \begin{aligned} x&\equiv 2\pmod {3}\\ x&\equiv 3\pmod {5}\\ x&\equiv 2\pmod {7} \end{aligned} \right.\tag{1.0} \]

前置知识

中国剩余定理，

引入

从 \(n\) 个不同元素中取出 \(m\) 个元素的组合数，即 \(C_n^m\)，是从 \(n\) 个不同元素中，取出 \(m\) 个元素所形成的组合个数。

我们需要使用各种方式求 \(C_n^m\)，每个方式难度，速度和空间都有不同。