咕了许久又来写东西了（
简单记录一下 2020 联合省选的题目做法。
A D1T1 / B D1T3 冰火战士
想办法给出一个较为系统地计算能量的方法。
可以发现无论如何能量少的一定会花光，相对地，能量多的一方也只会花那么多。
所以总能量就是 $2\min(E_1,E_2)$。
实质上是找到一个位置，使得前面的冰人能量和后面火人能量的最小值最大。
由于都是前缀和的形式，所以画出来大概类似一个单增一个单减的函数，它们的最小值的最大值在交点处取到。但由于只能取整点处，所以还要求一下周围的，具体实现时是求最大的冰小于火，最小的冰大于等于火。
但是这题数据范围有点大，线段树常数又稍大，考虑树状数组上倍增即可 $O(n\log n)$ 完成。
A D1T2 组合数问题
看到多项式次数那么小，肯定想把它拆开来然后交换求和次序算。
后面那个二项式系数的形式就让人很想往二项式定理凑，拆成幂次相性又不大好，那就转成下降幂形式吧，这个过程可以用第二类斯特林数解决，这里的数据范围允许直接 dp。
转完之后发现确实和组合数发生了奇妙的化学反应，然后就直接二项式定理解决了。
A D1T3 魔法商店
缝合论文题。
考虑到题目给出的是极大线性基，此时删去其中一个数，若可以加入另一个数，那么新加入的数和被删去的数就构成了一个偏序关系。
由于线性基的优秀性质，这样做就可以完整地搞出全部的偏序关系。
剩下就是个保序回归问题，由于各种性质，可以整体二分所有物品的权值，假如当前考虑的物品权值都确定在 $[l,r]$ 之内，我们考虑它们在最优决策下是取 $mid$ 还是 $mid+1$ ，如果是前者，那么它 $\le mid$，否则 $>mid$。跑个最小割即可。
A D2T1 / B D2T2 信号传递
首先 $S$ 这个序列挺憨的，事实上我们只在意它的相邻两位，我们考虑记 $M(i,j)$ 表示在这个序列中出现了多少个 $k$ 满足 $S_k=i,S_{k+1}=j$。
那么我们接下来计算 $i,j$ 填了 $p_i,p_j$，就只需考虑 $M(i,j)$ 和 $M(j,i)$。事实上，若 $p_i$ 大，那么它对答案的贡献是 $(p_i-p_j)M(j,i)+k(p_i+p_j)M(i,j)$，相反的话同理。
这里我们为了方便，将 $p_i,p_j$ 拆开，那么计算一个数的贡献系数就只需考虑它本身。如果不拆开的话，我们计算时就无法得知其它 $p$。
$m$ 的范围挺小的，直觉告诉我们是状压。
由于我习惯用 $S$ 表示状态，所以下文的 $S$ 与题目给出的 $S$ 没有任何关系。
可以看得出，上面的计算答案方式中，我们只需考虑任意两数的大小关系，所以我们依次决定把第 $k$ 个数填在哪里，这样已经填过的数的大小关系对此时答案的增量没有任何贡献，答案贡献只需考虑 $k$ 与集合内的数或集合外的数。
记 $F(S)$ 表示将 $1\sim|S|$ 填在了 $S$ 内，那么我们考虑它是添加了某个数 $x$，那么我们有转移：
其中 $p_x=|S|$，枚举 $x$ 计算后转移是 $O(m^2)$ 的，乘上状态数是 $O(m^22^m)$，怎么优化？
我们感觉要从后面这坨东西入手，不妨记它为 $G(S,x)$，那么对于另一个 $z\in S-x$，比对 $G(S,x)$ 与 $G(S-z,x)$，我们发现它的增量可以 $O(1)$ 计算，于是我们可以在 $O(m2^m)$ 的时间内计算它，那么 $F$ 也可以在这个时间内被计算。
这里的增量应该是：
现在还有个问题，那就是空间不大够用。但是我们发现每次转移只会让 $|S|$ 增加 $1$，对这个过程滚动一下即可，此处不再赘述。
A D2T2 树
通常这类问题有两种解法，第一种是通过儿子的信息得到当前节点信息，第二种是考虑每个节点的祖先的贡献，这里考虑第一种。
那么我们要解决的问题是：合并信息，插入一个数，全局加一，全局异或和。
结合数据范围，我们考虑使用 01 Trie 解决。
由于加一时可能产生的进位是从低位向高位的，所以我们插入时要从低位到高位插入。
合并两个 01 Trie
类似线段树合并。
插入一个数
常规操作。
全局加一
从低位到高位依次考虑，如果是 $0$，就转成 $1$，后面没有进位，否则转成 $0$，然后还有进位，递归下去做即可。
全局异或和
维护子树内数的个数与子树内的异或和（仅考虑子树内的位）。这样在全局加一时可以处理 $0$ 转 $1$ 的情况。
A D2T3 作业题
看到 $\gcd$ 果断枚举一个数 $d$ 然后仅考虑边集为边权都为 $d$ 的倍数的边的情况。
这样算的话，可以把外面的 $\gcd$ 当成常数 $d$ 处理，算完后利用 $\varphi\ast\operatorname{1}=\operatorname{Id}$ 就可以了。
那么现在的问题就是给你一张图，让你求它所有的生成树的边权和的和。
那我们肯定先判它连通不连通，如果不连通就不用算了。
接下来我们容易联想到矩阵树定理，但是普通的矩阵树定理只能求所有生成树边权积的和啊？怎么搞？
事实上这玩意也已经被出烂了，直接令原来的 $M_{i,j}$ 为一个多项式 $1+w_{i,j}x$，我们知道行列式实质上是求一个积和式，这样，我们把乘起来的多项式展开，其一次项系数就是 $\sum w$。
我们只需在 $\bmod{x^2}$ 意义下做乘法和除法，手动乘除即可。
注意常数项出现 $0$ 时的情况，要处理亿点细节。