摘要：
PAM 定义 我们用PAM上的一个节点代表原序列的一个本质不同回文串。 由于回文串分奇和偶两个长度，我们开两颗树分别存储奇回文串和偶回文串，不妨称之为奇树，偶树。 由于回文串前后相等，我们定义一个点对应的回文串是：一次写下从它到它这棵树的根，再从根回到它的路径上所有边的字符，定义奇树的与根相连的边上 阅读全文
posted @ 2026-02-03 09:54
spdarkle
阅读(14)
评论(0)
推荐(0)
摘要：
模型： \[dp_{i,j}=\max(dp_{i-1,j}+R(i-1,j),dp_{i,j-1}+U(i,j-1)) \]目标明确：\((0,0)\to (n,m)\)。 两个方向的贡献函数可以转化到一个方向，例如 \(U\to R\)。 将贡献函数转化为若干个区间修改的形式（唉没错就是差分）（ 阅读全文
posted @ 2026-01-27 21:19
spdarkle
阅读(18)
评论(0)
推荐(0)
摘要：
首先将区间加修改为后缀操作。 以前缀最大值为例。也就是执行区间修改操作之后维护前缀最值。 若后缀加正数，无影响。 若后缀加负数，那么被覆盖的是一段区间，可以线段树二分找到。 如果需要进行多次后缀修改操作之后再统一做前缀最大值。 可以转化为先做所有加正数的操作，然后把加负数的操作按照左端点从后往前做。 阅读全文
posted @ 2026-01-27 21:10
spdarkle
阅读(17)
评论(0)
推荐(0)
摘要：
我们知道，对于具有凸性的DP存在一种技巧叫 Slope Trick，一般指利用堆维护斜率拐点，但凸壳不止这一种表达方法，还有一些。 先来看看我们需要的操作： 加法：\(g(x)=f(x)+h(x)\)，\(h_1(x)=C,h_2(x)=kx+b,h_3(x)=|x-a|\) 平移，然后取极值——这 阅读全文
posted @ 2026-01-27 20:55
spdarkle
阅读(57)
评论(0)
推荐(1)
摘要：
P11328 贪心策略的发现的通用方法:假定最优解集合，再微调研究 很明显我们应该使用邻项交换法，假设选定了按照什么顺序参加比赛，并且参加的每一场都获得了徽章，那么考虑先操作 \(i\) 再操作 \(j\) 合法，而先操作 \(j\) 非法的条件是： \[now\le L_i,now+X_i\le 阅读全文
posted @ 2026-01-27 15:13
spdarkle
阅读(20)
评论(0)
推荐(0)
摘要：
考虑给定序列 \(a\)，求出序列 \(a\) 的最短线性递推式（在固定域 \(\mathbb{F}\) 下，通常是模意义或者实数域）。 引理：对于一个无限长的递推序列 \(a\)，若其满足线性递推且其最短递推式长度为 \(l\)，则取前 \(2l\) 项跑Berlekamp-Massey即可得到其 阅读全文
posted @ 2026-01-25 19:34
spdarkle
阅读(31)
评论(0)
推荐(0)
摘要：
以下默认小写字母 \(\mathbf{a},\mathbf{b}\) 等表示的向量是一个行向量，\(\mathbf{1}\) 表示全 \(1\) 行向量，\(\operatorname{diag(\mathbf{a})}\) 表示一个大小 \(|\mathbf{a}|\times |\mathbf{ 阅读全文
posted @ 2026-01-21 11:03
spdarkle
阅读(22)
评论(0)
推荐(0)
摘要：
零化多项式 定义： 矩阵定义 设域为 \(\mathbb{F}\)，在一个线性空间 \(\mathbb{F}^n\) 上的线性变换 \(T:V\to V\)（域为 \(\mathbb{F}\)）。 若有在域 \(\mathbb{F}\) 上的多项式 \(F(z)=\sum f_iz^i\) 满足： 阅读全文
posted @ 2026-01-21 11:02
spdarkle
阅读(24)
评论(0)
推荐(0)
摘要：
众所周知，第二类斯特林数通过二项式反演可以得到通项公式。 应用它可以得到线性计算 bell 与 fubini numbers 的方法。 先来看贝尔数。 \[\begin{aligned} Bell(n)&=\sum_{k=0}^n{n\brace k}\\ &=\sum_{k=0}^n\sum_{j 阅读全文
posted @ 2025-12-31 15:22
spdarkle
阅读(29)
评论(0)
推荐(0)
摘要：
核心思想是将无法处理的运算参量单独设为一个未知量，也就是变成维护二元组，多个未知量就是多元组，然后设置它们的合并规则进行计算。 一般而言，最终的未知量都会消去。 例如 NOI2025 集合 中，我们需要涉及到处理含 \(0\) 算式的乘除法，可以将数字表达为 \(x·0^y\) 的形式，用二元组 \ 阅读全文
posted @ 2025-12-28 14:37
spdarkle
阅读(37)
评论(0)
推荐(0)
浙公网安备 33010602011771号