最腥知识

· · 个人记录

二分图博弈

给定一张二分图, 有一枚棋子在一个左部点上. A 和 B 依次行动, 每次将棋子移到有边相连的另一点, 不能移动至之前到过的点, 无法移动者输. 对每个初始结点 v 计算 f(v) 表示 A 必胜 (1) 或必败 (0).

--- 设 $W$ 表示 **所有** 最大匹配方案构成的集合, $M$ 表示一个最大匹配方案, $M(v)$ 表示 $v$ 所匹配的点. 对于一个初始结点 $v$, $M \in W \Rightarrow v \in M \Leftrightarrow f(v)=1$. <details><summary>Proof</summary> > - 充分性 > > 任取一个最大匹配 $M$, A 将棋子从 $v$ 移至 $M(v)$, 则 B 无法移动 或 只能沿非匹配边移动至 $u$. 假设 $u \notin M$, 则可以将 $M$ 中的匹配 $(v, M(v))$ 改为 $(u, M(v))$ 得到最大匹配 $M'$ 且 $v \notin M'$. 故 $u \in M$, A 可以继续移动至 $M(u)$, 故 A 必胜. > - 必要性 > > 假设有 $M \in W$ 且 $v \notin M$, 则 A 无法移动 或 只能沿非匹配边移动至 $u$, 由于不存在增广路, 有 $u \in M$, 则 B 可以移动至 $M(u)$. 故 A 必败. </details> 建立经典的网络流求最大匹配模型, 边权全为 1. 考虑任意一个最大流 $F$ 与其残量网络 $G$ (有流量的边反向). 对于源点 $s$ 能到达的左部点集 $S$, 有 $v \in S \Leftrightarrow f(v)=0$, 即 $v \in S \Leftrightarrow \exist M \in W, v \notin M$. <details><summary>Proof</summary> > - 充分性 > > 假设有一最大匹配 $M$ 使得 $v \in M$, 则必然存在一条简单路径 $P$ 从 $s$ 到 $v$ 和 $G$ 中的一条边 $(v, s)$. 则 $P + (v, s)$ 形成环流, 可以构造 $M'$ 使得 $v \notin M'$. > - 必要性 > > 假设 $\forall M \in W, v \in M$, 则对于残量网络 $G$ 中不存在环流同时经过 $s$ 和 $v$. 又有 $G$ 中存在边 $(v, s)$, 则不存在简单路径 $P$ 从 $s$ 到 $v$, 则 $v \notin S$. </details> 故直接做即可, $O(m \sqrt n)$. # 线性规划对偶 给定一个序列 $a_i$, 要求用两种形式的串覆盖每个位置 $a_i$ 次. 一种为覆盖一个区间, 一种为在一个区间内覆盖一个跳过一个. 问最少用的串个数. $1 \le n \le 10^6$, $1 \le a_i \le 10^9$. --- 设一个串能覆盖到的点集为 $S_j$, 则 $\{2, 4, 6\}$ 为一个合法的 $S_j$, 设合法的 $S_j$ 总数为 $m$. 设 $m$ 维向量 $z$ 表示每种串使用的数量, 需满足 $z_i \ge 0$. 则需满足 $\forall i, \sum_j z_j [i \in S_j] = a_i$, 变形为 $\forall i, \sum_j z_j [i \in S_j] \ge a_i$ 且 $\forall i, \sum_j -z_j [i \in S_j] \ge -a_i$. 设 $2n$ 维向量 $t$ 满足 $t_i = a_i (-1)^{[n + 1 \le i \le 2n]}$. 设 $2n \times m$ 的矩阵 $A$ 满足 $A_{i,j} = [i \in S_j] (-1)^{[n + 1 \le i \le 2n]} \space (1 \le i \le 2n)$. 设单位 $m$ 维向量 $i$ 满足 $i_i = 1$. 则可将限制条件改写为 $Az \ge t$, $z \ge 0$, 需要最小化 $z \cdot i$. 其答案等于 $A^Tz' \le i$, $z' \ge 0$, 最大化 $z' \cdot t$, 其中 $z'$ 为一 $2n$ 维向量. <details><summary>Proof</summary> > 考虑将限制条件与需要最小化的式子再次拆开, 得到 $\sum_j A_{x, j} z_j \ge t_x$, $z_j \ge 0$, $\text{minimize} \sum_j z_j i_j$. 考虑做一个类似高斯消元的事情, 将限制条件线性组合, 使得不等式左侧恰为 $\sum_j z_j i_j$, 那么取右侧的最大值即为左侧的下界, 且一定能够取到. > > 故分别设 $b_x$ 和 $c_j$ 为两种限制的系数, 显然需要 $b_x \ge 0$, $c_j \ge 0$, 否则不等式会变号. 将所有限制相加, 得到 $\sum_j z_j (c_j + \sum_x A_{x, j} b_x) \ge \sum_x t_x b_x$. 故需要有限制 $c_j + \sum_x A_{x, j} b_x = i_j$, 需要最大化 $\sum_x t_x b_x$. > > 观察与 $c_j$ 有关的限制, 不难发现容易将限制改写为 $b_x \ge 0$, $\sum_x A_{x, j} b_x \le i_j$. 再改写为矩阵和向量的形式, 有 $b \ge 0$, $A^T b \le i$, 最大化 $b \cdot t$. 将 $b$ 改写为 $z'$ 即可得证. </details> 即需满足 $\forall j, \sum_i [i \in S_j] (-1)^{[n + 1 \le i \le 2n]} z'_i \le 1, z'_i \ge 0$, 最大化 $\sum_i z'_i a_i (-1)^{[n + 1 \le i \le 2n]}$. 设 $n$ 维向量 $x$ 与 $y$ 满足 $z' = [x \space y]$. 条件改写为 $\forall j, \sum_i [i \in S_j] (x_i - y_i) \le 1, x_i \ge 0, y_i \ge 0$, 最大化 $\sum_i a_i (x_i - y_i)$. 设 $n$ 维向量 $d$ 满足 $d = x - y$. 条件继续改写为 $\forall j, \sum_i [i \in S_j] d_i \le 1$, 最大化 $\sum_i a_i d_i$. 由于对于所有 $1 \le i \le n$, 有 $\{i\}$ 为合法的 $S_j$, 则 $d_i \le 1$. 考虑 $\max_j \sum_i [i \in S_j] d_i$ 事实上为 3 种最大子段和 (全局, 奇数位, 偶数位), 则当 $d_i = -1$ 时只要前面的部分合法 (最大子段和 $\le 1$), $i$ 这段前缀必然被舍弃. 故 $d_i \ge -1$. 故 $d_i \in \{-1, 0, 1\}$. 因此设 $f_{i, s0, s1, s2}$ 表示考虑了前 $i$ 位, 3 种最大子段和分别为 $s0$, $s1$, $s2$ ($0 \le s0$, $s1$, $s2 \le 1$) 的最大 $\sum_i a_i d_i$, 转移考虑 $d_{i+1}$ 的三种取值. $O(n)$. # 多项式快速幂 给定 $k$ 项的多项式 $F$ 和 $m$, 求 $G = F^m$ 的前 $n$ 项系数, 对 $10^9 + 7$ 取模. $1 \le n \le 5 \times 10^6$, $1 \le m \le 10^{18}$, $1 \le k \le 5

