wjyppm's Blog

0. 前言 你需要掌握的知识： 矩阵与矩阵运算。 行列式。 1. 概念与应用 1.1 概念 LGV 引理是用于解决图上不交路径计数的问题。同时也是线性代数中行列式的一个经典应用。 我们阐述一下概念。 对于一张有边权的有向无环图 GGG，定义一条路径 PPP，的权值 w(P)w(P)w(P) 为路径上所有边的边权的乘积，也就是说 w(P)=∏(u,v)∈Pval(u,v)w(P)=\prod_{(u,v)\in P} val(u,v)w(P)=∏(u,v)∈P​val(u,v)。 定义 e(u,v)e(u,v)e(u,v) 为 u→vu \to vu→v 的所有路径 PPP 的权值之和，也就是 ∑P:u→vw(P)\sum_{P:u\to v} w(P)∑P:u→v​w(P)。 定义两个大小为 nnn 的点集的子集 A,BA,BA,B，分别称之为起点集合与终点集合，则一组从 A→BA\to BA→B 的不交路径 SSS 为：SiS_iSi​ 是一条从 Ai→Bσ(S)iA_i \to B_{\sigma(S)_i}Ai​→Bσ(S)i​​。其中 σ(S)\sigma(S)...

正解 首先在分析问题的时候不难发现操作的一个性质就是同一个 xix_ixi​ 对应多个所谓的 p[l,r]p_{[l,r]}p[l,r]​ 序列。 对于这种操作对应多个序列不好计数的限制，一般情况下我们有下面两种思路 探究一下什么序列能够被得到，而不是从操作序列的角度设计 DP 状态。 若硬是从操作序列入手，我们可以通过给操作附上某种特定的顺序，让每一个序列都附上一个唯一的代表元，而这个代表元就是我们需要分题目去设计的。 如果你从第一个思路想的话你会很快陷入瓶颈，不建议自行尝试不然你会很痛苦。 我们从第二个思路入手，那么我们要对操作序列确定一个顺序，使得我们的决策可以唯一化。 考虑用插入法，我们可以从大到小钦定每一个值的位置，就是倒着遍历 n,n−1,n−2,…,2,1n,n-1,n-2,\dots,2,1n,n−1,n−2,…,2,1,。每一次我们把对应的值插到当前最左端的位置。 通过这种方式，我们可以将问题从对 xxx 计数变为对上面合法构造的排列 ppp 进行计数。 考虑如果 DP，注意到每一次操作都是涉及的是 max⁡\maxmax 操作，不妨考虑利用大根堆笛卡尔树...

0.前言 侧重于理论以及做题大方向，方法论的指导。 本博客若没有特殊说明，所有变量默认取值范围为 Z\mathbb{Z}Z。 1.半群线段树 1.1 定义 我们都说，线段树能维护具有结合律的信息，不能维护没有结合律的信息，那么为什么线段树只能维护有结合律的信息呢？这里我们可以利用半群线段树的理论来进行说明。 首先要定义什么是半群，半群是一个二元组 (S,×)(S,\times)(S,×)，其中： SSS 是一个非空集合； ×\times× 是一个定义在 SSS 上的运算，即 x∈S,y∈S,x×y=z,z∈Sx\in S,y\in S,x\times y=z,z\in Sx∈S,y∈S,x×y=z,z∈S，即满足封闭性。 这个 ×\times× 运算满足结合律，即 (x×y)×z=x×(y×z)(x\times y)\times z=x\times(y\times z)(x×y)×z=x×(y×z)。 注意这里上面的 ×\times× 不是乘法，是抽象代数中的集合运算，这里用乘法符号让读者更好理解。同时要注意，半群并不要求拥有单位元和逆元。 而半群线段树是一种数据结构，...

