1. LOJ6405 「ICPC World Finals 2018」征服世界
咋感觉不说原始咋建图的全是胡言乱语/qd 学习了一下这个
先强制每个 \(b\) 都和 \(inf-dep_i\) 匹配，问题中匹配的权值转化为 \(dep_x+dep_y-2dep_{lca}-inf\)，这样子最小费用循环流能够强制每个点都能进行匹配。拆点进行建图：
- \(in_x\to out_x\) 费用 \(-2dep_x\)，容量 \(+\infty\)；
- \(in_x\to in_p\)，其中 \(p\) 是 \(x\) 的所有祖先，费用为 \(0\)，容量 \(\infty\)；
- \(out_p\to in_x\)，其中 \(p\) 是 \(x\) 的所有祖先（包括自己），费用为 \(0\)，容量为 \(\infty\)；
- \(S\to in_x\) 费用为 \(dep_x\) 容量为 \(a_x\)；
- \(in_x\to S\) 费用为 \(dep_x-\infty\) 容量为 \(b_x\)。
有了建模之后模拟费用流就可以解释了。两个堆分别存的是子树到达自己 \(in\) 的路径权值，以及 \(out\) 到达子树的路径权值。退流也能变为这种的形式。
2. CF1392I Kevin and Grid
平面图欧拉定理：\(C+1=V-E+F\)，\(V,E,F,C\) 为点数边数面数连通块数。假设没有碰到边界的连通块数分别为 \(T_1,T_2\)，那么答案就是 \(C_1+T_1-C_2-T_2\)，还有就是注意到每个 \(T_1\) 一定被一个 \(F_2\) 所包围，而唯一不会包含 \(T_1\) 的 \(F_2\) 就是四个点连通的一个面。假设四连通块个数为 \(S_1,S_2\)，也就是 \(T_1+S_2=F_2\)，那么就可以化简式子：
\((V_1-E_1+F_1)+(F_2-S_2)-(V_2-E_2+F_2)-(F_1-S_1)=(V_1-V_2)-(E_1-E_2)+(S_1-S_2)\)
统计各自的点数，边数，以及四点连通面个数。算点数就是 \(a_i+b_j\geq x\) 个数是卷积。边数就是 \(\min(a_i,a_{io+1})+b_j\geq x\)，四点连通面数就是 \(\min_{a_i,a_{i+1}}+\min_{b_j,b_{j+1}}\geq x\)。反过来的也同理。
补：\(T_1\) 一定被一个 \(F_2\) 包围是需要题目里的限制的。只需证明不存在以下形状，从而在边角上的 \(F_2\) 不会断开。
a[1] a[2]
b[1] 1 0
b[2] 0 1
列出不等式相加发现 \(a_1+a_2+b_1+b_2\) 既 \(\geq 2x\) 又 \(<2x\)，矛盾。
3. gcd 矩阵行列式
\(C_{i,j}=\gcd(i,j)\) 求 \(\det C\)，首先欧拉反演得到 \(C_{a,b}=\sum_{i|a,b}\varphi(i)\)，尝试将矩阵 \(C\) 分解，写成 \([i|a][i|b]\varphi(i)\) 发现可以构造 \(A_{a,i}=[i|a]\varphi(i),B_{i,b}=[i,b]\)，那么 \(C=AB\Rightarrow \det C=\det A\det B\)。而 \(A,B\) 均为三角矩阵，行列式分别为 \(\prod \varphi(i),1\)。所以 \(\det C=\varphi(1)\varphi(2)\cdots\varphi(n)\)。
4. 愚蠢的在线法官
做法一：
先看 \(A_i=i\) 咋做。枚举排列 \(p\)，然后 \((-1)^{N(p)}\prod v_{LCA(i,p_i)}\) 贡献到答案里。和树有关的排列问题套路是设 \(f_{i,j}\) 表示 \(i\) 的子树中有 \(j\) 个位置还没有确定的权值总和（它们之间的权值任意排 不代表不计算它们的权值）。初始化时 \(p_i=i\)，分为自己已经确定和还未确定。
注意到 \(j\geq 2\) 时，swap 两个 \(j\) 中的 \(a_x,a_y\)，得到权值相同（因为 LCA 和这两个点没关系 只和 \(i\) 有关系）且正负相反的两个方案。所以 \(j\geq 2\) 时 \(f_{i,j}=0\)。
那么仅考虑 \(f_{u,0/1},f_{v,0/1}\) 之间的合并，首先卷起来得到 \(g_{0,1,2}\)，其中 \(0,1\) 不能再做啥操作直接贡献给 \(f'_{u,0}\)，对于 \(2\) 存在两种方式，swap 并且两个都确定下来，swap 并且只确定一个，分别贡献给 \(f'_{u,0},f'_{u,1}\)
对于一般的情况也是一样做，如果出现了两个相同的 \(A\) 答案肯定为 0，然后只对出现了的 \(x\) 进行 \(p_x=x\) 的初始化就行。
\(A\) 按 dfs 排序之后 det 不变，因为 swap \(A_i,A_j\) 相当于同时交换两行两列。此时考虑树上差分之后，一个点相当于要对矩阵进行一个矩形加，考虑矩阵的二维差分行列式不变（二维差分线性变换矩阵行列式为二维前缀和线性变换矩阵的倒数，均为 1），转化成四个单点加 B[l][l]++,B[r+1][r+1]++,B[l][r+1]--,B[r+1][l]--。
从而联想到这是基尔霍夫矩阵，去掉 \(k+1\) 行 \(k+1\) 列求行列式，相当于连边 \(l\to r+1\)，求生成树个数。由于 dfs 序区间两两不交，肯定不存在同胚于 \(K_4\) 的子图，广义串并联图方法即可。
5. P5548 [BJ United Round #3] 押韵 / LOJ 6696 复读机 加强版
这里推的时候用 P5548 [BJ United Round #3] 押韵 的 \(n,k,d\)。
\[[x^{nd}]\left(\sum_{i=0}\frac{x^{id}}{(id)!}\right)^k \]\(\sum\limits_{i=0}[d|i]\frac{x^i}{i!}\) 单位根反演推一下是 \(\frac{1}{d}\sum\limits_{i=0}^{d-1}e^{w^ix}\)，\(w\) 是 \(d\) 次单位根。那么所求答案就是
\[\frac{1}{d^k}[x^{nd}]\left(\sum_{i=0}^{d-1}e^{w^ix}\right)^k \]尝试把里面那个展开，考虑 \(d=6\) 时用 \(e^A=e^{w^0x},e^B=e^{w^1x}\) 表示所有的 \(e^{w^k}\)：\(e^A,e^B,e^{B-A},e^{-A},e^{-B},e^{A-B}\)，还元 \(y=e^A,z=e^B\)，那么展开后的每一项都能表示成 \(y^iz^j=e^{(i+jw)x}\)，从而转化成求 \(k^2\) 次快速幂。
（为了方便后面用 \(x,y\) 代替原来的 \(y,z\)）
那么现在就是算 \((x+y+x^{-1}y+x^{-1}+y^{-1}+xy^{-1})^k\)，D-Finite，是个二维的整式递推，手算一下：令其为 \(G(x,y)=F(x,y)^k\)，对 \(x\) 求偏导：
\[\frac{\partial}{\partial x}G(x,y)=kF(x,y)^{k-1}(1-x^{-2}y-x^{-2}+y^{-1}) \\ F(x,y)\frac{\partial}{\partial x}G(x,y)=kG(x,y)(1-x^{-2}y-x^{-2}+y^{-1}) \]令 \(g_n\) 为 \([x^n]G(x,y)\) 是一个关于 \(y\) 的多项式，上式两边提取 \([x^n]\) 那么有：
\[(1+y^{-1})g'_{n-1}+(y+y^{-1})g'_n+(y+1)g'_{n+1}=k(1+y^{-1})g_n-k(1+y)g_{n+2} \\ n(1+y^{-1})g_{n}+(n+1)(y+y^{-1})g_{n+1}+(n+2)(y+1)g_{n+2}=k(1+y^{-1})g_n-k(1+y)g_{n+2} \\ (n-k)(1+y^{-1})g_{n}+(n+1)(y+y^{-1})g_{n+1}+(n+2+k)(y+1)g_{n+2}=0 \]换元 \(n\leq n+2\) 就得到比较好看的递推式了。先二项式定理展开得 \(g_{-k}\) 再逐个递推即可。
\(d=3,4\) 也是一样推，\(d=2\) 直接二项式定理展开，\(d=1\) 就是 \(k^n\)。
6. 「2021 集训队互测」抽奖机
用 \(n\) 维，每维度大小为 3 的多项式（\(n\) 位三进制数）描述问题。对于状态 \(S\) 其系数 \(F_{S}=\sum\limits_{i=1}^m[x=a_i\wedge y=b_i]\)。那么 \(F^k\) 即为答案，其中乘法为对应位上长度为 3 的循环卷积。
对于高维循环卷积的形式，我们知道实际上就是对每一维度单独作 dft 就是这个高维的 dft，也就是每一位贡献系数的乘积就是总的系数（仿照 fwt 理解，其实就是张量积）。知道 \(S\to T\) 的贡献系数实际上就是 \(\prod\limits_{i=1}^n w_3^{S_iT_i}\)。而其逆变换就是正变换贡献系数取倒数，最后再乘 \(\frac{1}{3^n}\)。
记 \(a,b\) 为 1,2 的数量。\(a,b\) 相同，那么 \(F\) 和 \(dft(F)\) 也相同。那就尝试怎样通过 \(G_{a,b}\) 得到 dft 后的 \(G_{c,d}\)。这里 \(G_{a,b}\) 指的是 1,2 数量为 \(a,b\) 的 \(F\) 个数，后者是 1,2 数量为 \(a,b\) 的 \(dft(F)\) 的值。
考虑最终的每个 0,1,2 初始都是啥，容易列出来贡献系数是 \([x^ay^b](1+x+y)^{n-c-d}(1+wx+w^2y)^c(1+w^2x+wy)^d\)。
枚举 \(c,d\)，那么每次就是乘除一个简单多项式，可以做到单次 \(\mathcal{O}(n^2)\)，这样总的复杂度就是 \(\mathcal{O}(n^4)\)。
卡常/fn Code
7. 分层图
考虑类似插头 dp，\(f_{x,i}\) 表示考虑完了前 \(x\) 层，在第 \(x\) 层上有 \(i\) 对插头往下延伸。列出转移矩阵之后矩阵快速幂就行了。这里需要注意的地方是单点必须和某个东西连起来。考虑 \(i\) 对 \(j\) 的贡献，枚举有 \(k\) 对插头是不接在一起的，那么剩下的 \((i-k)\) 对插头就和单点一样必须和其它的连在一起，这样方案数就很好用组合数算了。另一个思路是钦定有 \(k\) 个单点是单独的，去容斥。总之都是三方算一下贡献系数然后矩阵快速幂。
8. 《关于因为与去年互测zjk撞题而不得不改题这回事》
考虑暴力在 Trie 上咋做。往下递归的时候先看 1 子树 size 是否 \(\geq m\)，如果是的话往右递归，否则往左递归，并且把右子树中的 \(<m\) 个插到左子树中。这样就发现其实只有最大的 \(m\log V\) 个有用。考虑每次找出下一个第 ? 大的东西，那就是超级钢琴，重链剖分搞个 ST 表，初始把 log 个重链 push 到堆里面，每次取出一个之后再把最大值两侧的区间 push 进去。
另一个实现是卡卡空间搞个树上主席树。另另一个实现是线段树套链表，按照权值插入，将 \(dfn_i\) 到线段树根上所有节点的链表都 insert 当前权值，查的时候就重剖把 log^2 个链表拉出来，再拿个堆维护表头实现归并就行。
标签：回眸,2024.2,Code,frac,矩阵,geq,varphi,终肯,权值 From： https://www.cnblogs.com/do-while-true/p/17955860