两边求导,

G' = mF^{m-1}F'

同乘 F,

G'F = mGF'

取第 n 项系数

\sum_{i=0}^{k-1} (n-i+1)g_{n-i+1}f_i = m \sum_{i=0}^{k-1} ig_{n-i+1}f_i \sum_{i=0}^{k-1} (mi+i-n-1)g_{n-i+1}f_i = 0 \sum_{i=1}^{k-1} (mi+i-n-1)g_{n-i+1}f_i = (n+1)g_{n+1}f_0 g_{n+1} = \frac{\sum_{i=1}^{k-1} (mi+i-n-1)g_{n-i+1}f_i}{(n+1)f_0}

特别地, g_0 = f_0^m, 其余项均可递推得到.

# 最小均值回路 给定一张边带权的有向图, 求其中平均值最小的环. $1 \le n, m \le 5000$, $|w_i| \le 10^9

显然可以二分答案 mid, 每次判断是否有 ans \ge mid. 将所有边权减去 mid 即为判断有无正环. SPFA 容易解决. O(nm \log V).

考虑将所有边权减去 ans, 则此时无负环, 存在至少一个 0 环. 新图的答案为 0.

任意选取一个能够到达所有点的结点 s, 若不存在可以新添加一个点并向所有点连边.

下面设 f_{i,j} 表示从 s 出发经过恰好 j 条边到达 i 的最短路径长度, d_i 表示从 s 出发到达 i 的最短路长度, x \rightarrow y 表示 x 到 y 的任意一条最短路径, |x \rightarrow y| 表示最短路径长度. 有

d_i = \min_{0 \le j \le n-1} \{f_{i,j}\}, \space f_{i,n} \ge d_i

<details><summary>Proof</summary>

反证法. 考虑一条长度 \ge n 的路径, 则经过了至少 n+1 个结点, 则其为复杂路径. 由于没有负环, 则删去这个环一定不劣. </details>

变形得到

f_{i,n}-d_i = \max_{0 \le j \le n-1} \{f_{i,n}-f_{i,j}\} \ge 0

因为一定存在一个 i 使得上式取等, 即 f_{i,n} = d_i,

<details><summary>Proof</summary>

考虑在 0 环上随意选择一点 x, 从 s 走一条最短路径走到 x, 再在环上绕圈直到走了 n 条边到达 t. 因为 s \rightarrow x 至多经过 n-1 条边, 则这样的 t 必然存在.

设 |x \rightarrow t| = w, 我们断言 f_{t,n} = d_t, 则需要证明 d_x + w = d_t.

假设 d_x + w > d_t, 则有 d_x > d_t - w. 那么 s \rightarrow t \rightarrow x 为一条更短的路径, 矛盾. </details>

则有

\min_{1 \le i \le n} \max_{0 \le j \le n-1} \{f_{i,n}-f_{i,j}\} = 0

考虑将边权重新加上 ans. 则此时

\min_{1 \le i \le n} \max_{0 \le j \le n-1} \{\frac{f_{i,n}-f_{i,j}}{n-j}\} = ans

简单 Dp 出 f_{i,j}, 则容易计算出 ans. O(nm).

特别地, 从推导过程中可以看出, 只有当 f_{i,n} 代表的路径中包含了 f_{i,j} 代表的路径, 才有可能作为答案. 故当边权用指数来表示时不用考虑减法退位的情况.

左右横跳

