马尔可夫链 持续更新中。。。 1. 简介 1.1 定义 我们一般这样描述马尔可夫过程（也叫马尔可夫链）：假设有一系列状态集合 $S=\{s_1,s_2,\ldots,s_r\}$ ，马尔可夫过程（Markov process）是从这些状态中的某一个开始，从一种状态连续移动到另一种状态。每一次移动被称为一步（step）。如果当前位于状态 $s_i$ …

这一章节主要通过各种例题的形式幂级数解法，来演示第一章节中的解题思维（或者说将题目翻译成多项式语言？）如何转化为算法实现。 前置芝士 首先你需要知道的是一些常用的多项式化简方法和多项式基本操作。 二项式定理 $$(x+y)^n=\sum_{i=0}^n \binom{n}{i}x^iy^{n-i}$$ 等比数列求和 $$\sum_{i=0}^{n-…

问题引入 问题来源：CF348D Turtles。 一个有障碍物的 $N\times M$ 网格图上，两只乌龟分别从 $(0,0)$ 点爬到 $(N-1,M-1)$ 点，询问路径不相交的方案数。 $N,M\leq 3000$ 。 首先问题可以转化为：两个人分别从 $A_0(0,1)$ 和 $B_0(1,0)$ 点出发，分别走到 $A_1(N-2,M…

多项式基本操作 多项式加法、减法 有手就行。 多项式乘法 一句话概括，就是FFT。 这是整个多项式章节中最基础的一部分：如何用FFT将两个 $n$ 度的多项式乘法优化到 $O(n\log n)$ 的时间复杂度。 洛谷模板题：P3803 【模板】多项式乘法（FFT），P4245 【模板】任意模数多项式乘法 。 在多项式乘法中，有两个核心问题，加法卷积…

本文主要讨论形式幂级数在解决数学问题以及算法竞赛问题的思维，因此并不会涉及形式幂级数运算的编程实现。 例题引入 [admonition title="问题1" color="indigo"]有 $3$ 个集合 $A=\{2,3\}, B=\{2,4\},C=\{3,5,7\}$ ，现在要求从三个集合中各选择恰好一个元素 $a,b,c$ 使得 $a+…

压位BFS 一个 $n$ 个点，$m$ 条边的有向图，当所有边权均为 $1$ 时，求任意两点之间的最短路。 $n\leq 1000,m\leq \frac{n(n-1)}{2}$ 。 多源最短路是一个经典问题，显然可以通过floyd算法在 $O(n^3)$ 的复杂度下求解。同时，考虑到本题中一个特殊的条件：所有边权均为 $1$ ，本题也可以通过01…

小球盒子模型总结 题目链接：洛谷十二重计数法。 设有 $n$ 个球，$k$ 个盒子： 球之间互不相同，盒子之间互不相同，可以空盒 根据乘法原理，答案就是 $k^n$ 。 球之间互不相同，盒子之间互不相同，每个盒子至多装一个球 相当于每个球找一个没有被选过的盒子放进去，答案是 $k^{\underline{n}}$ ，即 $k(k-1)\cdots(…

FFT解决字符串匹配问题 朴素的字符串匹配 设有两个字符串 $a,b$ 长度分别为 $n,m(n\geq m)$ ，询问字符串 $b$ 在 $a$ 中出现了几次。 这是一个最基础的字符串匹配问题，显然我们容易想到 $O(nm)$ 的暴力匹配方法，同时也可以使用 $KMP$ 算法在 $O(n+m)$ 的复杂度下解决该问题。实际上，我们还可以利用 $F…