小明の雜貨鋪

本文涉及的知识点：组合数公式，古典概型，Min-Max 反演及推广，卷积优化思想，状态压缩思想与状态压缩 DP，快速数论变换 NTT，快速数论变换 NTT，快速沃尔什变换 FWT。 本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。 2024 ICPC World Finals Astana B. Bingo for the Win! Bingo 游戏，nnn 个人每人要抢 kkk 个数，主持人按随机顺序依次报数，报到每个数 [1,109][1,10^{9}][1,109] 的概率相同。已知如果有多名选手要抢某个数字，那么编号小的选手总是优先抢到。问每个人成为最后一名（其他人都抢完了但自己还没抢完）的概率。 ...

有三件物品可供选择，物品甲重量为 3，物品乙重量为 8，物品丙重量为 5。有一个背包，问选择任意件物品放入背包后，背包总重为 8 的方案数。 列出所有的可能： 选甲，选乙，选丙； 选甲，选乙，选丙； 选甲，选乙，不选丙； 选甲，不选乙，选丙； 选甲，不选乙，不选丙； 不选甲，选乙，选丙； 不选甲，选乙，不选丙； 不选甲，不选乙，选丙； 不选甲，不选乙，不选丙。 每个物品 X 都有两种状态：选 X 或不选 X，而且每个物品的状态相互独立，直接用一个式子表达： （选甲 或 不选甲）且（选乙 或 不选乙）且（选丙 或 不选丙） 这个逻辑表达式包含了上面全部八种情形。这里 且 的含义是，如果 A 且 B，那么 A 必须执行，B 也必须执行。 把物品重量一并列入上面的表达式中： （重量为 3 或 重量为 0）且（重量为 8 或 重量为 0）且（重量为 5 或 重量为 0） 这样写虽然能表达所有的情况，但文字太多还是太麻烦了。希望选取一些数学符号，完全转化为数学表达式。 观察这个式子： （重量为 3 或 重量为 0）且（重量为 8 或 重量为...

本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。 我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」 可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。

想必读者第一次听说懒标记 (LazyTag) 是在线段树区间修改中，其实懒标记思想在图论及更多方面中也有应用。其核心思想在于「延迟计算 」，即通过标记的方式记录对某个有相同性质的对象（如线段树的区间、图中的连通块等）的 整体操作，而不是立即操作每个元素。 一、并查集维护连通性——The 2025 ICPC Latin America Championship D. Dangerous City Description 给定无向图，有点权。路径权值定义为路径上（含端点）所有点权最大值，定义 f(u,v)f(u, v)f(u,v) 为所有 uuu 到 vvv 路径中值最小的一条。对每个 uuu 求 su=∑v=1nf(u,v)s_u = \displaystyle \sum_{v=1}^n f(u, v)su​=v=1∑n​f(u,v)。n,m⩽3⋅105n,m \leqslant 3\cdot 10^{5}n,m⩽3⋅105。 Notes 将点权转化为边权，设 u−vu-vu−v 的边权 w=max⁡{wu,wv}w=\max\lbrace w_{u},w_{v}...