ACM 中的数学模版

前言

不知道怎么就成为数学手了（大概

​

Trick

切比雪夫转曼哈顿

对平面两点 $(x_1,y_1),(x_2,y_2)$

曼哈顿距离：$\left|x_1-x_2\right|+\left|y_1-y_2\right|$

切比雪夫距离：$\max(\left|x_1-x_2\right|,\left|y_1-y_2\right|)$

将 $(x,y)$ 映射到 $(x+y,x-y)$ ，可以将曼哈顿距离映射到切比雪夫距离

将 $(x,y)$ 映射到 $(\frac{x+y}{2},\frac{x-y}{2})$，可以将切比雪夫距离映射到曼哈顿距离

已经证明不可推广至高维

---

组合数学

多重集的排列数（多重组合数）

设 $S=\{n_1\cdot a_1,n_2 \cdot a_2,\dots,n_k\cdot a_k\}$ 表示 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$ ，$\dots$，$n_k$ 个 $a_k$ 构成的多重集，则 $S$ 的全排列个数为

$\frac{n!}{\prod_{i=1}^k n_i!}$

定义多重组合数：

$\binom{n}{n_1,n_2,\dots,n_k}=\binom{n}{n_1}\binom{n-n_1}{n_2}\dots\binom{n_k}{n_k}=\frac{n!}{\prod_{i=1}^kn!}$

多重集的组合数

设 $S=\{n_1\cdot a_1,n_2 \cdot a_2,\dots,n_k\cdot a_k\}$ 表示 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$ ，$\dots$，$n_k$ 个 $a_k$ 构成的多重集，定义从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数为多重集的组合数。

若 $r\le \min\limits_i n_i$，方案数为

$\binom{n+k-1}{k-1}$

等价于 $x_i=r$ 的非负整数解个数，多重集 $\{r\cdot 0,(k-1)\cdot 1\}$ 的排列数等

若 $r> \min\limits_i n_i$

设 $S_i$ 表示（至少）满足 $x_i\le n_i$ 的方案集合（ $x_i$ 表示从选择了 $x_i$ 个 $a_i$ ），$U$ 为不存在限制的全集，则

$\left|\bigcap_{i=1}^kS_i\right|=\left|U\right|-\left|\bigcup_{i=1}^k\overline{S_i}\right|$

由容斥

$\left|\bigcup_{i=1}^k\overline{S_i}\right|=\sum_i \left|\overline{S_i}\right|-\sum_{i<j}\left|\overline{S_i}\cap\overline{S_j}\right|+\sum_{i<j<l}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_l}\right|+\dots+(-1)^{(k+1)}\left|\bigcap_{i=1}^kS_i\right|$

$\overline{S}$ 的交是简单的，所以考虑这样容斥，我们可以钦定在集合中已经选择 $x+1$ 个 $a$，则

$\left|\bigcup_{i=1}^k\overline{S_i}\right|=\sum_{i=1}^k\binom{k+r-n_i-2}{k-1}-\sum_{i<j}\binom{k+r-n_i-n_j-3}{k-1}+\dots+(-1)^{k+1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1}$

则原式有

$\left|\bigcap_{i=1}^n S_i\right|=\sum_{P}(-1)^{|P|}\binom{k+r-\sum_{i=1}^{|P|}n_{p_i}-|P|-1}{k-1}$

$P$ 为从整数 $1$ 到 $k$ 中任取若干项组成的递增数列

生成函数练习 1

留坑

错排问题

设 $f_n$ 表示大小为 $n$ 的满足 $p_i\not=i$ 的排列 $P$ 的个数，那么有

$f_n=(n-1)(f_{n-1}+f_{n-2}),f_1=0,f_2=1$

$(n-1)f_{n-1}$ 表示位置 $n$ 与前面 $n-1$ 长的错排中任意一个已经存在的位置交换

$(n-1)f_{n-2}$ 表示位置 $n$ 与钦定的某个满足 $p_x=x$ 的位置 $x$ (共 $n-1$ 种) 交换

可以证明，存在且仅存在此两种单次交换可以构造大小为 $n$ 的错排

容斥练习 1

设排列的全集为 $U$，（至少）满足 $p_i\not=i$ 的排列集合为 $S_i$，则我们需要求解 $\left|\bigcap S_i\right|$，又

$\left|\bigcap S_i\right|=|U|-\left|\bigcup\overline{S_i}\right|$

则转化为求 $\left|\bigcup \overline{S_i}\right|$

我们发现，利用容斥展开后，实际上要求 $\left|\bigcap\limits^k \overline{S_{a_i}}\right|$，而此式子的值仅跟参与交的集合的个数有关，与集合的选择无关（值得一题的是，这点在容斥中很重要），在这个具体问题中值为 $(n-k)!$，那么有

$\left|\bigcup\overline{S_i}\right|=\sum_{k=1}^n \binom{n}{k}(-1)^{k-1}(n-k)!$

则

$\begin{aligned} \left|\bigcap S_i\right|&=\sum_{k=0}^n\binom{n}{k}(-1)^k(n-k)!\\ &=n!\sum_{k=0}\frac{(-1)^k}{k!} \end{aligned}$

组合恒等式

二项式定理及其推论

当 $n$ 为非负整数时

$\left(\sum_{i=1}^tx_i\right)^n=\sum_{(\sum\limits_{i=1}^tn_i)=n,n_i>0}\binom{n}{n_1,n_2,\dots,n_t}\prod_{j=1}^tx_j^{n_j}$

取 $t=2$ ，得到一般式

$(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}$

取 $a=b=1$ ，有

$2^k=\sum_{k=0}^n\binom{n}{k}$

取 $a=1,b=-1$，有

$\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]$

即奇项和与偶项和相等

扩展：当 $n$ 为实数且 $k$ 为非负整数时，定义

$\binom{n}{k}=\frac{r^{\underline{k}}}{k!}$

多项式求导

$\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\\ \sum_{i=0}^n i^2\binom{n}{i}=n(n+1)2^{n-2}$

斯特林数练习 1

$\sum_{i=0}^n\binom{n}{i}i^k=\sum_{j=1}^k{k \brace j}n^{\underline j}2^{n-j}$

留坑，此题为 CF 932 E

范德蒙德卷积

$\sum_{i}\binom{n}{i}\binom{m}{m-i}=\binom{m+n}{m}$

暂时先从组合意义理解，注意边界

取 $n=m$，有

$\sum_{i}\binom{n}{i}^2=\binom{2n}{n}$