1. Hall 定理 对于一张二分图，设两部分点数为 (x,y)(x,y)(x,y)，则其的一个完备匹配定义为左部分 xxx 个点成为匹配点，特别的，当 x=yx=yx=y 的时候这列匹配也称作完备匹配。 一个如上定义的二分图存在完备匹配的充要条件是对于左部分大小为 kkk 的任意子集 SSS，这些点在右部连到的点集，记作 N(S)N(S)N(S)，的大小不小于 kkk，即 ∣S∣≥∣N(S)∣|S|\ge |N(S)|∣S∣≥∣N(S)∣。 证明见： 「学习笔记」Hall定理。 上面就是 Hall 定理，下面是它的推论。 二分图存在大小为 kkk 的匹配，当且仅当 ∀S,∣S∣≤∣N(S)∣−k\forall S,|S|\le|N(S)|-k∀S,∣S∣≤∣N(S)∣−k。 进一步推论： 若使 GGG 中存在完美匹配，则最少补充 max⁡{0,∣S∣−∣N(S)∣}\max\{ 0,|S|-|N(S)| \}max{0,∣S∣−∣N(S)∣} 条边。 我们还有网络流的形式： 设左部点的流量为 aia_{i}ai​，右部点的流量为 bib_{i}bi​，那么有左部点满...

0. 前言 本篇文章不发布于洛谷文章广场，因为我是在自己 yy，不保证正确。 1. 介绍 同余最短路，用于解决完全背包计数问题，例如给你 nnn 个数，每个数可以选无限次，问你用这些数能够拼凑出的信息。 这里我们一般化，给定物品体积 aaa，每个物品可以选无数次，问是否存在一种选择方式，使得物品总体积恰好为 xxx。 考虑 DP，设 f(i)f(i)f(i) 表示能否拼凑出体积 xxx，转移方程是显然的： f(x)=f(x)or⁡f(x−ai)f(x)=f(x) \operatorname{or} f(x-a_{i}) f(x)=f(x)orf(x−ai​) 这是一个有向无环图（DAG）上的动态规划，没有环，这样的时间复杂度是非常高，因为我们要枚举 xxx，当 xxx 非常大的时候是无法承受。 而同余最短路就是优化这一过程的，首先对于一个完全背包计数问题，如果 xxx 可以被凑出来，那么 x+ai,x+2ai,…x+a_{i},x+2a_{i},\dotsx+ai​,x+2ai​,… 是可以都能够凑出来的。即如果能凑出来 xxx，那么 x+k×ai(k≥0)x+k\times...

1. 定义 竞赛图，即任意两点之前有且仅有一条边的有向图。即有向完全图，有 (n2)\dbinom{n}{2}(2n​) 条边。 至于为什么叫竞赛图，就是赢得点向输的点连边，一个边代表的是胜负关系。 2. 性质 兰道定理（竞赛图判定） 我们定义比分序列为将每个点的出度 sis_{i}si​ 从小到大排序的序列。 那么若满足 ∑i=1ksi≥(k2)\sum\limits_{i=1}^k s_{i}\ge \dbinom{k}{2}i=1∑k​si​≥(2k​) 且当 k=nk=nk=n 时取等（即 ∑s=(n2)\sum\limits s=\dbinom{n}{2}∑s=(2n​)），则一定能够造出一种竞赛图，反之不能。 必要性显然，考虑充分性证明，我们构造初始图，对于 j<ij<ij<i 则 i→ji\to ji→j 连边，设此时比分序列为 aaa，这个序列显然在上述条件能够取到等号。保持 ∑i=1kai≤∑i=1ksi\sum\limits_{i=1}^k a_{i}\le \sum\limits_{i=1}^k s_{i}i=1∑k​ai​≤i=1∑...

