TRICKS - XSC062 的博客

TRICKS

2023-11-17

下饭

想着写点什么东西，就是说，不会被归入知识点，却又感觉很常用的东西。

哦我懂了，通常来说我们管这个叫 trick。

先记一记自己遇到过的。

DS

不强制在线复杂度不依赖均摊的可持久化数据结构 \(\to\) DAG 上直接模拟。

猜猜这里内涵的是哪个名字叫并查集的小朋友
哦哦更新了，还有你，线段树合并
只要求在最新版本上修改和查询所有版本的可持久化数组可以在 vector 上二分，又唤部分可持久化。
在同时可以使用线段树合并和主席树解决的问题中，选前者。

问就是跑不满

数学

先整点若智的视力问题。虽然我在数学方面跟若智也没差太多了。
- \(\{1,1,2,3,5,8,\cdots\}\) 是斐波那契；矩阵可以优化；生成函数可以找通项；\(f_i=\sum\limits_{i=0}^nC_n-i^i\)。
- \(\{1, 1, 2, 5, 14, 42, 132, 429, 1430,\cdots\}\) 是 Catalan，走网格不能穿过对角线 / 构造二叉树方案数 / 一群人买电影票。有组合求法 \({2n\choose n} - {2n \choose n - 1}\)；生成函数还是可以找通项；
- \(\{3, 7, 6, 15, 25, 10, 31, 90, 65, 15, 63, 301, 350, 140, 21, 127, 966,\cdots\}\)，中间插着一堆 \(1\) 我写不下了所以删了，是展开了的第二类斯特林数三角形，把 \(n\) 个不同球，不空放，放到 \(k\) 个相同盒子的方案数，有递推式 \(S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)\) 和二项式反演出来的通项 \(S(n,m)=\sum\limits_{i=0}^m\dfrac {(-1)^{m-i}\cdot i^n}{i!\cdot (m-i)!}\)。多项式可以 \(n\log\) 算同一行 / 列，方法不太一样。

\(O(n)\) 求任意 \(n\) 个数的逆元：

inv[0] = 1;
for (int i = 1; i <= n; ++i)
    inv[i] = inv[i - 1] * a[i];
inv[n] = qkp(inv[n], mod - 2);
for (int i = n; i; --i) {
    int t = inv[i - 1];
    inv[i - 1] = inv[i] * a[i] % mod;
    inv[i] = inv[i] * t % mod;
}

求线段 \((x_1,y_1,x_2,y_2)\) 穿过直线系 \(x+y=k\cdots m(k\in \mathbb{N}^*)\) 的次数。

算出线段中 \(x+y\) 的取值范围也即 \([x_1+y_1,x_2+y_2]\)（斜率为负就不同了，但可以证明都是单调的），求出 \(k\cdot m\) 在里面的出现次数就可以了。

~~有的人高中数学欠的债要到竞赛来还~~

goto CF2098E。

图论

一系列元素，每个元素有不超过两种可选值，要求最终每个元素值不同，求方案数。

对所有可选值建图 / 并查集。如果只有一个可选值，看作两种可选值相同，连自环；否则把两个可选值连边。此时一个元素对应一条边，即对于每条边选一个端点，满足每个端点被选最多一次。

对于所有连通块：
- 若 \(n>m+1\)：没有这种可能性，不连通的。
- 若 \(n=m+1\)，即该连通块为树，任选一个点不选都能唯一构成一组解，方案数为 \(n\)。
- 若 \(n=m\)，即形成基环树：
  
  由于环上点只能且必须被环上边选，树上边的选法唯一。主要讨论环边选法。
  - 若环为自环，答案为 \(1\)；
  - 否则枚举环上所有边是统一选顺 / 逆时针方向的端点，答案为 \(2\)。
- 若 \(n<m\)：
  点不够用，答案为 \(0\)。最后把所有连通块的答案相乘就可以得到总答案。参见 Ball, Baggage Claim
比如有对图中边权的更新。像是让你求某某的最小，然后更新操作是减小某个边权。

这个时候我们就会发现改边不太现实，可以直接加边，因为保留原来那条更大的边不会影响答案。
题不知道。
有环图上的 DP，通常来说可以根据状态转移方程的形式找到环上的「根源」，即不由任何环上节点转移得到。

无视根源在环上的前驱边就可以用类拓扑的方式转移。
Goto solu to 商人。
关于树的直径：
- 树的半径（即 \(\min\limits_x\{\max\limits_y dis(x, y)\}\)）的一端一定在直径上，且在直径中间。
  如果不带权的话就是直径长度的一半 ~~不然为啥叫半径~~。
- 如果知道一坨连通块内的直径是 \(x\to y\)，另一坨是 \(a\to b\)，那么两个合并起来的直径一定是 \(\{x,y,a,b\}\) 里的 \(C_4^2\)。
  以及树上的连通块是树