三项式恒等式

$\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}$

平行求和法

$\sum_{0\le k\le n}\binom{r+k}{k}=\binom{r+n+1}{n}$

对杨辉三角手玩一下

上指标求和

$\sum_{0\le k\le n}\binom{k}{m}=\binom{n+1}{m+1}$

对杨辉三角手玩一下

卡特兰数

0	1	2	3	4	5	6
1	1	2	5	14	42	132

关于卡特兰数的问题有两种不同的形式。

路线问题

使用这个问题构造双射比栈序列更容易理解

考虑一个网格图，你处于 $(0,0)$ 每次可以选择右走一格或者上走一格，且在任意的时刻，你往上走的次数不得超过往右走的次数，求走到 $(n,n),\ n>0$ 的方案数。

考虑每个不合法的走路序列，其一定与直线 $y=x+1$ 有交点，假设某序列与直线 $y=x+1$ 的第一个交点为 P，那么将此直线在 $P$ 后的序列关于 $y=x+1$ 翻转，翻转后的序列结尾变为 $(n-1,n+1)$，可以证明，从 $(0,0)$ 走到 $(n-1,n+1)$ 的序列与上述的不合法序列构成双射，于是我们有方案数

$Cat_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{\binom{2n}{n}}{n+1}$

定义 $Cat_n$ 为卡特兰数

与路线问题本质相同的问题有

• 合法括号序列

• 进出栈

• 不相交弦

  圆周上有 $2n$ 个互不相等的点，将它们两两连边，求弦互不相交的方案数。

  任取某一个点和一个方向（顺时针或逆时针），然后按方向扫描点，将某条弦第一次在此方向出现的端点作为左括号 ‘(’，第二次出现的端点作为右括号 ‘)’ ，可以发现所有不相交连边方案与合法括号序列构成双射。

二叉树问题

问 $n$ 个点无标号二叉树个数，考虑 dp，设 $dp_n$（$dp_0=1$） 表示答案，枚举跟节点和左右节点个数，则有

$dp_n=\sum_{i=0}^{n-1}dp_i\times dp_{n-i-1}$

它的同构问题均可以使用 dp 解决

可以证明，$dp_n$ 即为 $Cat_n$

生成函数练习 2

证明一哈

斯特林数

第二类斯特林数

定义 ${n\brace k} (S(n,k))$ 表示 $n$ 个（不同的）元素，分给 $k$ 个（相同的）非空集合的方案数，我们有如下递推（分情况讨论即可）

$\begin{aligned} &{n \brace k}={n-1 \brace k-1}+k{n-1 \brace k-1}\\ &{n \brace 0}=[n=0] \end{aligned}.$

通项

$\begin{aligned} {n\brace k}&=\sum_{i=1}^k\frac{(-1)^{k-i}i^n}{i!(m-i)!}\\ &=\frac{1}{m!}\sum_{i=1}^k(-1)^{k-i}i^n\binom{m}{i} \end{aligned}$

容斥练习2

留空为上式证明

生成函数练习3

留坑

第一类斯特林数

定义 $\begin{bmatrix}n\\k\end{bmatrix}(s(n,k))$ 表示 $n$ 个（不同的）元素，分给 $k$ 个（相同的）非空轮换的方案数，我们有如下递推（分情况讨论即可）

$\begin{aligned} &\begin{bmatrix}n\\k \end{bmatrix}=\begin{bmatrix}n-1\\k-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k \end{bmatrix}\\ &\begin{bmatrix}n\\0 \end{bmatrix}=[n=0] \end{aligned}$

• 轮换：首位相接的环形排列，具有旋转等价性

• 同大小排列与轮换构成双射

  排列与置换构成双射，置换可以分解为若干非空轮换

  $\sum_k\begin{bmatrix}n\\k\end{bmatrix}=n!$

幂与恒等式

$\begin{aligned} &x^{\overline n}=\sum_k\begin{bmatrix}n\\k\end{bmatrix}x^k\\ &x^n=\sum_k{n\brace k}x^{\underline k}\\ \end{aligned}$

上式均可采用归纳进行证明，可以对幂构造逆变换，首先我们有

$x^{\underline n}=(-1)^n(-x)^{\overline n}$

将其带入上述公式，可以得到

$\begin{aligned} &x^{\underline n}=\sum_k\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^k\\ &x^n=\sum_k{n\brace k}(-1)^{n-k}x^{\overline k} \end{aligned}$

尝试将原公式带入新产生的公式

$\begin{aligned} x^n&=\sum_k{n\brace k}(-1)^{n-k}x^{\overline k}\\ &=\sum_k{n\brace k}(-1)^{n-k}\sum_m\begin{bmatrix}k\\m\end{bmatrix}x^m\\ &=\sum_m(\sum_k\begin{bmatrix}k\\m\end{bmatrix}{n\brace k}(-1)^{n-k})x^m \end{aligned}$

由于左右两边 $x$ 的系数需要相同，则有

$\sum_k\begin{bmatrix}k\\m\end{bmatrix}{n\brace k}(-1)^{n-k}=[n=m]$

同理可以得到

$\sum_k{k\brace m}\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}=[n=m]$

称最后两个公式为反演系数

行与列

• 第二类斯特林数行

  直接对通项卷积即可

• 第二类斯特林数列

  留作生成函数练习4

• 第一类斯特林数行

  利用倍增求 $x^{\overline n}$ 的多项式表达，留作练习

• 第一类斯特林数列

  留作生成函数练习5

斯特林反演

之后在反演大类里面应该会具体介绍，此处先简要说明

$f(n)=\sum_k{n\brace k}g(k)\Longleftrightarrow g(n)=\sum_{k}\begin{bmatrix}n\\k \end{bmatrix}(-1)^{n-k}f(k)\\ f(n)=\sum_k\begin{bmatrix}n\\k \end{bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k}{n\brace k}(-1)^{n-k}f(k)$

以一式左推右为例（其余同理）

$\begin{aligned} g(n)&=\sum_{i}g(i)[i=n]\\ &=\sum_ig(i)\sum_k\begin{bmatrix}n\\k\end{bmatrix}{k\brace i}(-1)^{n-k}\\ &=\sum_k(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}\sum_i{k\brace i}g(i)\\ &=\sum_k(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k) \end{aligned}$

贝尔数

0	1	2	3	4	5	6
1	1	2	5	15	52	203

称基数为 $n$ 的集合的划分方案的数目，记为 $B_n$

$B_{n+1}=\sum_k\binom{n}{k}B_k$

