跳至主要內容
[Medium] QOJ9539 Disrupting Communications

简要题意

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

xiezheyuan2025/6/7...大约 6 分钟做题笔记dp树形dp重链剖分换根
Slope Trick 优化 DP

消歧义

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

Slope Trick 基础

斜率表示法

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

  • 对于二维 dp 的每一行，都可以看成关于列的一个函数，并且它具有凹性或凸性。
  • 每一行的函数，都可以看成是一个连续的分段函数，每一段是一个一次函数。
xiezheyuan2025/6/2...大约 5 分钟学习新知dpSlope Trick
集合幂级数与子图计数

集合幂级数概论

集合幂级数

定义

设全集 U={1,2,⋯ ,n},U={S∣S⊆U}U=\{1,2,\cdots,n\},\mathbf{U}=\{S\mid S\subseteq U\}。定义 UU 上的集合幂级数 f:U→Rf:\mathbf{U}\to R，其中 RR 为一交换环。令 fSf_S 表示 ff 上 SS 的像。

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

  • h=f+gh=f+g，其中 h:U→Rh:\mathbf{U}\to R 且 hS=fS+gSh_S=f_S+g_S。类似的可以定义 h=f−gh=f-g。
  • h=kfh=kf，其中 h:U→R,k∈Rh:\mathbf{U}\to R,k\in R，其中 hS=kfSh_S=kf_S，类似的可以定义 h=−fh=-f。
  • h=f×gh=f\times g，其中 h:U→Rh:\mathbf{U}\to R 且 hS=∑T⊆SfTgS\Th_S=\sum\limits_{T\subseteq S} f_Tg_{S\backslash T}，即 f,gf,g 的子集卷积（不交并卷积）。
    为了方便之后的表述，我们定义 S⊔TS\sqcup T 表示 S,TS,T 的不交并（若 S∩T=∅S\cap T=\varnothing，则 S⊔T=S∪TS\sqcup T=S\cup T，否则是非法的）。
  • h=f∗gh=f\ast g，其中 h:U→Rh:\mathbf{U}\to R 且 hS=∑A∪B=SfAgBh_S=\sum\limits_{A\cup B=S} f_Ag_B，即 f,gf,g 的集合并卷积（OR 卷积）。
  • h=f∘gh=f\circ g，其中 h:U→Rh:\mathbf{U}\to R 且 hS=fS⋅gSh_S=f_S\cdot g_S，即 f,gf,g 的逐项积。

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

xiezheyuan2025/5/20...大约 37 分钟学习新知生成函数集合幂级数图论计数容斥dp组合计数线性基
[Medium] P12107 [NWRRC2024] Capybara Cozy Carnival

简要题意

给定一个 nn 个点的弦图，从点 11 开始，环上点依次为 2,3,⋯ ,n2,3,\cdots,n。另有 mm 条弦，第 ii 条弦为 (ui,vi)(u_i,v_i)，保证 1≤ui<vi≤n1\leq u_i<v_i\leq n 且无重边，且两两弦不相交（端点处相交除外）。

xiezheyuan2025/4/24...大约 6 分钟做题笔记dp矩阵加速分治组合计数
[Medium-Hard] AT_abc386_g [ABC386G] Many MST

简要题意

计算对于所有 nn 个点的无向完全图（边权位于 [1,m]∩Z[1,m]\cap\mathbb{Z}）的最小生成树边权和之和。答案对 998,244,353998,244,353 取模。

xiezheyuan2025/3/22...大约 6 分钟做题笔记组合计数容斥生成树dp图论计数
[Hard] P11714 [清华集训 2014] 主旋律

简要题意

给定一个 nn 个点 mm 条边的有向图，你需要求出其的边集数，使得断掉边集中的所有边后，整张图强联通。答案对 109+710^9+7 取模。

xiezheyuan2025/2/13...大约 11 分钟做题笔记dp状压dp图论计数连通性问题组合计数容斥子集反演
[Medium] CF1895F Fancy Arrays

简要题意

给定参数 x,kx,k，定义一个长度为 nn 的序列 aa 是好的，当且仅当满足下面所有条件：

xiezheyuan2025/2/10...大约 5 分钟做题笔记组合计数dp容斥
[Easy] CF1923E Count Paths

虚树 + 简单换根 dp。

简要题意

给定一个 nn 个点的树，点 ii 有点权 cic_i，计算满足下列所有条件的路径 (u,v)(u,v) 数量：

xiezheyuan2025/2/4...大约 5 分钟做题笔记dp树形dp容斥换根
[Medium] CF2026F Bermart Ice Cream

简要题意

你需要维护一些冰淇淋店，初始时只有一家店，编号为 11，不出售任何冰淇淋。有 nn 次操作，支持：

xiezheyuan2025/1/29...大约 8 分钟做题笔记dp线段树分治对顶栈
[Easy-Medium] CF2042F Two Subarrays

不是，都除夕了，CF 还卡我常数，没有武德！

简要题意

给定两个长度为 nn 的序列 a,ba,b，有 mm 次操作，支持：

xiezheyuan2025/1/28...大约 7 分钟做题笔记dp线段树动态dp