wjyppm's Blog

1. 一类连通块问题的优化 1.1 介绍 对于一类树上连通块或路径问题，合并子树（可以看作卷积）的复杂度很高，但是插入一个点和自己与自己合并（可以看作点积）的复杂度可以用点分治来进行优化。 以一道例题引入：Ridiculous Netizens - HDU 6643 首先你会想到用树形背包来做，但是问题在于如果你直接设置为 f(u,i)f(u,i)f(u,i) 表示为 uuu 子树内乘积为 iii 的方案数，但是直接做会出现两个问题： 你无法保证你选取的方案子树是连通的。 在不考虑乘积的情况下，你的合并是 O(mm)O(m\sqrt{m})O(mm​) 的，因为你要枚举约数。 先保证状态是 O(nm)O(nm)O(nm)，然后我们考虑把第一点解决掉，第一点的问题就是在于我们一般树形背包是自底向上合并的，但是这样可能中途就会断掉。 转化思路，我们考虑每个点作为连通块内部的贡献，我们先考虑强制这个连通块经过根，可以发现在这种情况下，如果一个点在连通块中，那么它的父亲必须也在。 自此，由于选取一个点就必须选它的父亲，所以要去选一个子树就必须选这个子树的根。我们可以把原命题转化为...

0. 前言 本文章介绍内容难度不超过提高组难度，属于笔者提高组复习计划的一部分。 1. 卡特兰数 1.1 介绍 卡特兰数作为广泛出现在OI中的一类特殊数列，第 iii 项改为 CiC_{i}Ci​，其拥有广泛的意义。数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862。 这些特殊的数字，在信息学竞赛里许多题目都有这个数列的存在，可以在打表找规律时激发灵感。 我们通过一个经典例子来说明，即折线问题，如下图： 在平面上从 (0,0)(0,0)(0,0) 走到 (n,n)(n,n)(n,n)，每次只能向上或者向右走，不穿过 y=xy=xy=x 这条直线有多少种方案。 1.2 朴素解法 我们考虑枚举最后一个 y=xy=xy=x 上的点 (i,i)(i,i)(i,i)，可以把问题规模缩小。 我们强制钦定最后一段不碰到 y=xy=xy=x，我们在 (i,i)(i,i)(i,i) 继续向终点走去的过程中，第一步只能向右走，到 (n,n)(n,n)(n,n) 的最后一步只能向上走，中间的问题我们可以视作从 (i,i+1)→(n,n−1)(i...

省流：被诈骗的一集 T1 诈骗题。 本题的性质只能从答案入手，很难观察到答案不超过 333，具体的就是令 i=n−2,j=n−1i=n-2,j=n-1i=n−2,j=n−1。那么由于 LCP 肯定不超过长度，所以答案构造 ≤3\le 3≤3。 一个暴力的想法就是暴力枚举两个指针 i,ji,ji,j 来去判断，但是这是 O(n2)O(n^2)O(n2) 的，不过有了答案 ≤3\le 3≤3 我们思考具体取值。 考虑固定 iii。首先 j∈[i+1,i+3]j\in[i+1,i+3]j∈[i+1,i+3] 的枚举是肯定需要的，复杂度可以接受。但是一但到了 i+4i+4i+4 之后呢？结论是直接取到 j=n−1j=n-1j=n−1 即可，答案还是因为答案不超过 3，可以让 LCP(a,c)+LCP(b,c)=0LCP(a,c)+LCP(b,c)=0LCP(a,c)+LCP(b,c)=0 当且仅当存在 cj≠a1∧cj≠bic_j\neq a_1\land c_j\neq b_icj​=a1​∧cj​=bi​。否则：如果 a1≠bia_1\neq b_ia1​=bi​，我们选 j...

0. 前言 邦邦卡邦！又学会了新的双射方式！这次是关于树的双射内容！ 1. 定义与构建 1.1 定义 prufer 序列，又叫做 prüfer 序列，因为键盘平时不太好打出来 ü 所以一般叫做 prufer 序列。他的作用就是可以将一个有标号的 nnn 个点的树映射成一个由 n−2n-2n−2 个在 [1,n][1,n][1,n] 范围内的数所组成的序列，同时这个序列也会唯一对应一个树。也就是说，prufer 序列和树结构构成双射。 1.2 构建 钦定 nnn 为树的根节点，因为这个树我没有说这是有根树，所以不会影响。 每次选择编号最小的叶子结点并删掉它，再把它的父亲的编号加入序列中。重复此操作，直到树上只有两个点为止。显然，这两个点中必有一个是编号最大的点 nnn。为什么是两个点呢？假设我们再进行一次操作，那么进入序列的必然是 nnn。这是没有意义的操作。而如果我们进行了这次操作，末尾不为 nnn 的 prufer 序列将失去对应一个树的优秀性质。 以下是一个 n=7n=7n=7 的例子： 最终的序列就是 {2,2,3,3,2}\{2,2,3,3,2\}{2,2,3,...

T1 字符串基础练习，时间复杂度 O(nL)O(nL)O(nL)。 T2 BFS 洪水填充，但是如果你直接暴力枚举一个点进行拓展的话显然不对。我们可以通过多源 BFS 来做到 O(nm)O(nm)O(nm)。 注意这里必须 O(nm)O(nm)O(nm)，记得以后一定要计算复杂度，不然会被卡常。 T3 更唐的做法： 观察一组合法的三元组的格式是怎样的，显然这三元组因为在树上，故必然存在一个点使得到这三个点距离相等(距离不等反而赢了）。如果不认为显然的请列方程计算，你会发现有解情况唯一剩下的都有环。 那么我们可以枚举交点，把它提起来作为根，然后我们枚举距离 ttt，对每一个孩子的子树求其子树内有多少距离根节点为 ttt 的点，记一个孩子子树的合法点个数为 aia_{i}ai​。 那么答案就是三个不同子树的点进行配对 ∑i≠j≠kaiajak\sum\limits_{i\neq j\neq k} a_{i}a_{j}a_{k}i=j=k∑​ai​aj​ak​。不难发现上述过程光枚举就花了 O(n2)O(n^2)O(n2)，这个玩意还是 O(n3)O(n^3)O(n3) 的...

T1 8 数码问题简化版，O(7!)O(7!)O(7!) 爆搜 BFS，没了。 T2 ∑i=0m+1(n+1i)=∑i=0m(ni)+(n−1i)\sum\limits_{i=0}^{m+1}\binom{n+1}{i}=\sum\limits_{i=0}^{m}\binom{n}{i}+\binom{n-1}{i} i=0∑m+1​(in+1​)=i=0∑m​(in​)+(in−1​) ∑i=0m+1(ni)=∑i=0m(ni)+(nm+1)\sum\limits_{i=0}^{m+1}\binom{n}{i}=\sum\limits_{i=0}^m \binom{n}{i}+\binom{n}{m+1} i=0∑m+1​(in​)=i=0∑m​(in​)+(m+1n​) 时间复杂度为 O(n)O(n)O(n)，瓶颈在预处理组合数。 T3 Subtask 1 暴力枚举排列，逆序对也可以暴力统计，时间复杂度 O(7!)O(7!)O(7!)。 Subtask 2 注意到暴力枚举排列不行，但是注意到这个只和排列奇偶性有关。本质上就是求行列式。具体的就是照题目的把矩阵 [...

前言 省流：300 分。 T1 考虑 DP，设 f(i,0/1/2)f(i,0/1/2)f(i,0/1/2) 表示处理到第 iii 个数，当前是往左，不动，往右，方案是否合法，转移如下： f[i][0]=f[i−1][0]⋅[xi−xi−1=1]+f[i−1][1]⋅[xi−(xi−1−1)=1]+f[i−1][2]⋅[xi−(xi−1+1)=1],f[i][1]=f[i−1][0]⋅[xi−1−xi−1=1]+f[i−1][1]⋅[xi−1−(xi−1−1)=1]+f[i−1][2]⋅[xi−1−(xi−1+1)=1],f[i][2]=f[i−1][0]⋅[xi+1−xi−1=1]+f[i−1][1]⋅[xi+1−(xi−1−1)=1]+f[i−1][2]⋅[xi+1−(xi−1+1)=1],\begin{aligned} f[i][0] &= f[i-1][0] \cdot [x_i - x_{i-1} = 1] + f[i-1][1] \cdot [x_i - (x_{i-1} - 1) = 1] + f[i-1][2] \c...

0. 前言 我们主要讨论的就是广义的圆方树。 1. 介绍 广义圆方树是刻画图上点连通性的工具，是 Tarjan 算法的一个强有力拓展。广义圆方树能够述原图任意两点之间的所有割点，即路径 u→vu\to vu→v 上所有必须经过的点。下面有一张图来举例： 图的问题我们不好处理，但是众所周知，树上问题是比普通的图论问题处理起来方便得多的。所以我们将图转化为圆方树的意义就是在于通过树上的算法简化问题。 广义圆方树中的节点分为两类：圆点和方点，在上图中所表示出来。圆点就是原本图上的点，而每个方点都代表了一个点双联通分量。将每个方点和所有在这个联通分量中的点连起来。 注意，只有原图联通的时候才能是一棵树，如果不连通的话那么会形成森林。 我们在求解点双的时候可以顺便建出圆方树，以下为代码，adjadjadj 为原图，GGG 为圆方树。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<bits/stdc++....

0. 前言 你需要知道： FFT 或 NTT。 CDQ 分治。 1. 介绍 分治 FFT，用于解决这一个问题： 给定长为 n−1n-1n−1 的序列 ggg，求长为 n−1n-1n−1 的序列 fff，满足： fi=∑j=1ifi−jgjf_i=\sum_{j=1}^i f_{i-j}g_jfi​=∑j=1i​fi−j​gj​，边界为 f0=1f_0=1f0​=1。 要求时间复杂度 O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。 你可能会说：“这不就是卷积吗，FFT秒了！”但是你发现这玩意不太对劲，因为你卷积默认你是知道 fff，现在问题在于你不知道 fff，要一个一个求。 我们解决这个问题可以利用 CDQ 分治的思想，具体的，设 solve(l,r) 表示计算 g[l,r]g[l,r]g[l,r] 内这一段子问题的函数，注意这里算的不是 fif_ifi​，而是这一段自己对自己的贡献。为了我们 FFT 的方便，一开始肯定是调用 solve(0,1<<k) 的形式。 让后就是分治的部分，首先 midmidmid 劈成 [l,mid],[mi...

0.前言与ntt 组合数学过于差得我，必须重修！ ntt板子？其中MOD，G,INVG需要自行定义 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657namespace Poly{ int rev[MN]; int ksm(int a,int b){ int ret=1; while(b){ if(b&1) ret=ret*a%MOD; a=a*a%MOD; b>>=1; } return ret; } void dorev(int f[],int len){ for(int i=0;i<len;i++){ rev[i]=rev[i>...