k 短路

好像是一个比较简单的东西

对于 正权有向图，\(\displaystyle G=(V,E),V=\{V_i\}_{i=1}^nE=\{(u_i,v_i,w_i)\}_{i=1}^m\)，求 \(s\) 到 \(t\) 的前 \(k\) 短路。

考虑建立反图 \(G'=(V,E')\)，容易 \(\text{Dijkstra}\) 求得 \(t\) 的单源最短路 \(dis_i\)，并且建立一棵最短路树。

无向图的 三元环 - 四元环 计数

问题描述：

给定一个 \(n\) 个点 \(m\) 条边的无向图，统计其中三元环 / 四元环的个数。

下降幂多项式的运算

下降幂的定义

下降幂 \(\text{Falling Factorial}\)。

下降幂多项式 \(\text{Falling Factorial Polynomial}\) 下面简称 \(\text{FFP}\)。

\(x\) 的 \(n\) 阶下降幂 \(x^{\underline n}=\prod_0^{n-1}(x-i) = \frac{x!}{(x-n)!}\)。

一个下降幂多项式 \(F(x)=\sum a_ix^{\underline i}\)。

二次剩余 (Quadratic Residue)

只考虑奇质数 \(P\) 的情况

设求 \(x^2\equiv a\pmod P\) 的一个 \(x\)。

判断

由费马小定理 \(x^{P-1}\equiv 1 \pmod P\)，即 \(a^\frac{P-1}{2}\equiv 1 \pmod P\)。

不存在二次剩余即 \(a^\frac{P-1}{2}\equiv -1\pmod P\)。

(对于所有 \(a=0,1\) 的情况需要特判)。

拟阵

大量基础定义警告，参考了 wiki 和2018论文《浅谈拟阵的一些拓展及其应用》，如果想看大段详细证明请移步论文。

拟阵的概念比较抽象，有多种定义方法，结合这些定义方法可以更具体地了解拟阵的基础性质。

前言

很多问题可以转化为拟阵，但是并不是所有问题都可以通过简单的拟阵操作得到答案。

在具体问题中，很多时候有着更优的算法解决拟阵运算无法解决的操作。

但是对于一个奇怪的问题，如果转化为类似拟阵的操作后，就有很多性质可以拿过来套。在 OI 中，应用于拟阵的常见算法与二分图上的一些算法相当相似。

拟阵的应用，更多还是用 诸多的性质 把复杂,抽象问题向更简单的方向转化(便于乱搞)。

也可以便于简化问题的证明，所以这个东西了解一下也差不多了。

(不会有人丧心病狂到专门出一个拟阵交的题吧)。

关于物品大小较小的01背包

设题目给出的物品大小为 \(w_i\)，个数为 \(n\) ,总和为 \(N\)。

前言

这个东西可能纯粹是乱搞。

发现 WC2020 选课这个题直接被一个错误的写法爆水。

ps: 这个题是大小范围 1~3 ，实际上正解复杂度很高。

关于生成函数

基础

普通生成函数

对于数列 \(a_i\) ，它的普通生成函数( \(\text{OGF}\) )为 \(A(x)=\sum a_ix^i\)。

这个 \(x^i\) 刚开始并没有实际意义，即为形式幂级数，实际这个 \(i\) 甚至可以不是一个整数，如 \(\text{FWT}\) 中的指数为集合幂指数。

普通生成函数常用于解决无序的组合计数问题，如背包问题。

单位根反演

最基础的用途是用于 FFT 中点值式转多项式。

即对于 \(G(i)=F(\omega_n^i)\) ，由 \(G(i)\) 反演得到 \([x^i]F(i)\) 的过程，称之为单位根反演。

式子非常简单：

\(\sum_{j=0}^{n-1}\omega_n^{ij}= \left\{\begin{aligned} \frac{\omega_n^{in}-1}{\omega_n^i-1}=0 && i\ne 0\\ n && i=0\end{aligned} \right.\)。

更简洁的式子为 \(\begin{aligned}\frac{\sum_{j=0}^{n-1}\omega_n^{ij}}{n}=[n|i]\end{aligned}\)。

反演

什么是反演

对于已知 \(F_i=\sum a_{i,j}\cdot G_j\)。

反演得到 \(G_i=\sum b_{i,j} \cdot F_j\)。

\(\text{NTT,FFT,FWT}\) 的逆卷积都是反演。

回文自动机 (PAM,Palindrome Automaton)

如果学习了\(\text{AC}\) 自动机和后缀自动机（\(\text{SAM}\)），那么这个冷门算法其实非常简单。

约定：原字符串为 \(S\)，长度为 \(|S|\)。