$1 \le n \le 10^9$, $0 \le |S| \le 10^6$. --- 设 L 为 $-1$, R 为 $1$. 考虑什么时候会全死光. 容易发现 $S^\infty$ 中不能有连续的一段使得和为 $n$, 否则之前在 $0$ 的人死不了. 故为充要条件. 考虑判定. - 跨过至少 $3$ 个 $S$. 此时有 $sum > 0$, 否则不优. 容易发现此为充要条件. - 跨过 $2$ 个 $S$. 此时 $premax + sufmax \ge n$. - 在 $S$ 内部. 此时 $S$ 存在一个前缀使得 $sufmax \ge n$. 其中 $sum$ 为整串的和, $premax$ 为 $S$ 的一个前缀使得其 $sum$ 最大, $sufmax$ 同理. 考虑如何动态维护 $sufmax$. 有 $sufmax \leftarrow \max(sufmax + w_i, 0)$, 其中 $w_i \in \{-1, 1\}$. 容易发现 $sufmax$ 也即之前在 $0$ 的人此时的位置, 但不重要. 现在至少有一个人不会死. 考虑计算活着的个数. 因为之前在 $0$ 的人不会死, 则到过 $0$ 的人都不会死. 故现在可以去除走到 $-1$ 则回到 $0$ 的限制, 因为反正不会死多往左走几步也无所谓, 则现在所有人始终为一个长为 $n$ 的区间. 去除走到 $n$ 就不能动的限制, 考虑区间到达过的最靠右的位置, 该时刻与 $[0,n-1]$ 的交的长度即为答案. 发现如果走满了 $S$ 则不优, 因为 $sum \le 0$, 故会取 $premax$. 故答案为 $n - premax$. 时间复杂度 $O(|S|)$. # 多项式取模 给定最高项次数分别为 $n$ 和 $m$ 的多项式 $F(z)$ 和 $G(z)$, 求最高项次数分别为 $n - m$ 与 $m - 1$ 的多项式 $Q(z)$ 与 $R(z)$, 使得 $$F(z) = Q(z) G(z) + R(z).$$ $1 \le n \le 10^5$, $1 \le m \le n$. --- 考虑定义最高项系数为 $n$ 的多项式 $F(z)$ 的转置 $$F^T(z) = z^n F(\frac{1}{z})$$ 即 reverse 每一项的系数. 有 $$F(z) = Q(z) G(z) + R(z)$$ $$z^n F(z) = z^{n - m} Q(z) z^m G(z) + z^{n - m + 1} z^{m - 1} R(z)$$ $$F^T(z) = Q^T(z) G^T(z) + z^{n - m + 1} R^T(z)$$ 因为 $Q^T$ 的最高项系数为 $n - m$, 则 $$F^T(z) = Q^T(z) G^T(z) \pmod {z^{n - m + 1}}$$ $O(n \log n)$. # 多项式多点求值 给定最高项次数为 $n$ 的多项式 $F(z) = \sum_i f_i z^i$ 与长为 $m$ 的序列 $a$, 求 $F(a_i)$. $1 \le n,m \le 10^5$. --- 考虑 $F(z) = F_i(z) * (z - a_i) + ans_i$, 则只要对每个 $i$ 求出 $F(z) \bmod (z - a_i)$ 的值即可. 考虑分治取模, 左边每次模 $\prod_{i = l}^{mid} (z - a_i)$, 右边同理. $O((n+m) \log^2 n)$. ~~或许可以利用 class 20240404 转置原理, 但我还不会.~~ # BDFS 序 考虑如下事实, DFS 序能够方便地处理 子树 与 链 的问题, 而 BFS 序能处理 较近的邻域 的问题. 因此, 将两者结合, 具体而言在根上方添加长为 $k$ 的链, 从链顶开始 DFS, 每次将该结点距离为 $k$ 的后代加入序中, 得到 k-BDFS 序. 一个结点的子树内的距离 $\le k$ 的结点在序上分别构成了 $k$ 个区间. 一棵子树除深度严格前 $k$ 小外在序上为一个区间. 一条重链除深度前 $k$ 小外在序上为一个区间, 但要把 非超重儿子 (在重链上的深度为前 $k$ 小) 剔除. 例题: 20240514 tree. # DAG 链剖分 给定一个字符串 $S$, 每次询问在 SAM 上匹配 $S$ 的一个子串 $T$ 所经过的点的权值和. $1 \le n, q \le 2 \times 10^5$, $\Sigma = 26$. --- 对每个结点计算 $out_i$ 与 $in_i$, 分别表示以 $i$ 为起点和终点的路径数. 设 $pre_i$ 和 $suf_i$ 分别为 $in_j$ 最大的前驱和 $out_j$ 最大的后继. 定义一条边 $x \rightarrow y$ 为重边当且仅当 $suf_x = y$ 且 $pre_y = x$. 由于一个点至多只有一条出重边, 则所有点可以被划分成若干条链. 考虑走一条轻边 $x \rightarrow y$, 由于 $out_x = 1 + \sum_{x \rightarrow i \in G} out_i$, $in_x = 1 + \sum_{i \rightarrow x \in G} in_i$, $suf_x = y$ 与 $pre_y = x$ 中至少不满足一个, 则要么 $out_x > 2out_y$ 要么 $2in_x < in_y$. 故一条路径可以被拆分为 $O(\log P)$ 条重链的区间, 其中 $P$ 为图中路径条数, 在 SAM 上 $P = \frac{n(n-1)}{2}$, 则区间数为 $O(\log n)$. 预处理 SA 以求 LCP, 预处理重链上权值前缀和并差分查询. $O(n \log n)$. 事实上目前能想到的应用场景仅限于 SAM. # Best 定理 给定一张欧拉图 (有向图, 每个点入度等于出度, 强连通), 求欧拉回路数量. $1 \le n \le 300$, $n \le m \le n(n-1)$. --- 根据 Best 定理, 有 $$ans = cnt \times \prod_i (d_i-1)!$$ , 其中 $cnt$ 为以 1 为根 (事实上拿什么当根值都相等) 的内向生成树数量, $d_i$ 为 $i$ 的出度 (即入度). <details><summary>Proof</summary> > 感性理解 (严谨证明不会). 考虑一棵内向生成树, 将一个点到父亲的边钦定最后走, 其它边的顺序随意, 根的所有边随意, 则从根开始走, 必然能走出一条合法欧拉回路. 但由于会经过根 $d_s$ 次, 所以需要对这个环除以 $d_s$. </details> 同时, 根据矩阵树定理, 有 $$cnt = \det(D - A){2, 3, 4, ..., n \choose 2, 3, 4, ..., n}$$ , 其中 $D$ 为出度矩阵, $A$ 为边的邻接矩阵, $a_{i, j} = 1 \Leftrightarrow i \rightarrow j \in E$. 事实上去除任意一行一列都可以. <details><summary>Proof</summary> > 不会. </details> 故求完行列式之后再乘几个阶乘即可. $O(n^3)$. # 保序回归 给定长度为 $n$ 的 $v_i$, $w_i$ 和 $y_i$ 以及一个正整数 $p$ 和偏序关系 $\preceq$ (事实上可以理解为 $\le$), 构造一个长度为 $n$ 的序列 $x_i$ 满足 $v_i \preceq v_j \Rightarrow x_i \preceq x_j$, 最小化 $\sum_{i=1}^n w_i |x_i-y_i|^p$. $1 \le n \le 10^5$, $1 \le v_i \le n$, 答案值域在 $10^{18}$ 以内. --- 考虑人为地加上一个额外限制, $\forall 1 \le i \le n, l \le x_i \le r$. 称这个问题为 $\mathcal P[l, r]$. 定义函数 $$ F(x, l, r) = \begin{cases} l \space (x < l) \\ x \space (l \le x \le r) \\ r \space (x > r) \end{cases}$$ . 设 $\mathcal P[-\infty, \infty]$ 的一组最优解为 $x_i$, 则 $F(x_i, l, r)$ 为 $\mathcal P[l, r]$ 的一组最优解. <details><summary>Proof</summary> > 合法性显然. 由于 $w_i |x_i-y_i|^p$ 为凸函数, 则离原先的最优解越远越劣, 故得证. 仅为感性证明, 具体证明参考 [这篇博客](https://blog.csdn.net/qq_42101694/article/details/105294249). </details> 故考虑整体二分, 每次计算 $\mathcal P[mid, mid+1]$ 的答案, 若 $x_i' = mid$ 则说明 $x_i \le mid$, 否则 $x_i > mid$. 对于其他的不在当前二分区间里的元素, 其对在区间里的元素没有限制作用且贡献固定, 则无需考虑. 考虑如何求解 $\mathcal P[mid, mid+1]$. 由于每个元素只有两种取值, 则事先将所有元素按 $v_i$ 排序, 对每个前缀求出都取 $mid$ 的贡献, 后缀同理. 枚举分界点容易计算最优解. 单次 $O(cnt)$, 其中 $cnt$ 为在二分区间内的元素个数. 总时间复杂度 $O(n \log V)$. # 杨表 给定长度为 $n$ 的序列 $a_i$, $m$ 次询问 $a_i$ 长为 $k$ 的前缀中, 最长的满足 LIS 的长度不超过 $l$ 的子序列的长度. $1 \le n \le 5 \times 10^4$, $1 \le m \le 2 \times 10^5$. --- 使用 Dilworth 定理将 LIS 长度不超过 $l$ 转化为可用不超过 $l$ 条不增子序列覆盖. 考虑一个序列 $\lambda_i$, 满足 $\lambda_1$ 为 $a_i$ 最长不增子序列的长度, $\lambda_2$ 为删去 $a_i$ 中某一个最长不增子序列 (显然删哪个不会有影响) 后, 最长不增子序列的长度, 以此类推. 显然有 $\sum \lambda_i = n$, 且询问 $l$ 的答案即为 $\sum_{i = 1}^l \lambda_i$. 问题转化为对每个前缀求出 $\lambda_i$, 考虑如下数据结构 $P$ : 第 $i$ 行有 $\lambda_i$ 个单调不增的数, 且这些数的并集为 $\{a_i\}$, 且每次在序列末尾添加一个数 $x$ 时可以动态维护 $\lambda_i$ 的变化. 显然有该数据结构沿主对角线转置后得到的新的 $\lambda'_i$ 序列, 为将前文不增全部改为上升对应的 $\lambda_i$ 序列. 考虑如下维护方式: 对于每一行 $i$, 二分找到第一个 $j$ 满足 $P_{i, j} < x$, 则将 $P_{i, j}$ 与 $x$ 交换, 并继续考虑下一行. 显然对于第一行来说就是二分法求最长不增子序列的过程, 后面的行可以归纳证明. 故每次 $\lambda_i$ 的改变只会发生在恰好一个位置, 且会使这个位置的 $\lambda_i$ 增加 1. 现在我们已经得到了一个 $O(n^2 \log n)$ 地构造 $P$ 的方式, 但无法通过此题. 考虑 $\lambda_i$ 为单调不增的, 则若 $P_{i, j}$ 存在, 有 $ij \le n$. 故 $i$ 与 $j$ 至少有一个不超过 $\sqrt n$. 只维护 $P$ 的前 $\sqrt n$ 行与 $P$ 的转置 $Q$ 的前 $\sqrt n$ 行, 则构造 $P$ 的时间复杂度降为 $O(n \sqrt n \log n)$. 将询问离线后使用树状数组维护 $\lambda_i$ 序列即可. $O(n \sqrt n \log n + m \log n)$. # 双调排序 考虑一次操作 ``CompareAndSwap(i, j)`` (后称 ``F(i, j)``) 为比较 $a_i$ 与 $a_j$ 的值, 若 $a_i < a_j$ 则交换 $a_i$ 与 $a_j$. 其中 $i \neq j$. 显然存在某些排序算法可以与具体序列无关地只使用这个操作来排序, 如选择排序和冒泡排序. 定义一次并行操作为若干操作集合 $S = \{(i_1, j_1), ..., (i_t, j_t)\}$, 且满足可重集 $T = \{x | (x, y) \in S \lor (y, x) \in S\}$ 中每个元素只出现一次. 即操作涉及到的元素彼此无交. 定义并行时间复杂度函数 $\Omega$ 为排序算法在尽可能的并行后所需的并行操作次数的数量级. 现介绍一种 $O(n \log^2 n)$, $\Omega(\log^2 n)$ 的排序算法. --- 定义一个序列为双调序列, 当且仅当存在一种该序列的轮换, 使得其为一个单峰序列. 考虑如何排序一个长度为 $2^n$ 的双调序列. 考虑将其拆成左右两半, 并一一对应地进行 $F(l, mid+1), F(l+1, mid+2), ... F(mid, r)$. 发现其左右两半分别变成了双调序列, 且左边的最大值小于等于右边的最小值. <details><summary>Proof</summary> > 容易发现只要证明对每个 01 序列合法即可. 对于 01 序列来说双调序列等价于连续段不超过三个. > > 若其中一半连续段只有一个, 是平凡的. 一定会全部交换或全部不交换, 则交换前后两半的连续段都不超过三个, 且要么左边全 0 要么右边全 1. > > 否则两边都恰有两个连续段, 则会交换一个前缀或一个后缀, 且至少有一边会换成全 1 或全 0, 另一边连续段数至多增加 1. </details> 故只需要操作后递归地排序即可. 发现同层的递归均可并行运算, 故 $O(n \log n)$, $\Omega(\log n)$. 考虑如何将一个长度为 $2^n$ 的一般序列转化为双调序列. 发现每一个数都是一个双调序列, 故可以将每一个小序列交错地升序和降序排序, 随后相邻的两个小序列就可以合并成一个大的双调序列. 发现同层的排序的同层的递归均可并行运算, $O(n \log^2 n)$, $\Omega(\log^2 n)$. 考虑其需要支持升序和降序排序, 难以将序列长度扩展到任意, 故考虑将如何降序排序删去. 若对每个小序列都升序排序, 则序号为偶数的小序列需要 reverse. 考虑排序这个合并后的大双调序列, 在第一次递归时把右侧的编号 reverse, 即进行 $F(l, r), F(l+1, r-1), ... F(mid, mid+1)$ 操作, 之后显然两半的序列又分别成为了双调序列, 故使用和之前一样的排序方式即可. 现在只需对序列进行升序排序, 故对于序列长度不是 $2^n$ 的, 考虑在其后补上若干 $+\infty$ 即可. $O(n \log^2 n)$, $\Omega(\log^2 n)$. # 一类特殊排列计数问题的另类解法 给定一个长度为 $m$ 的集合序列 $a_i$, 集合中可能出现的元素为 $[0, n)$. 你需要维护一个集合 $S$, 初始为 $U$, 从 $1$ 到 $m$ 地依次考虑每个 $a_i$, 若 $S \cap a_i \neq S \land S \cap a_i \neq \varnothing$, 则 $S \leftarrow S \cap a_i$, 否则不变. 现在你需要对每个元素 $x \in U$ 求出在 $a_i$ 的 $m!$ 个排列中有多少个 $S$ 最终包含了 $x$. 取模. $1 \le n \le 20$, $1 \le m \le 10^6$. --- 对 $a_i$ 的排列计数非常烦人, 需要保证每个元素都恰好出现一次. 考虑怎么把这个限制去除掉. 发现一个局面是否对一个元素有贡献只与最终的 $S$ 有关, 故可以只维护 $S$ 而不枚举元素. 注意到, $S$ 的转移只与新加入的元素有关, 且满足非严格 (有自环的 DAG) 的拓扑序 (即集合大小不增), 且满足可复操作性 (类似 checkmin, 多次对同一个元素操作值不变), 则对于这个烦人的限制, 考虑在状态内加入 当前的 $S$ 和 使得 $S$ 不变的未使用的 $a_i$ 数量 和 已经使用过的 $a_i$ 数量. 状态数 $O(2^nm^2)$, 每次转移考虑插入一个不变的 $a_i$ 或者一个会变化的 $a_i$ 并更新不变的数量. 注意到, 由于排列总数为 $n!$, 则可以考虑统计合法的概率, 便可以钦定每次转移 $S$ 都会变化, 并在所有会变化的转移中等概率的选择一个, 则可以省去第二维. 此时无法再记录已经使用过的 $a_i$ 数量, 但发现记这个的作用仅为判断是否是终止状态， 故考虑另一种方式判断是否是终止状态. 记使得 $S$ 变化的 $a_i$ 数量为 $c_S$, 则若一个 $S$ 满足 $c_S = 0$, 其为终止状态. 状态数 $O(2^n)$, 转移考虑枚举 $S$ 的子集 $T$ 满足 $T \neq S \land T \neq \varnothing$, 从 $S$ 转移到 $T$. 设 $trans_{S, T}$ 为 $S$ 有多少个 $a_i$ 会转移到 $T$, 其状态数为 $O(3^n)$. 则转移系数为 $\frac{trans_{S, T}}{c_S}$. 发现 $c_S = \sum_{T \neq S \land T \neq \varnothing} trans_{S, T}$, 故只需求出 $trans_{S, T}$ 即可. 事实上, $trans_{S, T} = \sum_i [S \cap a_i = T]$, 则 $trans_{U, T}$ 是好求的. 考虑从大小较大的转移到大小较小的, 对于一个 $S$ 求出任意一个元素 $x$ 满足 $x \notin S$, 分类讨论是否有 $x \in a_i$, 可得 $trans_{S, T} = trans_{S \cup \{x\}, T} + trans_{S \cup \{x\}, T \cup \{x\}}$. 现在得到了一个时空复杂度均为 $O(3^n)$ 的做法, 考虑优化. 发现瓶颈在于求转移系数和转移, 考虑一种更好的方式刻画转移. 事实上, 转移可以表示为 $\frac{f_S}{c_S} \rightarrow f_{S \cap a_i} \space (S \cap a_i \neq S \land S \cap a_i \neq \varnothing)$. 故可设 $g_S$ 为 $a_i$ 中 $S$ 出现的次数, 转移成为了一个半在线的位与卷积. 距离板子还剩一个 $c_S$ 的求解. 考虑用 $m$ 减去不变的数量, 则对于一个 $a_i$ 来说会对 $S \subseteq a_i$ 和 $S \subseteq U \setminus a_i$ 产生贡献. 高维后缀和即可. $O(n2^n)$. 对于半在线位与卷积 (即 $f_s \times g_t \rightarrow f_{s \cap t}, s \not \subseteq t$), 可以以 $\text{popcount}$ 为拓扑序, 从大往小地递推, 每次将 $\text{popcount} > i$ 的转移到 $\text{popcount} = i$ 的. 故需要做 $O(n)$ 次 $O(n2^n)$ 的 FWT, $O(n^22^n)$. 故总时间复杂度 $O(n^22^n + m)$, 空间复杂度 $O(2^n)$. # 树上背包 考虑一类树上背包问题, 结点 $x$ 的 Dp 数组长度为 $min(size_x, k) \space (k < n)$, 合并两棵子树为暴力卷积, 其复杂度为 $O(nk)$. <details><summary>Proof</summary> > 考虑 $x$ 的其中一个儿子 $i$, 其会与 $i$ 以前的所有儿子合并的结果来合并, 故复杂度为 $O(min(presize_i, k) \times min(size_i, k))$. > > 考虑 $presize_i$ 与 $size_i$ 在 Dfn 序上对应的区间, 这两个区间一定是连续的. 考虑将 $k$ 的贡献放在 $presize_i$ 的后 $k$ 个点与 $size_i$ 的前 $k$ 个点上, 点对间两两产生贡献. > > 则所有产生贡献的点对之间必定满足之间的距离 $< 2k$, 故一个点至多只会与 $4k$ 个点产生贡献. 复杂度 $O(nk)$. </details> # 错排数 计数长度为 $n$ 的排列 $p_i$, 满足 $p_i \neq i \space (i \le m)$. $1 \le n \le 10^7$, $0 \le m \le n$. --- 考虑 $n = m$ 如何做. 事实上即为常规定义的错排数 $D(n)$. 设 $f_i$ 表示 $n = m = i$ 时的答案. 设 $p_i = x \neq i$, 分类讨论 $p_x$ 与 $i$ 的关系. - $p_x = i

