博客主页 | xzy 的小屋

dbg.hpp 调试库

警告

本页面在黑暗模式下显示不佳，请切换到明亮模式。

dbg.hpp 是我们封装的调试库，用于在 OI / ACM 等算法竞赛中快速调试代码。目前部署在 Github Gist 上。

xiezheyuan2025/6/10...小于 1 分钟

[Medium] QOJ9539 Disrupting Communications

简要题意

给定一个 $n$ 个点的树，有 $q$ 次询问，每次询问给出 $u,v$ ，你需要求出树上有多少个连通块，使得该连通块与路径 $(u,v)$ 无交。答案对 $998,244,353$ 取模。

xiezheyuan2025/6/7...大约 6 分钟

[Easy] QOJ9543 Good Partitions

简要题意

给定一个长度为 $n$ 的序列 $a$ 。

xiezheyuan2025/6/7...大约 3 分钟

Slope Trick 优化 DP

消歧义

本文讲述的不是斜率优化（Convex Hull Trick）而是 Slope Trick。

Slope Trick 基础

斜率表示法

Slope Trick（无标准译名，与斜率优化不同）通常用于优化一类二维 dp，满足：

对于二维 dp 的每一行，都可以看成关于列的一个函数，并且它具有凹性或凸性。
每一行的函数，都可以看成是一个连续的分段函数，每一段是一个一次函数。

xiezheyuan2025/6/2...大约 5 分钟

暴力多项式操作

引言

本文将介绍如何 $O(n^2)$ 计算多项式求逆、取 $\exp$ 、取 $\ln$ 。

xiezheyuan2025/5/22...大约 5 分钟

集合幂级数与子图计数

集合幂级数概论

集合幂级数

定义

设全集 $U=\{1,2,\cdots,n\},\mathbf{U}=\{S\mid S\subseteq U\}$ 。定义 $U$ 上的集合幂级数 $f:\mathbf{U}\to R$ ，其中 $R$ 为一交换环。令 $f_S$ 表示 $f$ 上 $S$ 的像。

若 $f:\mathbf{U}\to R,g:\mathbf{U}\to R$ ，则定义：

$h=f+g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=f_S+g_S$ 。类似的可以定义 $h=f-g$ 。
$h=kf$ ，其中 $h:\mathbf{U}\to R,k\in R$ ，其中 $h_S=kf_S$ ，类似的可以定义 $h=-f$ 。
$h=f\times g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=\sum\limits_{T\subseteq S} f_Tg_{S\backslash T}$ ，即 $f,g$ 的子集卷积（不交并卷积）。
为了方便之后的表述，我们定义 $S\sqcup T$ 表示 $S,T$ 的不交并（若 $S\cap T=\varnothing$ ，则 $S\sqcup T=S\cup T$ ，否则是非法的）。
$h=f\ast g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=\sum\limits_{A\cup B=S} f_Ag_B$ ，即 $f,g$ 的集合并卷积（OR 卷积）。
$h=f\circ g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=f_S\cdot g_S$ ，即 $f,g$ 的逐项积。

另外还可以定义集合交卷积（AND 卷积）、集合对称差卷积（XOR 卷积）等，它们在一般的 FMT/FWT 技术中是十分重要的，不过它们在集合幂级数理论中应用较少，故不再赘述。

xiezheyuan2025/5/20...大约 37 分钟

[Medium] P8215 [THUPC 2022 初赛] 分组作业

简要题意

有 $2n$ 个人，第 $2k-1$ 个人和第 $2k$ 个人为一组（ $k\in\mathbb{Z}_+$ ）。

xiezheyuan2025/5/19...大约 7 分钟

[Hard] P5320 [BJOI2019] 勘破神机

简要题意

给定 $m$ ，记 $f(n)$ 表示用 $1\times 2$ 的骨牌覆盖 $m\times n$ 的网格的方案数。给定 $l,r,k$ ，你需要求：

xiezheyuan2025/5/5...大约 10 分钟

生成函数，卡特兰数，伯努利数与斯特林数总结

生成函数

生成函数绪论

对于函数 $f:\mathbb{N}\to\mathbb{C}$ ，定义其普通生成函数（OGF） $\mathbf{F}(z)=\sum_{i\geq 0} f(i)z^i$ ，指数生成函数（EGF） $\hat{\mathbf{F}(z)}=\sum_{i\geq 0} \frac{f(i)}{i!}z^i$ 。