1. 介绍与引入 没有前言，懒得写了。 根号分治，本质是平衡规划思想（大纲 9 级），在预处理和询问复杂度中寻找平衡，我们通常用根号作为问题规模的分界线。我们确定一个界限 BBB，小于 BBB 的暴力预处理，大于的回答一次时间只需要 nB≤n\dfrac{n}{B}\le \sqrt{n}Bn​≤n​ ，那么整个题目就可以做到 O(nn)O(n \sqrt{n})O(nn​)。 根号平衡思想，是平衡规划思想中重要的内容，例如空间平衡，时间平衡，根号滚动数组，都可以用这种思想。 我们以一道例题引入：CF797E Array Queries 这种操作我们发现没有什么很好的性质来维护，因为 apa_{p}ap​ 和变化的 ppp 是有关的。这两个关系是相互制约的，如果我们只关注一个肯定是不行的。怎么办？ 首先我们先想暴力，我们有两种想法： 预处理所有 p,kp,kp,k 的答案。 暴力模拟。 第一个虽然可以 O(1)O(1)O(1) 回答但是预处理时间空间复杂度 O(nk)O(nk)O(nk) 无法承受，而暴力算法时间复杂度一次是 O(nk)O(\dfrac{n}{k})O(kn...

不是，近 5 年 NOI 从来没考过绿吧，不会吧？ 形式化题面如下： 给定一个有向图，包含 nnn 个节点和 mmm 条有向边。边有长度。对于每个节点 xxx，其出边被编号为 1→dx1\to d_{x}1→dx​（dxd_{x}dx​ 是出边数量）。从 111 号点出发，初始有一个变量 p=1p=1p=1，按以下规则移动： 若当前位于节点 xxx 且 p≤dxp\le d_{x}p≤dx​，则走 xxx 的第 ppp 条边，移动到相邻节点 yyy。花费为边的长度。 修改参数 ppp： 若 p<kp<kp<k，则令 p←p+1p\leftarrow p+1p←p+1，花费为 vpv_{p}vp​。 若 p>1p>1p>1，则令 p←p−1p\leftarrow p-1p←p−1，花费为 wpw_{p}wp​。 求 1→i1\to i1→i 的最小花费，若无法到达输出 −1-1−1。 一眼分层图，题目转化为建 kkk 层的有向图，每次跳不同层要花费规则上指定的代价，求单源最短路跑 Dijkstra。但是空间复杂度是 O(nk)O(nk)...

0. 前言 会添加的吧，会添加的吧？一定会添加的吧！ 1. 线段树优化建图 CF786B Legacy 区间向区间连边，我们可以利用线段树的优秀区间特性来进行连边。具体来说，我们建立两颗线段树，一颗专门管入边，一颗管出边入边的树父节点向子节点连边（如果子节点向父节点连边，会导致本来只连向该区间的边通过子节点向父节点连的边连向了更大的区间），同理出边的子节点向父节点连边。父子节点之间的边，边权为 0。 总边复杂度大约在 O(mlog⁡n)O(m \log n)O(mlogn) 级别。 例如上图，本题代码如下： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include<bits/stdc++.h>#define int long...

串串构造题，纪念自己做出来的黑串串构造。大胆猜想！小心求证。 以下定义 n=∣S∣n=|S|n=∣S∣。 我们首先根据题目中给出的第三个条件，我们来看子串 SSS 在放进 TiT_{i}Ti​ 和 Ti−1T_{i-1}Ti−1​ 的形式是怎么样的： 那么，由图不难观察到一个很明显的构造过程，也就是我们先反过来，由 [l,r][l,r][l,r] 出发，右端点每一次减小 2，左端点每一次减小 1，也就是 [l,r]→[l−1,r−2]→[l−2,r−4]…[l−x,r−2x][l,r] \to [l-1,r-2]\to [l-2,r-4] \dots [l-x,r-2x][l,r]→[l−1,r−2]→[l−2,r−4]…[l−x,r−2x]。那么有一个显然的移动下界就是在极端情况下 [l,r]=[1,n][l,r]=[1,n][l,r]=[1,n]，最多只能移动 n2\dfrac{n}{2}2n​ 次。那么现在问题在于如何使得这个移动过程能够足够移动多次，首先根据题意不难得出对于每一个 TiT_{i}Ti​ 都要保证是 SSS 的子串，而且我们还要每次从上一个 Ti−1T_{...