- 动态维护树的直径（比如修改叶子的边权，这里是为了保证单点修改）：
  用上面提到的方法，线段树维护一段连续欧拉序内（不用 DFS 序是为了保证联通）的直径和两个端点，然后求 dis 再合并。为了快点儿我们在顺势欧拉序上 st 表来查 LCA 即可 \(n\log\) 地解决问题。
奇奇怪怪的优化建图：

通用的是 \(n\log\) 线段树，目前还见到过前缀和优化建图（前提是每条边都指向某个前缀区间，与线段树优化建图相比的优势是虚点数为 \(O(n)\)，eg）。

DP

用计数 DP 代替你那又臭又长还调不出来的该死的大容斥。
碰到了「起点状态到终点状态，中间不能经过一些非法状态的方案数」，可以用 \(f_i\) 表示从起点，不经过 \(1\sim i-1\) 的非法状态，到达非法状态 \(i\) 的方案数，最后将终点状态也视为一个非法状态并 DP 即可。
Goto solu to CF559C Gerald and Giant Chess，solu to 两双手。
要求字典序大于 / 小于给定值的方案数，考虑使用 \(f_i\) 表示 \(1\sim i\) 全部和给定值相同，\(i+1\) 大于 / 小于给定值，后面乱搞的情况总数。
Goto 冒泡排序。
求方案数，如果用通常的「考虑满足条件的情况并转移」，就必须能够简单地对条件进行判定。

如果这一点做不到，可以考虑从最简单或最极限情况出发构造出一般情况，并计算相应的方案数。

goto solu to 染色…

http://222.180.160.110:61235/contest/3887/problem/3

有 \(N\) 个格子排成一排，你需要用至多 \(M\) 种颜色给这些格子染色，每个格子恰好染成某一种颜色，不需要每种颜色都用上。求有多少种染色方案满足相邻的同色格子不超过 \(K\) 对。

不妨将一对相邻同色格子称为同色对，将一串连续的相同颜色称作一段，那么最极端的情况下会有 \(N\) 段（即不存在同色对）。

构造一段长度为 \(L\) 的 \(L\) 段序列（即不存在同色对）。此时将任意一段长度增加 1，则出现一对同色对。接下来，不论是选取长度为 2 的那一段，还是选取剩下的长度为 1 的段，将其长度增加 1，都会且仅会增加 1 对同色对。

以此类推，进行 \(K\) 次「选取一段并将其长度增加 1」的操作，可得到刚好 \(K\) 个同色对，此时序列长度为 \(L + K\)，而 段数没有变化，仍是一开始的 \(L\)。所以反过来，如果在长度为 \(N\) 的序列中存在 \(K\) 个同色对，那么段数为 \(N-K\)。~~很难想象题解用「所以」两个字直接略过了上述推导过程~~

由此，我们只要考虑分别将序列任意分为非空的 \(N-K\sim N\) 段，就可以解决问题，隔板法可得将 \(N\) 分为 \(T\) 段的方案数为 \(C_{N-1}^{T-1}\)。在此基础上考虑染色，由乘法原理，将 \(T\) 段染色的方案为 \((m - 1)^{T - 1}\times M\)。

取 \(T=N-K\sim N\) 并求和问题即解决。
如果有转移会有后效性不妨考虑是否有前效性然后逆序 DP。

比如题目让我们求最小字典序。你只知道最后一个字符肯定不能推断出谁的字典序最小，但如果你知道最开头一个字符，并保证从后往前填表的每一步都走的最小就可以。

goto solu to 匹配数…

http://222.180.160.110:61235/contest/3887/problem/2

求出最小的、不含前导零的 \(n\) 位数 \(x\)，满足 \(n-1\) 条限制，第 \(i\) 条限制规定 \(x\) 的第 \(i\) 位和 \(i + 1\) 位的关系（小于、大于、等于、不等于）。

如果正着 DP，也就是说先确定前面的数位再向后 DP，后面的数位就没办法决定选择哪个已有状态进行转移，因为我们没有办法仅凭上一位就得到哪个状态拥有最小的字典序。

但是题解很风轻云淡地给出了一个我一辈子想不出来的 fix：倒着 DP。我们只要保证每次选取最小的可行的下一位即可，这恰好符合字典序的定义。

记录前驱（or 后继？）后输出即可。
状态拆分技巧。比如状态 ABC 不一定要从状态 A、状态 B、状态 C 分别 \(O(m)\) 的转移，而可以从 A 和 BC 以 \(O(1)\) 完成转移。
Goto solu to 单词。
有结论：一个长度为 \(n\) 的 \(1/-1\) 随机序列的前缀和离 \(0\) 的距离期望不超过 \(\sqrt n\)。

故胡乱拓展一下，在保证值域内分布均匀的整数域内背包，在 random_shuffle 后实际最大状态不太会超过 \(\sqrt V\)。

