qidao123.com ToB IT社区-企服评测·应用市场

标题: 新蔬菜专题 [打印本页]
作者: 前进之路    时间: 2022-8-28 03:52
标题: 新蔬菜专题
公式


\[\sum \binom{2j}{j} \binom{2i-2j}{2j}=4^i \]

\[\prod[w_i=1]={1\over 2^n} \sum\limits_S \Big( \prod\limits_{j\in S}w_j \Big) \ (w_i=\pm1) \]

\[FWT(f)=g \Longleftrightarrow g_S=\sum\limits_T (-1)^{|S \cap T|}f_T \texttt{   可以倒着用} \]

\[\prod {1\over 1-a_iz} = \sum c_i{1\over 1-a_iz} \Longleftrightarrow c_i={1\over \prod\limits_{j\neq i}(1-{a_j \over a_i})} \]

\[\texttt{the number of out-facing block buildings on a}\times\texttt{b}\times\texttt{c: } \det \big( \binom{a+b}{a+i-j}_{i,j} \big) (1 \le i,j \le c) \]

\[x^k=\sum\limits_{j=1}^k\Big\{ \begin{matrix} k \\ j \end{matrix} \Big\} x^{\underline{j}} \\\Rightarrow \sum i^kf_iz^i=\sum\limits_{j=1}^k \Big\{ \begin{matrix} k \\ j \end{matrix} \Big\} \sum i^{\underline{j}}f_iz^i=\sum\limits_{j=1}^k \Big\{ \begin{matrix} k \\ j \end{matrix} \Big\}F^{(j)}(z)\]

\[(uv)^{(k)}=\sum \binom{k}{i} u^{(i)}v^{(k-i)} \\\Rightarrow \sum G^{(i)}{z^i\over i!}=\prod\ \sum F_j^{(i)}{z^i\over i!}\quad (G=\prod F_j)\]
建模

一个 01 序列区间的众数 \(\iff\) 将 0 换成 -1 后区间和与 0 的关系
ARC137E：覆盖一个区间，每个位置覆盖次数有上限，超过后无贡献：最小费用循环流模型
在一个 DAG 中删去一些点，使剩下任意 3 个点不在一条链上：将原图 G 复制一遍得到 G'，对于每个点 u，从 G 中的 u 向 G' 中的 u 连边。答案即为这个新图的最长反链=最小路径点覆盖（=二分图匹配）。
一个合法的点分树，设它的根权值为树的深度，每个点的权值为其父节点的权值 -1，那么点分树方案合法  任意两个权值相同的点之间有一个权值比它们大的点
交换一个序列的相邻两个 01 \(\iff\) 将 0 视为向右下走，1 视为向右上走，产生的一个“谷” V 变成“峰” ^
从一个序列中删数就变成往一个序列里加数，往一个序列里加数就变成从一个序列中删数，一定要与出题人对着干！
思想

每当 pos 右移一位时，a 只有一个元素性质发生大的改变，其它元素平移后不变/变化相同
求“aaa中xxx的最大值”的最大值，可以枚举 aaa 中的所有 xxx，使它最大，记录下结果，再在所有结果中取最大值
边很稀疏的图 （\(m-n \le 9\) 之类的）可以考虑收缩 1，2 度点，甚至收缩 3 度点进行递归求解
Segment Tree Beats: 留坑。。。
当对一个序列的操作等与其元素之间的大小有关时，可以考虑将 \(\le k\) 的视为 \(0\)，\(>k\) 的视为 \(1\)，01 串的操作往往有一些很好的性质
对于一些作用在多个（复杂）位置的操作，可以考虑用数据结构（一般是线段树）维护操作轴即时间轴，然后按顺序枚举位置（而不是时间）
从一个字符串 \(S\) 加/删 字符变成另一个字符串 \(T\)，可以考虑将操作倒过来，变成从 \(T\) 删/加 字符变成 \(S\)，往往会取得奇效
区间放一个数查询区间 mex：
AC 自动机能够处理：\(O(\log len)\) 求出一堆串中拎出一个文本串，其它串作为模式串出现的次数（路径 +1 fail 树求和）—— fail 树是一个可以与 SAM 媲美的东西
动态规划肯定要排序，但不一定要从左到右转移，也可以将所有转移排序，然后一个个转移进行，这样可以保证转移过程中的另一个有序性（如凸包上的斜率）。此时假的转移自然就假了，真的转移一定能转
对于停时问题，如果状态转移形成 DAG，则停时期望为所有非法状态出现的概率 * 离开这个状态的期望时间。（见 定理3）
当我们要数“一个 \(f\) 生成的一个 \(g\)” 的不同的 \(g\) 的方案数时，如果不同的 \(f\) 可以生成同一个 \(g\)，则应该想办法钦定每个 \(g\) 由唯一一种方法被 \(f\) 生成，然后数这样的 \(f\) 的个数。
随机二分法：对于一个很大的数域，想要求第 \(k\) 大，我们随机挑一个数计算有 \(c_0\) 个数小于它和有 \(c_1\) 个数小于等于它，若 \(c_0+1\le k\le c_1\) 则其为答案，否则根据结果左右递归处理，次数期望即为 \(O(\log V)\) 的
时间复杂度分析小专题


