博客主页 | xzy 的小屋

2025 7 月闲话合集

这一部分都是我 7 月份（中后旬）写的题的总结，如果对你有用，真是倍感荣幸。为了轻松一点，每四道题目我将放一段歌词，以供欣赏。

0x00.

给定 $n,k,p$ ，计算：
$\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor} \binom{n}{ik} \mathrm{fib}(i) \pmod{p}$
其中 $\mathrm{fib}(i)$ 表示 Fibonacci 数列，定义为 $\mathrm{fib}(0)=\color{red}\mathbf{1}\color{default}, \mathrm{fib}(1)=1, \mathrm{fib}(n)=\mathrm{fib}(n-1)+\mathrm{fib}(n-2)$ 。

$T$ 组数据， $1\leq T\leq 20,1\leq n\leq 10^{18},1\leq k\leq 2\times 10^4,1\leq p\leq 10^9,p\in\mathbb{P},k\mid p-1$ 。

xiezheyuan2025/7/31约 11487 字大约 57 分钟

2025-07-03 随笔

Minkowski 和与凸优化

在数学上，我们定义两个集合（通常是点集） $S,T$ 的 Minkowsi 和为：

xiezheyuan2025/7/3约 2847 字大约 14 分钟

OIFC 2025 NOI线下集训（二）

xiezheyuan2025/6/28约 3749 字大约 19 分钟

2025-06-26 随笔

回滚莫队

惭愧，我现在才开始学这么基础的东西。

众所周知，普通莫队之所以强悍，是因为它只需要加一个元素和删一个元素，就可以做到 $O(n\sqrt{n})$ 的优秀时间复杂度。但是存在很多问题不能同时做到加和删，那么就需要回滚莫队。

xiezheyuan2025/6/26约 1134 字大约 6 分钟

2025-06-25 随笔

基于值域预处理的快速离散对数

考虑下面一个经典题：

P11175 【模板】基于值域预处理的快速离散对数：给定质数 $p$ 和它的一个原根 $g$ ，有 $q$ 次询问，每次询问给出一个整数 $x\in [1,P)$ ，查询 $\log_g x\pmod{p}$ 的值。 $1\leq p\leq 10^9+7,1\leq q\leq 5\times 10^5$

xiezheyuan2025/6/25约 1886 字大约 9 分钟

2025-06-24 随笔

离线 O(1) 求逆元

一个很平凡的技巧，但是确实可以降低代码的常数或者复杂度。

假如我们有一个长度为 $n$ 的序列 $x_1,\cdots,x_n$ ，我们需要求 $x_1^{-1},\cdots,x_n^{-1} \pmod{p}$ ，其中 $p$ 是一个质数，不过允许离线，我们有一个 $O(\log p+n)$ 的算法。

xiezheyuan2025/6/24约 2759 字大约 14 分钟

省选国赛精选题单

AGC052B Tree Edges XOR

给定一个 $n$ 个点的无根树（保证 $n$ 为奇数），第 $i$ 条边有边权 $w_{i,1}$ 。

你可以进行任意次操作，每次操作选定一条边，并将与这条边相接的所有边的 $w_{j,1}$ 异或上这条边的 $w_{i,1}$ 。你需要将所有边的 $w_{i,1}$ 变为 $w_{i,2}$ ，求是否可以做到。

$1\leq n\leq 10^5,0\leq w_{i,1},w_{i,2} < 2^{30}$ 。

xiezheyuan2025/6/22约 6792 字大约 34 分钟

The 2024 ICPC Asia Chengdu Regional Contest (The 3rd Universal Cup. Stage 15: Chengdu)

The 2024 ICPC Asia Chengdu Regional Contest

The 3rd Universal Cup. Stage 15: Chengdu

Link

#	Problem	Coding Status	Document Status
A	Arrow a Row	Planned	Unavailable
B	Athlete Welcome Ceremony	Accepted	Finished
C	Chinese Chess	Planned	Unavailable
D	Closest Derangement	Planned	Unavailable
E	Disrupting Communications	Accepted	Finished
F	Double 11	Accepted	Planned
G	Expanding Array	Accepted	Planned
H	Friendship is Magic	Planned	Unavailable
I	Good Partitions	Accepted	Planned
J	Grand Prix of Ballance	Planned	Unavailable
K	Magical Set	Accepted	Planned
L	Recover Statistics	Accepted	Planned
M	Two Convex Holes	Planned	Unavailable

xiezheyuan2025/6/20约 791 字大约 4 分钟

The 2023 ICPC Asia Xi'an Regional Contest (The 3rd Universal Cup. Stage 9: Xi'an)

The 2023 ICPC Asia Xi'an Regional Contest

The 3rd Universal Cup. Stage 9: Xi'an

Osijek Competitive Programming Camp Fall 2024. Day 8. Xi'an Contest

Link

xiezheyuan2025/6/19约 3121 字大约 16 分钟

dbg.hpp 调试库

警告

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

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

xiezheyuan2025/6/10约 121 字小于 1 分钟

暴力多项式操作

引言

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

xiezheyuan2025/5/22约 1093 字大约 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约 7496 字大约 37 分钟

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

简要题意

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

xiezheyuan2025/5/19约 1344 字大约 7 分钟

[Hard] P5320 [BJOI2019] 勘破神机

简要题意

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

xiezheyuan2025/5/5约 1971 字大约 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$ 。