这就是枚举新元素加入某个集合的 dp

由组合意义，我们有

$B_n=\sum_k{n\brace k}$

生成函数练习6

比较有趣，留坑

伯努利数

先给出一些简单定义，后续在复习生成函数之后进行补充

0	1	2	3	4	5
$1$	$-\frac{1}{2}$	$\frac{1}{6}$	$0$	$-\frac{1}{30}$	$0$

定义 $S_m(n)=\sum\limits_{k=0}^{n-1}k^m$，将其写成关于 $n$ 的多项式后，定义其系数为伯努利数，具体的，有

$\begin{aligned} S_m(n)&=\frac{1}{m+1}(B_0n^{m+1}+\binom{m+1}{1}B_1n^m+\binom{m+1}{2}B_2n^{m-1}+\dots+\binom{m+1}{m}B_mn)\\ &=\frac{1}{m+1}\sum_{k=0}^m\binom{m+1}{k}B_kn^{m+1-k} \end{aligned}$

由

$S_m(1)=[m=0]$

则

$\sum_{k=0}^m\binom{m+1}{k}B_k=[m=0]$

此式可以朴素求或构造生成函数

生成函数练习7

晚点

欧拉数

这，先留个坑吧

容斥

设全集 $U$ 中的元素可能有 $n$ 种不同的属性，其中（至少）拥有第 $i$ 种属性的元素构成集合 $S_i$，我们有

$\left|\bigcup_{i=1}^nS_i\right|=\sum_i|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\dots+(-1)^{m-1}\sum_{a_i<a_{i+1}}|S_{a_1}\cap S_{a_2}\cap\dots\cap S_{a_m}|+\dots+(-1)^{n-1}|S_1\cap S_2\cap \dots\cap S_n|$

这个式子有一个广为人知的证明，即讨论每个元素被统计的次数，发现系数可以利用帕斯卡三角形同行奇偶项相等约到只剩系数 $1$

当具体问题为交集时，采用如下转化

$\left|\bigcap S_i\right|=|U|-\left|\bigcap\overline{S_i}\right|$

一般化(子集反演)

设存在两个集合的函数 $f(S),g(S)$，若有

$f(S)=\sum_{T\subseteq S}g(T)$

那么有

$g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)$

证明思路和普通的容斥原理相似，强行拆开后交换次序构造出奇偶项相等即可

其存在一个推论，在全集 $U$ 下，若有

$f(S)=\sum_{S\subseteq T}g(T)$

那么有

$g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f(T)$

例题

求 $n$ 个点有标号 DAG 的个数，$n\le5000$ （此题有若干加强版，这里仅讨论运用子集反演的简单版，后续可能会在别的地方作为练习题补充）

在考虑 DAG 的连边情况时，入度或出度为 $0$ 的点是特殊的，我们考虑以入度为 $0$ 的点为基础进行统计，令 $dp_{i,j}$ 表示 $i$ 个点的 DAG，入度为 $0$ 的点恰好为 $j$ 个的个数，我们有

$dp_{i,j}={i\choose j}\sum_{k=1}^{i-j}(2^j-1)^k2^{(i-j-k)j}f_{i-j,k}$

首先因为有标号，所以先钦定 $j$ 个点，然后枚举去掉这 $j$ 个点后的图中有多少个度为 $0$ 的点（$k$），这 $k$ 个点的每个点与 $j$ 个点的点集至少连一条有向边，然后 $j$ 个点的点集同时与剩下的 $i-j-k$ 个点任意连边。

考虑对入度为 $0$ 这个条件进行容斥，设 $f(i,S)$ 表示 $i$ 个点的 DAG 中恰好集合 $S$ 的度数为 $0$，$g(i,S)$ 表示 $i$ 个点的 DAG 中至少集合 $S$ 的度数为 $0$，我们有

$g(n,S)=\sum_{S\subseteq T}f(n,T)$

由子集反演，则

$f(n,S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(n,T)$

我们的目标是 $g(n,\varnothing)$ ，那么有（$U=\{1,2,\dots,n\}$）

$\begin{aligned} g(n,\varnothing)&=\sum_{\varnothing \not=T\subseteq U}f(n,T)\\ &=\sum_{\varnothing \not=T\subseteq U}\sum_{T\subseteq P}(-1)^{|P|-|T|}g(n,P)\\ &=\sum_{\varnothing \not=T\subseteq U}\sum_{T\subseteq P}(-1)^{|P|-|T|}g(n-|P|,\varnothing)2^{|P|(n-|P|)}\\ &=\sum_{\varnothing\not=P\subseteq U}g(n-|P|,\varnothing)2^{|P|(n-|P|)}\sum_{\varnothing\not=T\subseteq P}(-1)^{P-T}\\ &=\sum_{k=1}^n\binom{n}{k}g(n-k,\varnothing)2^{k(n-k)}\sum_{i=1}^k\binom{k}{i}(-1)^{k-i}\\ &=\sum_{k=1}^n\binom{n}{k}g(n-k,\varnothing)2^{k(n-k)}([k=0]-(-1)^k)\\ &=\sum_{k=1}^n\binom{n}{k}g(n-k,\varnothing)2^{k(n-k)}(-1)^{k-1} \end{aligned}$

令 $dp=g(\varnothing)$ 即可朴素求出，为

$dp_n=\sum_{i=1}^n(-1)^{i-1}dp_{n-i}\binom{n}{i}2^{i(n-i)}$

上述推导过程相对麻烦，不妨感性认识一下这个转移式的容斥意义，我们枚举的 $i$ 即为钦定了度数为 $0$ 的点，那么上式意义为 DAG 个数=至少一个点入度大于 $0$ 的 DAG 个数 减去 至少两个点的入度大于 $0$ 的 DAG 个数 加上 至少三个点的入度大于 $0$ 的 DAG 个数 …

min-max容斥

• 前置知识

  二项式反演

  $f(n)=\sum_{i=0}^n\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)$

• 一些定义

  $\max (S),\min (S)$表示分别集合$S$的最大，最小元素

• 套路式子

  $\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)$