\[\sum\limits_u \sum\limits_{v\in son_u} siz_v(\sum\limits_{w\ before v}siz_w) = O(n^2) \]
证明：等价于每两个点在其 LCA 处贡献 1，自然 \(O(n^2)\)
在一个序列上以一定的规则游走，提出 \([l,r]\) 的位置所走出的序列是整个序列所走出的序列的一个子串
一堆数异或和 \(=C\) 的题目，有两种基本方法：一是 \(FWT\)，二是如果有一个数可取的值为 \([0,2^k)\)， 则方案数可以 \(O(1)\) 计算（其它任选，这个数调整即可）
技巧

\(mod 2\) 意义下的多项式，乘法（又称二项卷积）可以变为子集卷积，求逆即为自身，可以各种乱搞
当一个区间的答案与其最小值/最大值有关时，可以考虑对整个序列建出笛卡尔树，然后对每个节点预处理出其前后缀的答案，对于每组询问 \([l,r]\)，以其最大值/最小值 \(k\) 为中心划分成三部分：\(val(l,r),f(l,k-1),f(k+1,r)\) 计算，后两者即为一个节点的前缀/后缀
分治 FFT 只需要保证递归层数是 \(O(\log n)\) 级别的，例如 \(m\) 个多项式相乘，次数和为 \(n\)，尽管这些多项式次数各不相同，但直接普通分治 FFT，每层的次数和均为 \(O(n)\)，共 \(O(\log n)\) 层，则总复杂度为 \(O(n \log^2 n)\)
！！  有些（很多）换根树形 dp 可以对于每个“上子树”都算出它的 dp 值，但这样做是 \(O(n^2)\) 的（虽然界很弱），怎么办？拆点！将一个点的若干个儿子拆成一条链（和边分治一样），然后就是 \(O(n)\) 的了（边权的重赋值可能有点棘手）
求强连通分量中所有环长度的 \(\gcd\)，可以跑出一棵 dfs 树，然后对所有非树边 \((i,j)\)，求 \(|dep_i+1-dep_j|\)  的 \(\gcd\)。
---——对于一些传染性问题的技巧——
对于一棵树，求一棵子树内是否有某种颜色，可以将所有有此颜色的点按 dfs 序排序，每个点打标记 +1，每相邻两个点的 lca 打标记 -1，答案即为子树内标记和
（因为听说 pb 在 GDOI2019 因为不会这个技巧爆炸了所以全部加粗）
dp 神奇优化：CDQ 分治（？，\(solve(l,r)\) 递归到 \(solve(l,k-1)\) 与 \(solve(k,r)\)，在中间处理 \([l,k-1]\) 到 \([k,r]\) 的转移。
然后 \(k\) 不一定要是区间中点，如果能够在 \(\min (k-l,r-k)\) 的时间内处理出这个转移，则时间复杂度等同于启发式合并，\(O(n \log n)\)。
复杂度分析：有时一个算法的复杂度可能看上去是 \(O(nmk)\) 的，实际上是 \(O(nk\frac{m}{k})\) 的，然后你就过了（？
如果要求一个区间第 \(k\) 大的数的贡献，可以转为枚举每个位置，看它在那些区间里面是第 \(k\) 大，这个就开一个链表，每次查询最小的左右两边 \(k\) 个位置，再把它删掉。
解树上的 dp 方程的好套路：\(f_u=\sum\limits_{v \in  son_u} c_vf_v+d_uf_{fa_u}\)，则记 \(f_u=a_uf_{fa_u}+b_u\)，当 \(u\) 为根时就有 \(f_u=b_u\)，于是再从上到下递推回来即可
处理点分树的技巧：留坑
对于一个由若干条直线组成的下凸函数，可以用如下方法求出它的所有拐点：先找出最左端和最右段的直线，找出它们的交点，如果这个交点在凸壳上，则这个区间内只有这一个拐点，返回；否则，找到这个交点横坐标所在直线，左右递归处理。这个过程是 \(O(n)\) 的（不会证）
若 \(a_1,a_2,\dots,a_n\) 中有 \(k\) 个子集的和为 \(j\)，则不妨设 \(a_1+a_2+\dots+a_x=j\)，有 \(a_1,a_2,\dots,a_x,-a_{x+1},-a_{x+2},\dots,-a_n\) 中有 \(k\) 个子集的和为 \(0\)。