显然可以将 i 与 x 一同删去, 方案数为 f_{i-2}.

$$f_i = (i-1)(f_{i-2}+f_{i-1})$$ 现在考虑一般情况, 设 $g_{i, j}$ 表示 $n = i$, $m = j$ 时的答案. 我们希望通过分类讨论某个特殊位置的值使得能够删去几个位置. 显然第 $j$ 个比第 $i$ 个更加特殊 (多了一个不等关系). 设 $p_j = x \neq j$, 分类讨论 $p_x$ 与 $j$ 的关系. - $p_x = j

同样的一同删去 j 和 x, 发现为了维护 j 需要额外讨论 x 与 j 的关系来判断 j 减少 1 还是 2.

此处省略另一种分类讨论. 发现我们需要分类讨论 2 \times 2 = 4 种情况, 导致转移方程中有四项, 这显然是不优美且难以优化的. 注意到促使我们选择分类讨论第 j 个位置的原因是这样多了一个条件, 即 x \neq j. 但略加思考我们发现设 p_x = j 也能满足 x \neq j, 而且无需讨论第一个分支, 故有了一个新的思路.

设 p_x = j \neq x, 分类讨论 x 与 j 的关系.

$$g_{i, j} = (j-1)g_{i-1, j-2} + (i-j)g_{i-1, j-1}$$ 此时获得了一个 $O(nm)$ 的做法, 考虑进一步优化. 发现递推式只与 $G_i$ 和 $G_{i-1}$ 有关, 考虑能否推导出一个新的二者的关系. 我们不选择推导 $G(j)$, $G(j-1)$ 和 $G(j-2)$ 的关系显然是因为三元需要额外的两个关系, 更难以找到. 既然我们想在 $i$ 一维移动量尽量的少, 不妨考虑以 $j$ 为拓扑序 Dp. 发现 $G_i$ 随 $j$ 单调不增, 考虑 $j$ 从大到小转移, 可以使式子中尽量出现加号. 推导 $g_{i, j-1}$ 满足的式子, 分类讨论 $p_j$ 与 $j$ 的关系. - $p_j = j