• 证明

  首先我们先设一个容斥系数$f(x)$

  $\max(S)=\sum_{\varnothing\not=S\subseteq T}f(|T|)\min(T)$

  设集合$S$有$n$个元素，我们讨论第$k$小元素的贡献

  $\sum_{i=0}^{n-k}\binom{n-k}{i}f(i+1)=[n-k=0]$

  就是当这个元素成为最小值时另外再选几个比它要大的元素的方案，如果这个元素不是最大元素，要求不贡献

  设

  $F(n)=f(n+1),G(n)=[n=0]$

  上式为

  $G(n)=\sum_{i=0}^n\binom{n}{i}F(i)$

  由二项式反演

  $F(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}G(i)$

  代回去

  $\begin{aligned} f(n+1)&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}[i=0]\\ &=(-1)^n\\ f(n)&=(-1)^{n-1} \end{aligned}$

  所以有

  $\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)$

• 用处

  在期望意义下，这个式子依然成立，即

  $E(\max(S))=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}E(\min(T))$

  下面给几个例题

• 例题

  • HDU4336

    题意：有$n$个卡牌，每秒有$p_i$的概率抽到卡牌$i$，求至少得到每个卡牌至少一张的期望时间

    min-max容斥有个套路思想就是化max为min，因为min一般比较好统计

    令$\max (S)$表示集合$S$中最后一个获得元素的期望时间，$\min (S)$代表集合$S$中第一个获得元素的期望时间

    那么有上面的套路式子

    $\max(S)=\sum_{\varnothing\not=S\subseteq T}(-1)^{|T|-1}\min(T)$

    $\min (T)$就非常好求了

    $\min(T)=\frac{1}{\sum_{i\in T}p_i}$

    就是先把总概率算一下的事情

  • 「HAOI2015」按位或

    题意：初始有一个数$0$，每秒有$p_i$的概率或(|)上整数$i(i\in [0,2^n))$，求期望多少秒后数组变成$2^n-1$

    令$\max(S)$表示最后一个或上去的期望时间，$\min(S)$同理

    式子随便套，考虑求出$\min(T)$

    $\min(T)=\frac{1}{\sum\limits_{S\cap T\not=\varnothing}p_S}$

    考虑求底下的东西

    $\begin{aligned} \sum_{S\cap T\not=\varnothing}p_S&=\sum_{S\subseteq U} p_S-\sum_{S\cap T=\varnothing}p_S\\ &=\sum_{S\subseteq U}p_S-\sum_{\overline S\cup T=\overline S}p_S \end{aligned}$

    后面的东西取补集后是子集和的形式，我们可以$FWT$或者$FMT$在$2^nn$内求出

  • 「PKUWC2018」随机游走

    题意：树上随机游走，给定起点，每次询问至少走过一次点集的期望时间

    直接套路上去考虑如何求$\min (T)$，即第一次到达给定点集的期望步数

    令$dp_u$表示$u$走到给定点集$S$的期望步数，$d_u$为$u$点度数

    若$u\in S,dp_u=0$

    否则

    $\begin{aligned} dp_u&=\frac{dp_{fa}}{d_u}+\frac{\sum dp_v}{d_u}+1\\ &=A_udp_{fa}+B_u \end{aligned}$

    就先把环状的转移和其他的分开搞一下，那么

    $dp_u=\frac{dp_{fa}}{d_u}+\frac{\sum A_vdp_u+B_v}{d_u}+1$

    化简一下

    $(1-\frac{\sum A_v}{d_u})dp_u=\frac{dp_{fa}}{d_u}+\frac{\sum B_v}{d_u}+1$

    把左边除过去就可以了

    这样的话我们可以$n2^n\log 998244353$处理出每个集合的$\min(S)$了，仍然可以预处理子集和

• kthmax-min容斥

  $kthmax(S)=\sum_{\varnothing\not=T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)$

  $kthmax(S)$表示集合中第$k$大的元素

  证明起来和普通的差不多

  设一个容斥系数$f(n)$,统计$n$个元素中第$x$小的贡献

  $\sum_{i=0}^{n-x}\binom{n-i}{i}f(i+1)=[n-x+1=k]\\ \sum_{i=0}^n\binom{n}{i}f(i+1)=[n=k-1]\\ f(n+1)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}[i=k-1]\\ f(n)=(-1)^{n-k}\binom{n-1}{k-1}$

  • 例题

    重返现世

    题解

• 参考资料

  【Learning】min-max容斥以及推广kth min-max容斥

  min-max容斥

LGV 引理

一般用于求 DAG 上不相交路径的数量

• 相关定义：

  $p$ ​表示图上某一个路径，$P_{u,v}$​ 表示图上以 $u$​ 为起点以 $v$​ 为终点的路径集合

  $\omega(p)$​​​ 表示路径 $p$​​​ 上所有边权之积

  $e(u,v)=\sum_{p\in P_{u,v}}\omega(p)$​​

  定义超级起点集合 $A$​，超级终点集合 $B$​，且 $|A|=|B|=n$​，$\sigma(S)$​ 为一个 $1\sim n$​ 的排列，$\mathtt{sign}(\sigma(S))$​ 表示 $\sigma(S)$​ 逆序对的奇偶性，即 $(-1)^{\mathbf{inversion \ number \ in \ \sigma(S)}}$​​​

  一组( $n$ 条) $A\rightarrow B$ 的路径 $S$：$S_i$ 表示一条从 $A_i$ 到 $B_{\sigma(S)_i}$​​ 的路径

  一组( $n$ 条) $A\rightarrow B$ 的不相交路径 $S_0$：$S_i$ 表示一条从 $A_i$ 到 $B_{\sigma(S)_i}$ 的路径，其中路径两两没有交点

• 引理

  $\begin{aligned}M&=\begin{bmatrix} e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n) \end{bmatrix}\\ \det(M)&=\sum_{S:A\rightarrow B}\mathtt{sign}(\sigma(S))\prod_{i=1}^n\omega(S_i)\\ &=\sum_{S_0:A\rightarrow B}\mathtt{sign}(\sigma(S))\prod_{i=1}^n\omega(S_i) \end{aligned}$

  所有系数为正的相交序列和所有为负的相交序列可以按照第一个交点任意排列，构成的奇偶排列数量相等，构成双射

  而一般来说，只有正排列 $(1,2,\dots,n)$ 构成的路径能做到没有交点，因此一般最后 $\det(M)$​ 求的就是整排列对应的无交路径

