immix's blog

子序列指的是不连续的一些位置组成的序列，而子串指的是连续的一段区间。 括号串的简化 一个括号序列能匹配都匹配完之后剩下一定是一段前缀 ) 和后缀 (。（要不然就还有能匹配的部分） 比如序列 (())))()(() 最后留下的就是 ))(。 而我们能证明，该括号序列的最长合法子序列就是删掉了留下来的字符所得到的结果。（这就是答案的上界，而我们取到了上界） 比如说，上面的序列最长合法子序列就是 (())()()。 我们尝试把这种结构放到线段树上维护。 区间翻转，区间最长合法括号子序列 P10513 括号 给定一个长度为 nnn 的括号序列，支持 mmm 次操作： 翻转 [l,r][l,r][l,r] 中的括号，即 ( 变 )，) 变 (。 查询子串 [l,r][l,r][l,r] 最长合法括号子序列的长度除 222。 n,m≤5×105n,m\le 5\times 10^5n,m≤5×105。 对于线段树的每个节点，我们维护当前在左边剩余的右括号（l），右边剩余的左括号（r），节点的合并就是把中间的括号的一边匹配完。 1234567struct Node{ // 形如 ))) ...

准确的来说，线性基这个概念可以扩展到更大的线性空间中，但本文只包括了异或线性基。 线性基 定义 对于一个序列来说，一个满足如下条件的集合称作其线性基（不唯一）： 线性基中任意选择一些数（可以不选）的异或值所构成的集合，与原序列中任意选择一些数的异或值所构成的集合相同。 该集合的元素个数最少。 比如对于序列 {1,4,5,7}\{1,4,5,7\}{1,4,5,7} 来说，其一个线性基就是 {1,3,4}\{1,3,4\}{1,3,4}。 性质 线性基中不存在取值集合，使得异或和为 000。 否则可以删去一个数，仍然可以表达出一样的集合。 线性基中不存在任意两组取值集合，使得异或和相等。 否则就能得到异或和为 000 的取值集合。 若线性基的大小为 SSS，能异或出的数（包括不选得到 000）个数为 2S2^S2S。 由性质 2 可知任意异或都不重复，故个数为 2S2^S2S。 建立线性基 贪心算法 假设当前插入的数是 xxx，我们的线性基为 b0,b1,…,bkb_0,b_1,\ldots,b_kb0​,b1​,…,bk​，初始都为 000。 从高到低扫，如果 xxx 第 pp ...

前言 前置知识： 阶、原根、离散对数; 多项式（1）— 快速傅里叶变换（FFT）。 FFT 已经能很好的在 O(nlog⁡n)O(n\log n)O(nlogn) 内解决卷积问题，但是 FFT 用到的单位根和三角函数有关，只能采用浮点数储存，必定会带来精度误差。 我们尝试不在复数域内，而是在模剩余系内寻求一种新的单位根来解决问题，这样带来了两个好处： 不再有误差（只要大小没有超出模数）； 如果题目要求取模，一并可以完成取模的任务。 新型单位根 我们回看 FFT，FFT 中单位根 wnkw_n^kwnk​ 满足了如下性质： wnk=(wn1)kw_n^k = \left(w_n^1\right)^kwnk​=(wn1​)k； wn0,wn1,…,wnn−1w_n^0,w_n^1,\ldots,w_n^{n-1}wn0​,wn1​,…,wnn−1​ 互不相同； wnk+n/2=−wnkw_n^{k+n/2}=-w_n^kwnk+n/2​=−wnk​； 这个性质可以导出 wnk mod n=wnkw_n^{k\bmod n}=w_n^kwnkmodn​=wnk​。 w2n2 ...

多项式乘法与卷积 对于两个多项式 f(x)=∑i=0naixi,g(x)=∑i=0nbixif(x)=\sum_{i=0}^na_ix^i,g(x)=\sum_{i=0}^nb_ix^if(x)=∑i=0n​ai​xi,g(x)=∑i=0n​bi​xi，如果要求出乘积多项式 fgfgfg，朴素实现是 O(n2)O(n^2)O(n2) 的。但是，利用 FFT，我们可以在 O(nlog⁡n)O(n\log n)O(nlogn) 时间内完成这一问题。 从另一个角度来理解，多项式的乘法是一种加法卷积。 对于两个序列 {a0,a1,…,an},{b0,b1,…,bn}\{a_0,a_1,\ldots,a_n\},\{b_0,b_1,\ldots,b_n\}{a0​,a1​,…,an​},{b0​,b1​,…,bn​}，定义其卷积 {c0,c1,…,c2n}\{c_0,c_1,\ldots,c_{2n}\}{c0​,c1​,…,c2n​}，ck=∑i+j=kaibjc_k = \sum_{i+j=k}a_ib_jck​=∑i+j=k​ai​bj​。 不难发现 {an},{bn}\{a_n\},\{ ...

欧拉函数 定义 φ(n)\varphi(n)φ(n) 表示 1∼n1\sim n1∼n 中与 nnn 互质的数个数。 形式化地讲， φ(n)=∑i=1x[gcd⁡(i,n)=1]\varphi(n)=\sum_{i=1}^{x}[\gcd(i,n)=1]φ(n)=∑i=1x​[gcd(i,n)=1]，其中 [⋅][\cdot][⋅] 表示艾佛森括号。 性质 1 φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}φ(pk)=pk−pk−1，其中 ppp 为质数。 证明： 1∼pk1\sim p^k1∼pk 中恰有 pk−1p^{k-1}pk−1 个 ppp 的倍数，只有他们与 pkp^kpk 不互质。 即 φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}φ(pk)=pk−pk−1。 性质 2 欧拉函数是积性函数。 也就是说，对于互质 a,ba,ba,b，φ(ab)=φ(a)φ(b)\varphi(ab)=\varphi(a)\varphi(b)φ(ab)=φ(a)φ(b)。 证明： 引理1：xxx 与 ababab 互质的充要条件是 x ...

离散变量取值问题 有若干个变量，每个变量取值为 v1,v2,…,vnv_1,v_2,\ldots,v_nv1​,v2​,…,vn​，现在要求所有变量的和最小（大），且不同变量的取值有某种限制。（详细见下文例题） 先不考虑限制，考虑用最小割刻画这个问题。 如图所示，对每一个变量都建立 n+1n+1n+1 个点 X1,X2,…,Xn+1X_1, X_2, \ldots, X_{n+1}X1​,X2​,…,Xn+1​： 从 SSS 到 X1X_1X1​ 建立一条边权为 ∞\infty∞ 的边； 从 Xn+1X_{n+1}Xn+1​ 到 TTT 建立一条边权为 ∞\infty∞ 的边； 从 XiX_{i}Xi​ 到 Xi+1X_{i+1}Xi+1​ 建立一条边权为 viv_{i}vi​ 的边； 从 Xi+1X_{i+1}Xi+1​ 到 XiX_{i}Xi​ 建立一条边权为 ∞\infty∞ 的边。 这样我们保证了，每个变量所构造出的一条链上，在最小割中有且仅有一条边被割掉，被割掉的边的边权就代表了我们为这个变量的取值。 证明： 存在性： 如果没有边被割，那么显然存在 S→TS\to ...

题意 [ARC068E] Snuke Line 给定 nnn 个区间 [li,ri] (1≤li≤ri≤m)[l_i,r_i]\ (1\le l_i \le r_i \le m)[li​,ri​] (1≤li​≤ri​≤m)。 对 1∼m1\sim m1∼m 中的每一个 iii，求出存在一个 iii 的倍数在其中的区间个数。 解法 1（整除分块） 我们发现，对于一个 ddd 来说，[l,r][l,r][l,r] 中有 ddd 的倍数的充要条件是 ⌊l−1d⌋≠⌊rd⌋\left \lfloor \dfrac{l-1}{d} \right \rfloor \neq \left \lfloor \dfrac{r}{d} \right \rfloor⌊dl−1​⌋=⌊dr​⌋。 略证： （引理）⌈xy⌉=⌊x−1y⌋+1\left \lceil \dfrac{x}{y} \right \rceil = \left \lfloor \dfrac{x-1}{y} \right \rfloor +1⌈yx​⌉=⌊yx−1​⌋+1。 证明：设 x=ky+bx=ky+bx=ky+b，其中 ...

拉格朗日插值法 过 n+1n+1n+1 个横坐标互异的点 (x1,y1),(x2,y2),⋯ ,(xn+1,yn+1)(x_1,y_1),(x_2,y_2),\cdots,(x_{n+1},y_{n+1})(x1​,y1​),(x2​,y2​),⋯,(xn+1​,yn+1​) 的 nnn 次多项式恰为 f(x)=∑i=1n+1yi∏j≠ix−xixj−xif(x) = \sum_{i=1}^{n+1} y_i \prod_{j\neq i} \dfrac{x-x_i}{x_j-x_i} f(x)=i=1∑n+1​yi​j=i∏​xj​−xi​x−xi​​ 证明 将 n+1n+1n+1 个点代入显然得到结论。 模板 [洛谷P4781] 【模板】拉格朗日插值 给出 nnn 个点，插值出多项式，并求出一个点值，朴素实现是 O(n2)O(n^2)O(n2) 的。 如果要在取模下实现，记得先把分母都乘起来，然后统一求逆元，这样复杂度依然是 O(n2)O(n^2)O(n2)的。 参考代码： 12345678910111213141516171819202122232425262728293031 ...

shell 脚本介绍 略。看下面的代码自行意会 一键测试所有样例 123456789101112131415name=problemg++ $name.cpp -o $name -std=c++14 -Wallfor i in {1..10}do cp $name$i.in $name.in time ./$name diff $name.out $name$i.out -Z > /dev/null if (($?)) then echo 样例 $i 不通过 else echo 样例 $i 通过 fidone 注意这里的 -Z 开关可以自行调整。 $? 指的是上一个命令的返回值。 对拍 12345678910111213141516g++ gen.cpp -o geng++ std.cpp -o stdg++ my.cpp -o mywhile truedo ./gen ./std ./my diff out ans -Z if (($?)) then ...

点分治 淀粉质 常见题目套路：求出具有某一条件的路径个数/求出一条最优的路径 核心思路是：每次选取一个点 uuu ，统计所有经过这个点的路径，然后把这个点删去，对于剩下的森林执行同样的操作。 如何统计？所有经过点 uuu 的路径分成 3 部分，v1−u−v2v_1 - u - v_2v1​−u−v2​，其中 v1,v2v_1,v_2v1​,v2​ 不在同一个子树之中，然后每个点存储需要的信息，最后合并。 统计完点 uuu 后，把它从整颗树里面删去，以后不需要用到它了。 如果每次选取的点都是子树的重心，那么复杂度就能够达到 O(nlog⁡n)O(n \log n)O(nlogn)。 总结一下，就是如下流程： 对于一颗树 TTT： 找到重心作为根。 对每个子树，依次进行如下 3 步操作： i) dfs 求出每个子树的到当前根的信息； ii) 对于子树的所有节点，与前面的子树的信息进行合并求解答案； iii) 将这个子树节点的所有信息合并。 删去根。 对于根的每一个子树，回到第 111 步，直到只剩下一个节点。 信息究竟是什么意思呢？ 举个例子，求树的直径。（这是上文说的求出一条最优的 ...