将 j 删去, 方案数为 g_{i-1, j-1}.

故有

g_{i, j-1} = g_{i-1, j-1} + g_{i, j}

发现两个递推式共与 g_{i, j}, g_{i, j-1}, g_{i-1, j-1} 和 g_{i-1, j-2} 有关, 不妨改写 G_{i-1} 的下标, 全部减 1. 设 p_i = g_{n, i}, q_i = g_{n-1, i-1}, 有

\begin{aligned} p_i &= (i-1)q_{i-1} + (n-i)q_i \\ p_{i-1} &= p_i + q_i \end{aligned}

发现两个式子中 i-1 项都只出现了一种, 故将式子改写为从 i 转移到 i-1 的形式.

\begin{aligned} p_{i-1} &= p_i + q_i \\ q_{i-1} &= \frac{p_i-(n-i)q_i}{i-1} \end{aligned}

其中 p_n = f_n, q_n = f_{n-1}, 答案为 p_m.

f_i = (i-1)(f_{i-2}+f_{i-1})

其中 f_0 = 1, f_1 = 0.

# 线性空间交并互转 以模 2 意义为例, 后文省略等价符号后的对 2 取模. 设线性空间的维度为 $d$. 对于一组线性基 $\mathcal P$, 考虑一组新的线性基 $\mathcal Q$, 满足对于一个向量 $\vec x$, $\vec x \in \mathcal P \Leftrightarrow \forall \vec y \in \mathcal Q, \vec x \cdot \vec y \equiv 0$. 首先先将 $\mathcal P$ 消元成上三角矩阵. 称一行包含了一列当且仅当行列的交点为 1, 称一行的主元是这一行包含的列中编号最小的列. 由于是上三角矩阵, 显然每一行的主元互不相同. 考虑将 $\mathcal P$ 视为一个高斯消元的矩阵, 限定了若干个未知数异或和为 0. 显然任意一组非主元的值可以唯一确定所有主元的值, 则解有 $2^{d - | \mathcal P |}$ 个. $\mathcal Q$ 应当包含且仅包含这些解, 故 $| \mathcal Q | = d - | \mathcal P |$. 考虑如何构造任意一个合法的 $\mathcal Q$. 枚举每一个不是任何一行的主元的列, 钦定这一位为 1, 且所有包含了这一列的行的主元对应的位都为 1, 否则为 0, 则显然这样构造出的一个向量 $\vec y$ 满足 $\vec x \in \mathcal P \Rightarrow \vec x \cdot \vec y \in \{0, 2\} \Rightarrow \vec x \cdot \vec y \equiv 0$, 且构造出的 $d - | \mathcal P |$ 个向量线性无关 (每个向量编号最大的为 1 的位互不相同). 现在我们得到了一个合法的 $\mathcal Q$, 显然将其消为上三角矩阵后便是唯一的 $\mathcal Q$. 故可得 $\mathcal P$ 与 $\mathcal Q$ 一一对应, 称这样的 $\mathcal Q$ 为 $\mathcal P$ 的正交变换. 回到标题, 我们希望将线性空间的交转化为线性空间的并, 这样合并两个线性空间就只需线性基合并. 显然有 $\vec x \in \mathcal P_1 \land \vec x \in \mathcal P_2 \Leftrightarrow \forall \vec y \in \mathcal Q_1 \cup \mathcal Q_2, \vec x \cdot \vec y \equiv 0$. 故对于 $\mathcal P_1$ 和 $\mathcal P_2$ 取交等价于对 $\mathcal Q_1$ 和 $\mathcal Q_2$ 取并. # 决策单调性 后以 最优决策点是每一行的最小值 为例, 相同时取编号最小. ## 满足决策单调性的矩阵 - 单调矩阵. 单纯的满足决策单调性, 没有好的判定条件. - 完全单调矩阵. 每个子矩阵都满足决策单调性, 一个判定条件是满足四边形不等式, 即 $A_{i_1, j_1} + A_{i_2, j_2} \le A_{i_1, j_2} + A_{i_2, j_1} \space (i_1 < i_2, j_1 < j_2)$. <details><summary>Proof</summary> > 根据四边形不等式得到 $A_{i_1, j_1} \le A_{i_1, j_2}$ 或 $A_{i_2, j_2} < A_{i_2, j_1}$. 考虑 $i_1, i_2$ 与 $j_1, j_2$ 对应的子矩阵, 假设前者成立, 则 $i_1$ 行最优决策为 $j_1$, 假设后者成立, 则 $i_2$ 行最优决策为 $j_2$. 故这个子矩阵满足决策单调性, 进而所有 $2*2$ 的子矩阵都满足决策单调性. 考虑所有子矩阵, 假设其不满足决策单调性, 找到任意不满足决策单调性的行二元组, 取出分别的最优决策对应的两列, 则这个 $2*2$ 的子矩阵不满足决策单调性, 故矛盾. </details> 称满足四边形不等式的矩阵为 monge 矩阵. 事实上 monge 矩阵有更宽松的判定条件, 即 $A_{i, j} + A_{i+1, j+1} \le A_{i, j+1} + A_{i+1, j}$, 不妨称之为弱四边形不等式, 其等价于四边形不等式. <details><summary>Proof</summary> > 将四边形不等式变形为 $A_{i_2, j_2} - A_{i_1, j_2} - A_{i_2, j_1} + A_{i_1, j_1} \le 0$. 观察到若将 $A_{i, j}$ 看作某个矩阵 $B_{i, j}$ 从当前格子到左上角的前缀和, 则相当于对于 $B$ 的任意的连续子矩形的和不超过 0. 显然等价于 $B_{i, j} \le 0$, 故四边形不等式等价于弱四边形不等式. </details> ## 单调矩阵和完全单调矩阵满足的性质 - monge 矩阵是完全单调矩阵, 完全单调矩阵是单调矩阵. - 每行都相等的矩阵和每列都相等的矩阵是 monge 矩阵. - 单调矩阵的转置依旧是单调矩阵, 完全单调矩阵的转置依旧是完全单调矩阵. - monge 矩阵的线性组合依旧是 monge 矩阵. ## 区间上的决策单调性 定义一个区间的贡献为 $w(i, j) \space (i \le j)$. 判断 $w(i, j)$ 满足四边形不等式只需考虑定义域内的位置即可, 也即 $i_1 < i_2 < j_1 < j_2$, 也即所谓的 "交叉小于包含". <details><summary>Proof</summary> > 将四边形不等式弱化为弱四边形不等式再考虑. > > 将 $i > j$ 的位置补全, 值为 $(i-j)^2 M$, 其中 $M$ 大于等于 $w(i, j) \space (i \le j)$ 中的所有数的绝对值, 以及任意两个数的和的绝对值 (即充分大). > > 若四边形不等式中取的四个位置均是 $i > j$ 的. 弱四边形不等式等价于 $2(i-j)^2 \le (i-j-1)^2 + (i-j+1)^2$. 左侧加上 $2(i-j)^2$, 右侧加上 $2(i-j)^2-2 = 2(i-j-1)(i-j+1)$, 得到左右均为 $4(i-j)^2$. 故成立. > > 若三个位置是 $i > j$ 的, 显然只可能 $i = j+1$. 弱四边形不等式等价于 $2M \le 4M + A_{i, i}$. 显然成立. > > 若一个位置是 $i > j$ 的, 显然只可能 $i = j$. 弱四边形不等式等价于 $A_{i, i} + A_{i+1, i+1} \le M + A_{i, i+1}$. 显然成立. </details> 若 $w(i, j)$ 形如 $F(j-i)$ 的形式, 其中 $F$ 为下凸函数, 则 $w(i, j)$ 满足四边形不等式. 由此可以得到一个推论, $\min+$ 卷积中若有一侧为下凸函数, 则另一侧满足决策单调性. <details><summary>Proof</summary> > 考虑弱四边形不等式, 只需证明 $F(j-i) + F((j+1)-(i+1)) \le F(j-(i+1)) + F((j+1)-i)$ 即可. 上式化为 $2F(j-i) \le F(j-i-1) + F(j-i+1)$, 根据下凸函数的定义显然成立. > > 设 $\min+$ 卷积的两个函数为 $f$ 和 $g$, 其中 $g$ 下凸. 构造矩阵 $A_{i, j} = f_j + g_{i-j}$, 显然 $A$ 为一个每列相等的矩阵加上 $C_{i, j} = g_{j-i}$ 的转置, 故 $A$ 满足决策单调性, 推论得证. </details> 区间问题上满足决策单调性的函数: 上文中的 $j-i$ 复合下凸函数和下凸函数的 $\min+$ 卷积, 被区间 $[i, j]$ 包含的关键区间个数 (如逆序对数, 颜色数), $\frac{a_i}{b_j}$ 其中 $a$ 和 $b$ 分别单调不降. ## monge 矩阵最短路 考虑 Dp 方程 $f_{i, t} = \min_{j<i} \{f_{j, t-1} + w(j+1, i)\}$, 相当于求从 1 出发到每个点走 $t$ 步的单源最短路. 假设 $w(i, j)$ 满足四边形不等式, 也即 monge 矩阵. $f_{i, t}$ 关于 $t$ 是下凸的. 故若只需求解一个 $f_{i, t}$ 的值, 直接 wqs 二分即可. <details><summary>Proof</summary> > 只需证明 $2f_{n, t} \le f_{n, t-1} + f_{n, t+1}$ 即可. 考虑从 1 到 $n$ 的两条长度分别为 $t-1$ 和 $t+1$ 的路径, 分别称之 $P$ 和 $Q$, 按编号从小到大写下两条路径经过的结点, 以小写字母区分这个结点由哪条路径经过, 都经过同一个点时认为 $p$ 在 $q$ 之前, 则得到一个长度为 $2t$, 字符集为 $\{p, q\}$ 的序列, 其中有 $t-1$ 个 $p$ 和 $t+1$ 个 $q$. > > 显然序列中存在一个前缀使得 $q$ 的数量比 $p$ 多 2, 比如整个序列作为前缀就满足. 找到第一个这样的前缀 $i$, 则 $i-1$ 与 $i$ 都是 $q$. 若 $i$ 是 $p$, 则 $i-1$ 的前缀中 $q$ 的数量比 $p$ 多 3, 而空串 $q$ 的数量与 $p$ 的数量相等, 必然前面还有一个位置是多 2, 矛盾; 若 $i-1$ 是 $p$, 则 $i-2$ 的前缀 $q$ 比 $p$ 多 2, 矛盾. > > 设 $i-1$ 之前的最靠近 $i-1$ 的 $p$ 的下标为 $j$, $i$ 之后的最靠近 $i$ 的 $p$ 的下标为 $k$. 将 $i$ 以及 $i$ 之后的所有字符翻转 ($p$ 变 $q$, $q$ 变 $p$). 若 $i-1$ 和 $j$ 对应的位置相同则变化量为 0, 否则两条路径的权值总和的变化量为 $-w(j, k) - w(i-1, i) + w(j, i) + w(i-1, k)$, 需要将式子中的下标替换为对应的位置, 显然四个位置都不同, 由于四边形不等式, 变化量一定非正. 故一定存在两条长度为 $t$ 的路径和不超过长度为 $t-1$ 的路径与长度为 $t+1$ 的路径的和. </details> ## 求解决策单调性的算法 - 分治. 只需满足单调矩阵即可, 但是是离线的. - 二分栈. 需要满足完全单调矩阵, 但是是在线的. - SMAWK 算法. 需要满足完全单调矩阵, 而且是离线的, 但是不带 log. 算法流程是先递归算偶数行的最优决策点, 然后奇数行的就可以 $O(n+m)$ 算. 发现这样是 $O(n + m \log n)$ 的, 于是每次先用类似二分栈的方式找到可能用到的 $n$ 列, 则将 $m$ 缩减到了 $n$, 每次 $O(n)$ 计算, 复杂度 $O(n)$. # 单点匹配区间问题 给定一个长度为 $n$ 的整数序列 $a_i$ 与一个长度为 $n+1$ 的区间序列 $b_i$. 定义 $a_i$ 能匹配 $b_j$ 当且仅当 $a_i \in b_j$, 求有多少个整数 $x$ 满足将 $x$ 加入 $a$ 序列中后 $a_i$ 能与 $b_i$ 形成完美匹配. $1 \le n \le 3 \times 10^5$, [原题](https://www.luogu.com.cn/problem/CF1718D). --- 考虑 Hall 定理. 假设有一个大小为 $p$ 的区间集合, 所有区间的并为 $S$, 设 $q = \sum_{i} [a_i \in S]$. 显然 $p > q + 1$ 时无解, $p = q + 1$ 时需要 $x \in S$, 否则没有限制. 显然有限制的都是 $p > q$ 的情况, 注意到若 $S$ 不连续, 则 $S$ 中必然有连续的一段满足 $p > q$, 且这个限制更严, 故只需考虑 $S$ 为区间的情况. 又可以立即推出结论, 若有解则可行解一定构成一个区间, 故只需考虑如何求出区间的上下界. 上面的推导是显然的, 重点在下面求上下界的方法. 假设给定了 $x$, 考虑如何判断是否合法. 固然可以用 Hall 定理写线段树直接判, 但我们希望有一种更有拓展性的方法. 考虑从小到大为每个 $a_i$ 寻找尚未被匹配的右端点最小的区间来匹配, 现证明其正确性. 显然对于所有左端点不超过当前的 $a_i$ 的区间, 它们的左端点是等价的, 故现在就把右端点限制最严的区间匹配掉肯定不劣. 现在并没有这个 $x$, 但假设依旧做上述的贪心, 若存在一个 $a_i$ 找不到匹配则无解, 故现在所有的 $a_i$ 都找到了匹配, 故唯一地剩下了一个区间没有被匹配. 我们声称这个区间的右端点就是可行解构成区间的上界, 现证明其正确性. 假设还有一个可行解 $x$ 大于这个区间的右端点 $r$, 那么这个区间一定会匹配上一个 $a_i$. 考虑 $a_i$ 在贪心算法中匹配的区间 $r'$, 一定有 $r' \le r$. 故有 $x > r \ge r'$, $x$ 无法匹配 $r'$ 这个区间. 故只能继续尝试增广, 继续考虑 $r'$ 现在匹配的 $a_{i'}$, 则无论考虑多少层 $x$ 都无法成功增广. 故 $x$ 并非可行解. 类似地, 可以用同样的方法来求得下界. 显然, 当且仅当上界小于下界时无解. 考虑对于求解上界的实现方式. 固然可以对 $a_i$ 升序排序, 对 $b_i$ 的左端点升序排序, 每次往小根堆中加入左端点不超过当前 $a_i$ 的区间的右端点, 然后不断弹堆直到右端点不小于 $a_i$ 为止. [具体代码](https://codeforces.com/contest/1718/submission/312522470) 但也可以对 $a_i$ 升序排序, 对 $b_i$ 的右端点升序排序, 每次往 ``set`` 中加入不超过当前右端点的 $a_i$, 然后在 ``set`` 中找到当前左端点的后继进行匹配. [具体代码](https://codeforces.com/contest/1718/submission/312522571) 时间复杂度均为 $O(n \log n)$, 但前者常数较小. # 多项式前缀积系数 给定 $n$ 个一次多项式 $f_j$ 和 $n$ 个一次多项式 $g_j$, 对每个 $1 \le i \le n$ 求 $[x^m] \prod_{j=1}^i \frac{f_j}{g_j}$. $1 \le n, m \le 10^5$. [例](http://oj.daimayuan.top/contest/327/problem/3032) --- 先考虑 $g_j = 1$ 怎么做. 发现如果只要求全局积的 $m$ 次系数, 也需要用分治 NTT, 故对于每个 $i$ 都求也考虑分治 NTT. 考虑现在分治区间为 $[l, r]$, 并给定了多项式 $H$ 和非负整数 $k$, 要对每个 $l \le i \le r$ 求 $[x^k] H \prod_{j=l}^i f_j$. 不妨设 $len=r-l+1$. 注意到即使是全集, 最高次数也只有 $len$, 故只需考虑 $H$ 的 $k-len$ 次系数到 $k$ 次系数即可. 不妨平移 $H$ 和 $k$, 则 $H$ 只有 $O(len)$ 项, $k$ 的规模也是 $O(len)$ 的. 故递归到子区间的复杂度为 $O(len \log len)$, 有复杂度 $T(n) = 2T(\frac{n}{2}) + O(n \log n) = O(n \log^2 n)$. 现在需要考虑 $g_j \neq 1$, 则可以把一开始的 $H$ 设为 $\prod_{j=1}^m \frac{1}{g_j}$, 往左边递归时乘上右边的 $g_j$ 的乘积, 往右边递归时乘上左边的 $f_j$ 的乘积, 则复杂度依旧为 $O(n \log^2 n)$. 实现上, 一次递归中的两个卷积可以只用 5 次 NTT, 即 $H$ 无需被反复 NTT. 并且预处理每个分治区间的 $f_j$ 与 $g_j$ 而不是每次需要用时再重新分治 NTT, 会将运行时间变为原来的一半一下, 尽管空间复杂度变为 $O(n \log n)$. # 一类特殊格路计数问题 求从 $O(0, 0)$ 走到 $P(n, m)$, 每次可以向 $x$ 轴正方向或 $y$ 轴正方向移动一单位, 不能碰到 $l_1:y=x-a$ 和 $l_2:y=x+b$ 的方案数. [例](https://www.luogu.com.cn/problem/P3266) $0 \le n, m \le 10^7$, $a, b \ge 1$. --- 下设 $F(O, P)$ 表示从 $O$ 走到 $P$, 不考虑其他任何限制的方案数. 注意到当 $b=\infty$ 时, 就可以用经典的容斥求解. 经典做法是将 $P$ 沿 $l_1$ 对称得到 $S$, 计算 $F(O, S)$, 即为从 $O$ 走到 $P$ 且碰到过 $l_1$ 的方案数. 考虑拓展这个容斥. 不难想到将 $P$ 沿 $l_2$ 对称得到 $T$, 考虑 $F(O, P) - F(O, S) - F(O, T)$ 是否为正确答案. 发现若存在一条格路既碰到过 $l_1$ 也碰到过 $l_2$, 则会被减去两次, 故应当将这部分加回来. 对称次数不超过 1 的点已经被我们发掘完了, 考虑对称两次的点. 将 $S$ 沿 $l_2$ 对称得到 $S'$, 考虑 $F(O, S')$ 的意义. 首先从 $O$ 到 $S$ 的路径本身就蕴含了碰到过 $l_1$, 那么再对称一次就变成了依次碰到过 $l_2$ 和 $l_1$. 通过画图不难得出这一结论. 故类似的将 $T$ 沿 $l_1$ 对称得到 $T'$, $F(O, T')$ 为从 $O$ 走到 $P$ 且依次碰到过 $l_1$ 和 $l_2$ 的方案数. 现在重新考虑 $F(O, P) - F(O, S) - F(O, T) + F(O, S') + F(O, T')$ 是否为正确答案, 发现若一条格路依次碰到了 $l_1$, $l_2$ 和 $l_1$, 则会被减去两次加上两次, 故还应当将这部分减去. 不难发现, 只要我们无限的对称 $S'$, $T'$, 和它们对称得到的一系列新点, 无限的延长这个式子, 就能得到正确答案. 即 $F(O, P) - F(O, S) - F(O, T) + F(O, S') + F(O, T') - F(O, S'') - F(O, T'') + F(O, S''') + F(O, T''') \dots$. 其中 $S''$, $T''$, $S'''$ 和 $T'''$ 的意义不言自明. 注意到一个 $F(O, P)$ 可以通过 $O(n+m)$ 预处理阶乘后 $O(1)$ 求出, 考虑这个式子非 0 的项数. 注意到 $F$ 中第一项均为 $O$, 第二项均在直线 $x+y=n+m$ 上, 且分别考虑 $S$ 一簇点和 $T$ 一簇点, 其到 $y=x+ {b-a \over 2}$ 的距离单调递增, 而只有 $P_x, P_y \ge 0$ 的 $P$ 才非 0, 故至多有 $O(n+m)$ 个非 0 项. 两簇点的坐标都容易通过递推求出, 复杂度 $O(n+m)$. # 类欧几里得 求 $$\sum_{i=1}^n \lfloor {ai+b \over c} \rfloor.$$ $1 \le n, a, b, c \le 10^{18}$, $0 \le a, b < c$. --- 思路万千不如考场手推的灵光一现. 设 $g = \lfloor {an + b \over c} \rfloor \le n$. $$ \begin{aligned} Ans &= \sum_{i=1}^n \sum_{j=1}^g [\lfloor {ai+b \over c} \rfloor \ge j] \\ &= \sum_{j=1}^g \sum_{i=1}^n [\lfloor {ai+b \over c} \rfloor \ge j] \end{aligned} $$ 有 $$ \begin{aligned} [\lfloor {ai+b \over c} \rfloor \ge j] &= [ai+b \ge cj] \\ &= [i \ge \lceil {cj-b \over a} \rceil] \end{aligned} $$ 故 $$ Ans = \sum_{j=1}^g \sum_{i=1}^n [i \ge \lceil {cj-b \over a} \rceil] $$ 我们希望 $$ \sum_{i=1}^n [i \ge \lceil {cj-b \over a} \rceil] = n - \lceil {cj-b \over a} \rceil + 1 $$ 则需要满足 $$ 1 \le \lceil {cj-b \over a} \rceil \le n $$ 有 $$ \begin{aligned} [\lceil {cj-b \over a} \rceil \ge 1] &= [\lfloor {cj-b+a-1 \over a} \rfloor \ge 1] \\ &= [cj-b+a-1 \ge a] \\ &= [cj > b] \\ \\ [\lceil {cj-b \over a} \rceil \le n] &= [cj-b \le an] \\ &= [j \le {an+b \over c}] \\ &= [j \le \lfloor {an + b \over c} \rfloor = g] \end{aligned} $$ 后者显然满足, 前者只需满足 $b < c$ 即可. 故当 $b < c$ 时, $$ \begin{aligned} Ans &= \sum_{j=1}^g (n - \lceil {cj-b \over a} \rceil + 1) \\ &= g(n+1) - \sum_{j=1}^g \lceil {cj-b \over a} \rceil \end{aligned} $$ 设 $c = ka+r$, 有 $$ \begin{aligned} Ans &= g(n+1) - \sum_{j=1}^g \lceil {kaj+rj-b \over a} \rceil \\ &= g(n+1) - \sum_{j=1}^g (kj + \lceil {rj-b \over a} \rceil) \\ &= g(n+1) - {g(g+1) \over 2}k - \sum_{j=1}^g \lceil {rj-b \over a} \rceil \\ &= g(n+1) - {g(g+1) \over 2}k - \sum_{j=1}^g \lfloor {rj+(a-b-1) \over a} \rfloor \end{aligned} $$ 故将 $(a, c)$ 的问题 $O(1)$ 地转化为了 $(c \bmod a, a)$ 的问题, 且当 $a=0$ 时答案为 0, 故可以 $O(\log c)$ 解决. 注意到两个小细节: $g(n+1)$ 有可能超过 ``long long`` 范围, 则答案需要使用 ``__int128_t``; 式子只有在 $b < c$ 时才成立, 故递归调用 $b' = a-b-1$ 前, 需要将 $b'$ 移动到 $[0, a)$ 范围, 同时给答案加上 $g$ 的某个整数倍即可.