• 例题

  二维网格图有 $n$​​ 个起点 $(0,a_1),(0,a_2),\dots,(0,a_n)$​​ 和 $n$​​ 个终点 $(1,0),(2,0),\dots,(n,0)$​​，每一步只能向右或向下走，询问有多少个从对应起点到对应终点不相交的路径组 $1\le n \le 5\times10^5,0\le a_i\le 10^6,a_i< a_{i+1},\bmod 998244353$​​​

  直接套用 LGV 引理即可，但是 $n$ 比较大，我们需要一些后续处理

  $\begin{aligned} \det(M)&=\begin{bmatrix} \binom{a_1+1}{1}&\binom{a_1+2}{2}&\cdots&\binom{a_1+n}{n}\\ \binom{a_2+1}{1}&\binom{a_2+2}{2}&\cdots&\binom{a_2+n}{n}\\ \vdots&\vdots&\ddots&\vdots\\ \binom{a_n+1}{1}&\binom{a_n+2}{2}&\cdots&\binom{a_n+n}{n}\\ \end{bmatrix}\\ &=\prod_{i=1}^n\frac{1}{i!}\begin{bmatrix} (a_1+1)^{\overline{1}}&(a_1+1)^{\overline{2}}&\cdots&(a_1+1)^{\overline{n}}\\ (a_2+1)^{\overline{1}}&(a_2+1)^{\overline{2}}&\cdots&(a_2+1)^{\overline{n}}\\ \vdots&\vdots&\ddots&\vdots\\ (a_n+1)^{\overline{1}}&(a_n+1)^{\overline{2}}&\cdots&(a_n+1)^{\overline{n}}\\ \end{bmatrix}\\ &=\prod_{i=1}^n\frac{a_i+1}{i!}\begin{bmatrix} 1&(a_1+1)^{1}&(a_1+1)^{2}&\cdots&(a_1+1)^{n}\\ 1&(a_2+1)^{1}&(a_2+1)^{2}&\cdots&(a_2+1)^{n}\\ \vdots&\vdots&\ddots&\vdots\\ 1&(a_n+1)^{1}&(a_n+1)^{2}&\cdots&(a_n+1)^{n}\\ \end{bmatrix}\\ &=\prod_{i=1}^n\frac{a_i+1}{i!}\prod_{1\le i<j\le n} (a_i-a_j) \end{aligned}$

  第一步把每一列的 $\frac{1}{i!}$ 提取出来，第二步注意到 $n$ 次上升幂可以看作 $n$ 次多项式，这样后面项数大的可以不断减前面项数小的，把上升幂转成普通幂，最后再每一行提取一个 $(a_i+1)$ ，第三步直接使用范德蒙行列式

  范德蒙德行列式：

  $\begin{bmatrix} 1&1&1&\cdots&1\\ x_1&x_2&x_3&\cdots&x_n\\ x_1^2&x_2^2&x_3^3&\cdots&x_n^2\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ x_1^n&x_2^n&x_3^n&\cdots&x_n^n \end{bmatrix}=\prod_{1\le i<j\le n}(x_i-x_j)$

  最后设 $f_{a_i}=1,g_{mx-a_i}=1$ 两个卷一下，取大于 $mx$ 的系数，可以得到某个权值的出现次数，注意到 $a_i$ 互不相同，因此次数不超过 998244353，不需要使用任意模数，直接 NTT 即可

---

数论

约定

• O(1) 快速乘

  1 2 3 4 5

  ll ksc(ll a,ll b,ll p) { ull c=(ull)a*b-(unsigned)((long double)a/p*b+0.5L)*p; return c<p?c:c+p; }

同余方程

裴蜀定理等

CRT及其扩展

BSGS

见邝斌板子

二次剩余

原根与高次剩余

筛法

万金油线筛

素数判定与整除

这两个东西比较万金油

Miller-Rabin

前置知识：

1. 费马小定理

   $a^{p-1}\equiv 1\pmod p,p \ is \ prime$

2. 二次探测（ $\bmod$ 奇素数下 $1$ 的二次剩余 ）

   $x^2\equiv 1\pmod p\Longrightarrow x=1 \ or \ p-1$

   如果不是 $\bmod$ 奇素数，二次剩余可能是更多的值

如果把费马小定理反过来用来检测一个数是否是素数，虽然是错的，但是反例比较少，如果配合二次探测进行测试并取多个 $a$，可以把 $1\sim 10^{18}$ 内的所有数是否是质数判断出来。

具体的，取 $a$ 为前 $12$ 个质数 $(2,3,5,7,11,13,17,19,23,29,31,37)$

然后用费马小定理进行测试，如果 $a^{p-1}\equiv 1\pmod p$ ，就根据二次探测检验是否有 $a^{(p-1)/2}\equiv 1\pmod p$ ，如果值为 $1$ ，就递归 $(p-1)/4$ 处理，如果值为 $p-1$ 或无法向下递归（指数为奇数）直接返回 true ，否则返回 false

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