\[x^k=\sum\limits_{j=1}^k\Big\{ \begin{matrix} k \\ j \end{matrix} \Big\} j!\binom{x}{j} \]
于是 \(k\) 次方可以表示为若干个组合数之和，这给组合意义赋予了非常好的武器。
对于计数的问题，可以考虑转化为期望，然后变成次数较小的多项式进行插值。
dp 的批量转移技巧：如果我们要进行若干次 dp，每次 dp 的初值相同而终态不同，则我们可以将整个 dp 反过来进行，如果原来的 dp 有 \(u*k \rightarrow v\)，则在新的 dp 中进行 \(v*k\rightarrow u\)，就可以求出 dp 的结果。仅限于一个点 dp 到另一个点的 dp。
巧妙推性质：如果我们可以从一个状态转移到其它若干个状态，但每个状态的某个函数值恰有一种转移使之严格变小，且函数值均非负，则我们可以证明所有状态都可以走到某若干个函数值最小的状态，从而形成树/森林/基环树。
dp 技巧：如果一个转移方程形如 \(f_{i,j,k}\cdot a(j) \cdot b(k)\rightarrow g_{i',j',k'}\) 之类的，其中中间的两个转移系数分别与某一维独立，则可以考虑设置一个中间状态 \(h_{i,j,k}\)，例如让 \(f_{i,j,k}\) 转移到 \(h_{i',j',k'}\)，再由另一种转移从 \(h_{i',j',k'}\) 转移到 \(g_{i'',j'',k''}\)。
无穷归纳法： 求一个序列 \(a_1,a_2,\dots,a_n\) 的函数 \(f(a_1,a_2,\dots,a_n)\)，可以对方差进行归纳，即

\[f(a_1,a_2,\dots,a_k,a_{k+1},\dots,a_n)\leftarrow f(a_1,a_2,\dots,{a_k+a_{k+1}\over2},{a_k+a_{k+1}\over2},\dots,a_n)\]
由于前者的方差严格小于后者的方差，我们就可以无限将序列 \(a\) 变为同一个值！
（事实上，方差这个函数可以改为任意一个会严格变小的函数）
树上多点最远距离： 维护一个树上的点集，支持加点，删点，询问一个（树上的）点到点集中任意一个点的最远距离
做法：把所有点按一定顺序丢到一个线段树里（只要有顺序就行，方式任意，这意味着可以按 时间戳/dfn 排序等方式也是可行的），每个节点上维护其节点内所有点形成的虚树的直径端点，合并时直接6条线段取最大值即可（用 #define 好用）
查询时直接对区间内直径的两个端点测一下即可（这意味着也可以只对一个 时间段/子树 查）
树上与点 \(u\) 距离在 \(k\) 以内的点一定在 \(u\) 的 \(k\) 级祖先的子树内（注意判0）

<strong>拉格朗日乘子法
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 qidao123.com ToB IT社区-企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.5