摘要：
后续： 半在线子集卷积，逆子集卷积 特殊的二进制卷积 k-fwt RT，主要内容涉及有 高维前缀和（子集DP），高维后缀和，高维差分，快速沃尔什变换，子集卷积。 参考资料： link1 link2 知识点合集 高维前缀和 用于求解 \(f(S)=\sum_{T\subseteq S}g(T)\)。 阅读全文
posted @ 2024-11-04 08:59
spdarkle
阅读(72)
评论(0)
推荐(0)
摘要：
RT，本文探讨一些简单的分块应用，不会涉及太高深的分块知识。 PS:如有错误请不吝赐教，不胜感激 PS:代码仅供参考 PS:更新了Ynoi杂题记 分块 友情提醒：#include<cmath> 望月悲叹的最初分块 分块，优雅的暴力 分块也是同线段树等结构一样，维护区间操作的，不同于线段树和树状数组的 阅读全文
posted @ 2023-01-22 00:05
spdarkle
阅读(120)
评论(0)
推荐(0)
摘要：
# 二项式系数 ## 定义 首先定义阶乘： 对于任意$n\in\mathbb{N}$，定义$n$的阶乘$n!=n(n-1)……1=\prod_{i=1}^n i$ 再来定义二项式系数(组合数) 我们用符号$n\choose k$表示二项式系数，其中$n$为上标，$k$为下标。 1. 数学定义： $$ 阅读全文
posted @ 2022-12-06 17:22
spdarkle
阅读(1433)
评论(0)
推荐(1)
摘要：
莫比乌斯反演 数论函数 列举几个常见数论函数 $\varphi(n)$,欧拉函数，表示$1\sim n$中与$n$互质的数的个数 $d(n)$，表示$n$的约数个数，具体设$n=p_1^{c_1}p_2^{c_2}……p_m^{c_m}(p_1,p_2……都是质数)$,则$d(n)=\prod_{i 阅读全文
posted @ 2022-11-30 22:42
spdarkle
阅读(100)
评论(0)
推荐(0)
摘要：
莫队 贴一个神仙博客：莫队全家桶 莫队算法是对询问进行分块的一种算法，其本质是对暴力的优化。 这个算法主要是解决区间操作的，适用于求解那种区间$[l,r]$可以快速支持区间的端点移动$+1,-1$的问题，也是充分利用已知信息，避免重复计算的典范 莫队算法核心思想就是：对于所有查询的区间，通过合理的排 阅读全文
posted @ 2022-11-30 22:41
spdarkle
阅读(87)
评论(0)
推荐(0)
该文被密码保护。 阅读全文
posted @ 2026-04-05 18:31
spdarkle
阅读(0)
评论(0)
推荐(0)
摘要：
最基础的情况是无源汇上下界可行流。 无源汇上下界可行流 找到一个流函数 \(f\)，满足 \(f(u,v)\in [low(u,v),up(u,v)]\)。 解决方案：利用网络流平衡流量。 首先全部流取下界，算出一个点的 \(d\)： \[d_u=\sum_{(u,v)}low(u ,v)-\sum 阅读全文
posted @ 2026-04-05 16:45
spdarkle
阅读(7)
评论(0)
推荐(0)
摘要：
原始对偶算法 我们是只会背结论的不求甚解的好家伙 是一种费用流算法，其本质目的是将 spfa 优化为 dijkstra，可以解决没有负环的最小费用流问题。 下面全部假定为最小费用流。 流程： 预跑一次 spfa，设得到的最短路数组为 \(h\)。 跑 dijkstra，将 \(u\to v\) 边权 阅读全文
posted @ 2026-04-05 16:17
spdarkle
阅读(9)
评论(0)
推荐(0)
摘要：
挑几道有意思的题目。 P14212 设 \(w(l,r)\) 为子串 \([l,r]\) 能匹配上前后缀的串的最小代价。 拼接问题显然考虑DP，设 \(dp_{i}\) 表示 \([1,i]\) 的最小总代价。 有： \[dp_{i}=\min_{j<i}dp_j+w(j+1,i) \]这个形式事实 阅读全文
posted @ 2026-03-28 11:31
spdarkle
阅读(15)
评论(0)
推荐(0)
摘要：
难度按CF*2500- *2900。 <=*2600基本可以独立完成。 可能不完全是构造？也有强注意力题目。 1840G2 *2500。 很小清新的概率+构造。 大义是给定一个环，这个环由若干不同数字连接而成，你不知道环的大小，最初有个指针指向某个数字，你每次可以顺时针或者逆时针转动指针任意步，交互 阅读全文
posted @ 2026-03-25 10:44
spdarkle
阅读(12)
评论(0)
推荐(0)
摘要：
一课一度的抄课件环节。 群 定义 群是一种代数系统，定义一个群 \((G,\oplus )\)，满足以下条件： $\oplus $ 是一个 满足结合律的二元运算。 \(G\) 是一个集合，存在单位元 \(e\)。 \(a\in G\implies a^{-1}\in G,a\oplus a^{-1} 阅读全文
posted @ 2026-03-17 20:54
spdarkle
阅读(15)
评论(0)
推荐(0)
摘要：
RT，设计一种数据结构，支持以下操作： 在末尾插入数字 \(k\)。 设当前加入了 \(len\) 个数字，给定 \(p,k\)，将 \([p,len]\) 全部加上 \(k\)。\(k\) 是任意整数。 查询全局最大值以及最大值第一次出现位置。 可以使用并查集维护单调栈。 实现思路：使用并查集查询 阅读全文
posted @ 2026-03-16 22:05
spdarkle
阅读(13)
评论(0)
推荐(0)
摘要：
考虑一个新的排列 \(p\) 被得到，每次操作需要满足： 如果我们对 \([l,r]\) 的 \(mid\) 处断开，说明在当前局面下 \([l,mid]\) 与 \([mid+1,r]\) 的元素集合分别与目标排列 \(p\) 的对应区间元素集合相同。 为了避免重复计数，我们钦定如下操作方式： 只 阅读全文
posted @ 2026-02-27 20:02
spdarkle
阅读(9)
评论(0)
推荐(0)
摘要：
集合幂级数运算 exp 考虑 \(g(x)=e^{f(x)}\) 的组合意义： \[g(x)=\sum_{i\ge 0}\frac{f^i(x)}{i!} \]这里的乘法是无交并，也就是常说的子集卷积。 当 \([x^0]f=0\) 时，\(i>n\) 的项为全零。 方法1 从组合意义的角度入手，有 阅读全文
posted @ 2026-02-25 21:52
spdarkle
阅读(21)
评论(0)
推荐(1)
浙公网安备 33010602011771号