const int pri[]={2,3,5,7,11,13,17,19,23,29,31,37}; bool ck(ll a,ll k,ll p) { ll x=qp(a,k,p);//a^k mod p if(x!=1&&x!=p-1) return false; if(x==p-1) return true; if(k&1) return true; return ck(a,k>>1,p); } bool Miller_Rabin(ll p) { if(p==1) return false; for(int i=0;i<12;i++) if(p%pri[i]==0) return p==pri[i]; for(int i=0;i<12;i++) if(!ck(pri[i],p-1,p)) return false; return true; }

这样做的复杂度是 $12\log^2 n$，其中因子的个数是一个$\log$，里面每次还做了一次快速幂。

考虑从底向上做，就是说，先求出 $x-1$ 除 $2$ 到不能除的最底层的 $x$ ，这样每次向上一层直接就直接平方 $x^2$ 即可

考虑在某一层 $x=1$，那么如果之前的一层的 $x'\not=p-1$ 的话，就不合法了，或者在最上面一层 $x$ 仍然不为 $1$ ，也是不合法的

这样就优化掉了一个 $\log$

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

const int pri[]={2,3,5,7,11,13,17,19,23,29,31,37}; bool Miller_Rabin(ll p) { if(p==1) return false; for(int i=0;i<12;i++) if(p%pri[i]==0) return p==pri[i]; ll res=p-1;int k=0; while(!(res&1)) res>>=1,++k; for(int i=0;i<12;i++) { ll x=qp(pri[i],res,p); for(int j=0;j<k&&x>1;j++) { ll y=ksc(x,x,p); if(y==1&&x!=p-1) return false; x=y; } if(x!=1) return false; } return true; }

Pollard Rho

现在需要求出 $n$ 的最大约数，考虑在 $[1,n-1]$ 随便 rand 两个数 $x,y$ ，若 $\gcd(x+n-y\bmod n,n)\not=1 \ or \ n$ ，则 $\left|x-y\right |$ 为 $n$ 的一个约数

假设现在有一个近似的随机函数 $f$

令 $f_m(x)=f(f_{m-1}(x))$ ，由于同余系的封闭性，则若干步后一定有循环出现，次数若还没找到约数就退出

具体的，初始 $x=y=rand()$，每一步时 $x=f(x)$ ，$y=f(f(y))$ ，如果 $x=y$ 第二次出现，那么说明存在环，可以证明，环最多被遍历一次就会被找到

取 $f(x)=x^2+c$ ，$c$ 是随机正整数

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

ll f(x,c,p){return (ksc(x,x,p)+c)%p;} ll Find(ll n) { for(int i=0;i<12;i++) if(n%pri[i]==0) return pri[i]; ll x=rand(),y=x,c=rand(); int lim=1e5; do { ll g=gcd((x-y+n)%n,n); if(g!=1&&g!=n) return g; x=f(x,c,n),y=f(f(y,c,n),c,n); }while(x!=y&&lim--); return -1; } void Pollard_Rho(ll n,ll &a) { if(n<a) return; while(!(n&1)) n>>=1;a=2; if(n==1||Miller_Rabin(n)) {a=a>n?a:n;return;} ll d=Find(n); while(d==-1) d=Find(n); if(d<n/d) d=n/d; Pollard_Rho(d,a),Pollard_Rho(n/d,a); }

这样做的复杂度是 $O(n^{\frac{1}{4}}\log n)$

考虑将复杂度优化掉一个 $w(127,512,\dots)$

注意到 $\gcd(x,n)|\gcd(xy\bmod n,n)$

可以倍增 $y$ 的步数，在每次倍增中，$w$ 步取一次 $\gcd$ ，若其为 $1$，说明没找到，继续重复，若为 $n$ ，说明这一次倍增中得到答案，回去重新走一遍，中间遇到不为 $1$ 的就返回，不过这样可能会得到 $n$ ，我们就在外面重跑

这样复杂度可以近似认为是 $(n^\frac{1}{4})$ 的

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

ll f(x,c,p){return (ksc(x,x,p)+c)%p;} ll Find(ll n) { for(int i=0;i<12;i++) if(n%pri[i]==0) return pri[i]; ll x,y=rand(),c=rand(); int w=1<<9; for(int l=1;;l<<=1) { x=y; for(int i=0;i<l;i++) y=f(y,c,n); for(int i=0;i<l;i+=w) { int le=min(l-i,w); ll g=1,las=y; for(int j=0;j<le;j++) g=ksc(g,(y+n-x)%n,n),y=f(y,c,n); g=gcd(g,n); if(g==1) continue; if(g==n) { y=las,g=1; while(g==1) g=gcd((y+n-x)%n,n),y=f(y,c,n); } return g; } } } void Pollard_Rho(ll n,ll &a) { if(n<a) return; while(!(n&1)) n>>=1;a=2; if(n==1||Miller_Rabin(n)) {a=a>n?a:n;return;} ll d=Find(n); while(d==n) d=Find(n); if(d<n/d) d=n/d; Pollard_Rho(d,a),Pollard_Rho(n/d,a); }

杜教筛

Min_25筛

Dirichlet 卷积

反演

二项式反演

莫比乌斯反演

斯特林反演

单位根反演

---

杂项

概率期望

博弈

群论

群

代数结构$(S,\cdot)$​​​ 有封闭，结合，单位元，逆元，称群

陪集

设群 $G$ 某一子群为 $H$，$\forall g\in G$，定义 $H$ 的某左陪集为 $gH=\{gh|h\in H\}$

引理1： $a,b \in G$​​，$aH$​​ 与 $bH$​​ 要么相等，要么不交

推论1（拉格朗日定理）：$|G|=|H|\times|D|$​​，$D$​​ 为 $H$​​​​ 不同的陪集个数

轨道-稳定子定理(orbit-stabilizer theorem)

定义1：置换群

置换：有限集合到自身的双射称为置换，定义在其上的乘法比较显然

置换群：定义在某个确定集合 $X$ 的全部置换与其乘法构成置换群

定义2：轨道 (orbit)

$\forall x \in X$​​​​ ,轨道 $O_x=\{g(x)|g\in G\}$​​​​，又记为 $x^G$​​​​，$G$​​​​ 为 $X$​​​​ 的置换群

因为群的可逆性，所以 $O_x$ 构成 $X$ 的一个等价类

记 $|X/G|$​​ ​为等价类的数量，称轨道数量

定义3：稳定子群

$\forall x\in X$​​​​ ，称 $H_x=\{g|g(x)=x,g\in G\}$​​​​ 为 $x$​​​​​​ 的稳定子群

引理2：轨道构成的等价类与稳定子群的陪集构成的等价类相同

$\forall a,b\in G,a(x)=b(x)\iff a^{-1}(b(x))=x\iff a^{-1}b\in H_x\iff a^{-1}bH_x=H_x\iff bH_x=aH_x$

推论2：$\forall x\in X$​，$H_x$​ 不同的陪集个数即为 $O_x$​ 的大小

由以上，orbit-stabilizer theorem: $|G|=|O_x|\times |H_x|$​​​

Burnside 引理

$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$

$X^g=\{x|g(x)=x,x\in X\}$，表示置换 $g$ 在 $X$ 下的不动点

$\sum_{g\in G}|X^g|=\sum_{x\in X}|H_x|=|G|\sum_{x\in X}{\frac{1}{|O_x|}}=|G|\times|X/G|$

作用：求某集合 $X$​ 经过置换（比如环的旋转）后不同元素的个数

Polya 定理

定义染色行为：

定义待染色集合 $X$ 和颜色集合 $Y$ ，每种染色方案可以定义为一个映射 $\phi:X\to Y$​

则有 $Y^X=\{\phi|\phi \in f:X\to Y\}$​

$G$ 为定义在其上的某置换群

由 Burnside 引理：

$|Y^X/G|=\frac{1}{|G|}\sum_{g\in G}\left|{Y^X}^g\right|=\frac{1}{|G|}\sum_{g\in G}|Y|^{c(g)}$

$c(g)$ 为置换 $g$ 中轮换的个数（每个轮换必须选择同一种颜色才满足不动点）

工具人多项式

多笑考到一次卷积处理字符串，我在这里先扔一个自己的 NTT(FFT) 板子

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

const int mod=998244353,Gi=332748118; /* const int pi=acos(-1); struct complex { double x,y; complex(){} complex(double x,double y){this->x=x,this->y=y;} complex friend operator +(complex n1,complex n2){return complex(n1.x+n2.x,n1.y+n2.y);} complex friend operator -(complex n1,complex n2){return complex(n1.x-n2.x,n1.y-n2.y);} complex friend operator *(complex n1,complex n2){return complex(n1.x*n2.x-n1.y*n2.y,n1.x*n2.y+n1.y*n2.x);} }; */ // a[0~n-1] b[0~m-1] 则卷完后为 0~m+n-1，保证 len=2^k>=n+m 最小值即可 void NTT(int *a,int typ,int len) { int L=-1;for(int i=1;i<len;i<<=1) ++L; for(int i=1;i<len;i++) { turn[i]=turn[i>>1]>>1|(i&1)<<L; if(i<turn[i]) std::swap(a[i],a[turn[i]]); } for(int le=1;le<len;le<<=1) { int wn=qp(typ?3:Gi,(mod-1)/(le<<1)); //complex wn=complex(cos(pi/le),typ?sin(pi/le):-sin(pi/le)); for(int p=0;p<len;p+=le<<1) { int w=1;//complex(1,0) //FFT 下面几行的运算换成复数域下的即可 for(int i=p;i<p+le;i++,w=mul(w,wn)) { int tx=a[i],ty=mul(w,a[i+le]); a[i]=plus(tx,ty); a[i+le]=plus(tx,mod-ty); } } } if(!typ) { //FFT 中此步变换需要注意可能需要取整 // a[i].x <- (int)(a[i].x/len+0.5) int inv=qp(len,mod-2); for(int i=0;i<len;i++) a[i]=mul(a[i],inv); } } void sol() { NTT(a,1),NTT(b,1); for(int i=0;i<len;i++) a[i]=mul(a[i],b[i]); NTT(a,0); }

位运算卷积（FWT）

参考于 位运算卷积(FWT) & 集合幂级数 by command_block ，本文仅留部分摘要及模板

思路：对于 $C(k)=\sum\limits_{t\oplus j=k}A(i)B(j)$ ，考虑构造线性变换 $FWT$，使得 $FWT_A(i)=FWT_B(i)FWT_C(i)$​，同时，我们需要得到一个在时间接受范围内的变换和逆变换（需要保证存在，不一定唯一）。

强行令 $FWT_A(i)=\sum\limits_{j}c(i,j)A(j)$，我们可以计算得出有 $c(i,j)c(i,k)=c(i,j\oplus k)$，如果 $\oplus$ 表示位运算（可拆位），那么变换系数 $c(i,j)$ 也可以拆位，有 $c(i,j)=c(i_k,j_k)c(i_{k-1},j_{k-1}),\dots$

具体的，设 $c=\begin{bmatrix}c(0,0)&c(0,1)\\c(1,0)&c(1,1)\end{bmatrix}$

那么对于 or 运算，我们取 $\begin{bmatrix}1&0\\1&1\end{bmatrix}$​，逆变换为 $\begin{bmatrix}1&0\\-1&1\end{bmatrix}$​

对于 and 运算，我们取 $\begin{bmatrix}1&1\\0&1\end{bmatrix}$​​，逆变换为 $\begin{bmatrix}1&-1\\0&1\end{bmatrix}$​​

对于 xor 运算，我们取 $\begin{bmatrix}1&1\\1&-1\end{bmatrix}$​​​，逆变换为 $\begin{bmatrix}0.5&0.5\\0.5&-0.5\end{bmatrix}$​​​​

特别的，有一些正变换具有一些不错的用处

对于 or 运算，有 $c(i,j)=[i\&j=j]$，即 $A'_i=\sum\limits_{j\in i}A_i$​，可做子集和卷积

对于 xor 运算，有 $c(i,j)=(-1)^{popcount(i\&j)}$​​

最后，我们需要一个较快的变换方式($O(m2^m)$​​​​)，对于一个长为 $2^m$​​​​ 的数组 $A[0,2^m)$​​​​​

其中，$c(i_k,j_k)$ 表示拆位后（从低到高）第 $k$ 位，$A_0,A_1$ 分别表示 $A$ 的前半段与后半段

$\begin{aligned} FWT_A(i)&=\sum_{j=0}^{2^{m-1}-1}c(i,j)A(j)+\sum_{j=2^{m-1}}^{2^m-1}c(i,j)A(j)\\ &=\sum_{j=0}^{2^{m-1}-1}\prod_{k=0}^{m-1}c(i_k,j_k)A(j)+\sum_{j=2^{m-1}}^{2^m-1}\prod_{k=0}^{m-1}c(i_k,j_k)A(j)\\ &=c(i_{m-1},0)\sum_{j=0}^{2^{m-1}-1}\prod_{k=0}^{m-2}c(i_k,j_k)A(j)+c(i_{m-1},1)\sum_{j=2^{m-1}}^{2^m-1}\prod_{k=0}^{m-2}c(i_k,j_k)A(j)\\ &=\left\{\begin{aligned} &c(0,0)FWT_{A_0}(i)+c(0,1)FWT_{A_1}(i),0\le i< 2^{k-1}\\ &c(1,0)FWT_{A_0}(i-2^{k-1})+c(1,1)FWT_{A_1}(i-2^{k-1}),2^{k-1}\le i< 2^k \end{aligned}\right. \end{aligned}$

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <cstdio> #include <cctype> #define gc() getchar() template <class T> void read(T &x) { x=0;int f=0;char c=gc(); while(!isdigit(c)) f|=c=='-',c=gc(); while(isdigit(c)) x=x*10+c-'0',c=gc(); if(f) x=-x; } const int mod=998244353; const int N=(1<<20)+10; int n,len,A[N],B[N],a[N],b[N]; #define mul(a,b) (1ll*(a)*(b)%mod) int plus(int x,int y){return x+y>=mod?x+y-mod:x+y;} void orfwt(int *a,int typ) { for(int le=1;le<len;le<<=1) for(int p=0;p<len;p+=le<<1) for(int i=p+le;i<p+(le<<1);i++) if(typ) a[i]=plus(a[i],a[i-le]); else a[i]=plus(a[i],mod-a[i-le]); } void andfwt(int *a,int typ) { for(int le=1;le<len;le<<=1) for(int p=0;p<len;p+=le<<1) for(int i=p;i<p+le;i++) if(typ) a[i]=plus(a[i],a[i+le]); else a[i]=plus(a[i],mod-a[i+le]); } void xorfwt(int *a,int typ) { for(int le=1;le<len;le<<=1) for(int p=0;p<len;p+=le<<1) for(int i=p;i<p+le;i++) { int tx=a[i],ty=a[i+le]; a[i]=plus(tx,ty),a[i+le]=plus(tx,mod-ty); } if(!typ) { int inv=qp(len,mod-2); for(int i=0;i<len;i++) a[i]=mul(a[i],inv); } } int main() { read(n);len=1<<n; for(int i=0;i<len;i++) read(A[i]); for(int i=0;i<len;i++) read(B[i]); for(int i=0;i<len;i++) a[i]=A[i],b[i]=B[i]; orfwt(a,1),orfwt(b,1); for(int i=0;i<len;i++) a[i]=mul(a[i],b[i]); orfwt(a,0); for(int i=0;i<len;i++) printf("%d ",a[i]); puts(""); for(int i=0;i<len;i++) a[i]=A[i],b[i]=B[i]; andfwt(a,1),andfwt(b,1); for(int i=0;i<len;i++) a[i]=mul(a[i],b[i]); andfwt(a,0); for(int i=0;i<len;i++) printf("%d ",a[i]); puts(""); for(int i=0;i<len;i++) a[i]=A[i],b[i]=B[i]; xorfwt(a,1),xorfwt(b,1); for(int i=0;i<len;i++) a[i]=mul(a[i],b[i]); xorfwt(a,0); for(int i=0;i<len;i++) printf("%d ",a[i]); puts(""); return 0; return 0; }

类欧几里得 【simple】

一些引理

• $\lfloor\frac{ai}{c}\rfloor=\lfloor\frac{a\bmod c}{i}\rfloor+i\lfloor\frac{a}{c}\rfloor$

• $X^2=-X+\sum_{i=1}^Xi$

• $a\ge b\Rightarrow a+1>b(a,b\in \mathbb Z)$

• $a>b\Rightarrow a>\lfloor b\rfloor(a\in \mathbb Z,b\in \mathbb R)$

• $\lfloor a\rfloor>b\Rightarrow a>b(a\in \mathbb R,b\in \mathbb Z)$

结论

• 定义

  $\begin{aligned} &f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\\ &g(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2\\ &h(a,b,c,n)=\sum_{i=0}^ni\lfloor\frac{ai+b}{c}\rfloor \end{aligned}$

• 结论

  $\begin{aligned} &f(a,b,c,n)=\left\{\begin{aligned} &(n+1)\lfloor\frac{b}{c}\rfloor,a=0\\ &f(a\bmod c,b \bmod c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor,a\ge c \ or \ b\ge c\\ &n\lfloor\frac{an+b}{c}\rfloor-f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1),a<c \ and \ b<c \end{aligned}\right.\\ &g(a,b,c,n)=\left\{ \begin{aligned} &(n+1)\lfloor\frac{b}{c}\rfloor^2,a=0\\ &g(a\bmod c,b \bmod c,c,n)+\frac{(2n+1)(n+1)n}{6}\lfloor\frac{a}{c}\rfloor^2+(n+1)\lfloor\frac{b}{c}\rfloor^2+2\lfloor\frac{a}{c}\rfloor h(a\bmod c,b \bmod c,c,n)\\&+2\lfloor\frac{b}{c}\rfloor f(a\bmod c,b \bmod c,c,n)+n(n+1)\lfloor\frac{a}{c}\rfloor \lfloor\frac{b}{c}\rfloor,a\ge c \ or \ b\ge c\\ &n(\lfloor\frac{an+b}{c}\rfloor)(\lfloor\frac{an+b}{c}\rfloor+1)-2h(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)-2f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)\\&-f(a,b,c,n),a<c \ and \ b<c\\ \end{aligned} \right.\\ &h(a,b,c,n)=\left\{\begin{aligned} &\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor,a=0\\ &h(a\bmod c,b \bmod c,n)+\frac{(2n+1)(n+1)n}{6}\lfloor\frac{a}{c}\rfloor+\frac{n(n+1)}{2}\lfloor\frac{b}{c}\rfloor,a\ge c \ or \ b\ge c\\ &\frac{1}{2}[n(n+1)\lfloor\frac{an+b}{c}\rfloor-g(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor-1)-f(c,c-b-1,a,\lfloor\frac{an+b}{c}\rfloor)]\\ \end{aligned}\right. \end{aligned}$

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

  #include <cstdio> #include <cctype> const int SIZE=1<<21; char ibuf[SIZE],*iS,*iT; #define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++) template <class T> void read(T &x) { x=0;char c=gc(); while(!isdigit(c)) c=gc(); while(isdigit(c)) x=x*10+c-'0',c=gc(); } struct node { int f,g,h; node(){} node(int a,int b,int c){f=a,g=b,h=c;} }; const int mod=998244353,inv2=499122177,inv6=166374059; inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;} #define mul(a,b) (1ll*(a)*(b)%mod) #define S1(n) (1ll*n*(n+1)/2%mod) #define S2(n) mul(mul(n<<1|1,n+1),mul(n,inv6)) node query(int a,int b,int c,int n) { int ac=a/c,bc=b/c; if(!a) return node(mul(n+1,bc),mul(n+1,mul(bc,bc)),mul(S1(n),bc)); if(a>=c||b>=c) { node ret,yuu=query(a%c,b%c,c,n); ret.f=add(yuu.f,add(mul(S1(n),ac),mul(n+1,bc))); ret.g=add(yuu.g,add(mul(S2(n),mul(ac,ac)),add(mul(n+1,mul(bc,bc)), mul(2,add(mul(ac,yuu.h),add(mul(bc,yuu.f),mul(S1(n),mul(ac,bc)))))))); ret.h=add(yuu.h,add(mul(S2(n),ac),mul(S1(n),bc))); return ret; } int m=(1ll*a*n+b)/c; node ret,yuu=query(c,c-b-1,a,m-1); ret.f=add(mul(n,m),mod-yuu.f); ret.g=add(mod-ret.f,mul(2,add(mul(n,S1(m)),add(mod-yuu.h,mod-yuu.f)))); ret.h=mul(inv2,add(mul(n,mul(n+1,m)),add(mod-yuu.g,mod-yuu.f))); return ret; } int main() { int T,n,a,b,c;read(T); while(T--) { read(n),read(a),read(b),read(c); node ret=query(a,b,c,n); printf("%d %d %d\n",ret.f,ret.g,ret.h); } return 0; }

参考资料

• OI-wiki
• 具体数学
• 算法竞赛进阶指南
• hz 的群论学习笔记