因为这个是由一个科什么什么定理推来的中间很松的结论，所以运气比较好的时候甚至不会超过 \(\log v\)。

哈希

用哈希解决，呃，怎么概括呢，比如区间计数，其中合法区间的左右端点对应着一种转化后的「全等」关系……？
Goto Three Occurrence。
xor hash

使用于异或判断次数奇偶性 / 元素存在性的哈希。

我们知道，区间里每个值出现次数都是偶数的必要不充分条件是区间异或起来为 \(0\)。之所以不充分是因为存在类似 \(1\oplus 2\oplus 3=0\) 的情况。

然后怎么让他变成充要的呢，哎，我们把每个数都给他哈希成一个随机大数（比如 ull），这样冲突的概率就会变成 \(2^{-64}\)。

goto NOI2024 D1T1。

goto solu to 牛客题…

给定一棵带权树，把 \((u,v)\) 间简单路径上的边权全部拉出来生成数组，两个人在数组中轮流选数，每次选走的数必须小于等于上一个人选走的数，不能选的人输，问有多少个 \((u,v)\) 满足先手必胜。

首先给一个结论，如果在 \((x, y)\) 的路径上有任何一种边权的数量是奇数，那么就要统计 \((x,y)\)。

首先，假设 \(x\) 是一个边权。如果从最小边权一直到 \(x\)，每个边权的出现次数之和为奇数，先手必胜。

因为这个时候先手选 \(x\)，后手选任意一个小于等于 \(x\) 的边权，原来总共有奇数个可选项，选走两个，剩下的可选项的个数还是奇数个。

如此递归下去，最后一定会出现：可选最小边权剩下奇数个，那么两个轮流选，明显先手胜。

然后，如果任意一种边权出现的次数是奇数，那么先手胜。

为什么呢？因为如果它是最小的出现次数为奇数的边权，那么它和比它小的所有边权的数量之和为奇数，因为前面的出现次数都是偶数。如果它不是最小的，那么明显就是因为存在比它更小的。根据我们刚刚得到的结论，此时先手胜。

所以，问题就转化为了：统计点对 \((x, y)\) 的数量，满足 \(x\) 到 \(y\) 的简单路径中存在出现次数为奇数的边权。

另一种可行的转化是，用 \(C_n^2\) 减去路径上不存在出现次数为边权的点对数。

接下来讲讲统计。这个要用到一个 xor-hashing，字面意思，给异或用的哈希，专门应对这种情况。

给每个边权映射一个值，为 base 的 rand() 次方，自然溢出即可。然后直接按照之前的操作处理就好了。

如果一个你想找到类似于 1 ^ 2 ^ 3 = 0 的情况，其出现概率与数字的二进制位数有关。因为 xor 只针对于同一位，结果不会被上一位或下一位干扰，所以每一位出现异或起来为 \(0\) 的概率是 \(\dfrac 12\)。只要我们整点比较强力的 \(k\) 位二进制数，那么出现以上情况的概率就是 \(2^{-k}\)。

那么这个比较强力的 \(k\) 位二进制数，用比较强力的类字符串哈希生成方式，再使用一个很大很大的随机数替代字符串哈希中表示下标的 \(i\)，用自然溢出让它显得更加稳妥就好。

所以现在我们程序寄掉的概率就是 \(\dfrac 1{2^{64}}\)，好事情啊好事情。

最后时间复杂度 \(\mathcal O(n\log n)\)，\(\log n\) 来源于映射。

关于最值

关于冒泡排序

『冒泡排序有一种被出烂但是每次碰到我都不会的美感。』——wosile

这个人我不认识，但是我觉得这句话说得太好了！

一轮冒泡排序做的事情：将序列按前缀最大值为段首划分为若干段，并把其移到段末。
goto 1 Loop Bubble Sort。
前缀最大值在一轮冒泡排序后仍是前缀最大值。

关于 LIS

要求一个下标在序列 LIS 中（显然一个序列存在多个 LIS）的出现次数。

这个时候分别统计以其结尾和开头的 LIS 长度与次数，如果加起来是序列 LIS 的长度，那么次数相乘就是答案。

杂项

对于悬线法：可以顺带维护一些东西。

具体可维护的东西和倍增差不多吧，还是比单调栈泛用性大很多的。是单调栈 / 单调栈上二分的 \(O(n)\) 平替。

但事实上可以用笛卡尔树完美替代

不过肯定悬线是好写很多的。一行代码还不用在意任何特殊情况的单调栈谁不爱呢。
Goto solu to 情景剧。
\(k\) 个「二者至少选其一」形式的限制，要求选的尽可能少，使用 \(2^k\) 枚举后取并集代替你那脑子被电灯泡撞了才能想出来的 \(3^k\) 枚举。

言论

杂题全谈

杂题