TriCk

· · 个人记录

转化成对应前缀和的一段折线考虑。（/bx @Iceturky）

维护前后缀乘积（/bx @Iceturky）

求出 inv_i\times i \equiv 1\pmod p，考虑计算 p=ri+t,t<i，则 ri\equiv -t,i\equiv-\frac tr,inv_i\equiv -\frac rt\pmod p，所以 inv_i=(p-\lfloor\frac pi\rfloor)inv_{p\bmod i}\bmod p。

使用可持久化值域线段树维护哈希值，从而快速求出最长公共前后缀，进行比较和更新。

当树上每个连通块作为根计算答案时，可用每个点为根计算一遍并累加，再减去以所有边连接的两个点合成大点作为个根的答案，这样每个连通块的贡献只有 1。

当凸包的横纵坐标均为 [0,n] 内的整数时，凸包的点数为 O(n^{\frac23})。

竞赛图强连通缩点后的 DAG 呈链状, 前面的所有点向后面的所有点连边；

竞赛图存在哈密顿回路和哈密顿路径。

多次询问时可预处理转移矩阵的 2^k 次方，每次询问做 \log n 次向量乘矩阵，复杂度为 O(k^3\log n+qk^2\log n)。

若要最小化排列 p 的字典序，可考虑其逆排列 q（p_{q_i}=i,q_{p_i}=i），并求出倒序字典序最大的 q，再还原回 p 即为答案。

证明考虑首先最小化 p_1，也就是 q 中 1 的位置，以此类推。则 q 从后往前考虑，只能填 1 时再填 1，以此类推。

实在困难，记一下。代码选自 P11210。

int getp(int u,int l,int r,int L)
{
    if(r<L) return n+1;
    if(l>=L)
    {
        if(wy[u]<L) return n+1;
        if(l==r) return l;
    }
    int rl=getp(Lc,L);
    return rl==n+1?getp(Rc,L):rl;
}

每次随机选一个左部未匹配点 x（可初始随机一个排列）,再随机其连着的某点 y 求增广路，期望复杂度 \mathcal O(n\ln n)。

二分图最大匹配数与最小点覆盖数相等，最大独立集为最小点覆盖的补集。

构造一组最小点覆盖，可在最大匹配 M 的基础上，找到所有左部未匹配点通过交错路不可达的左部点和可达的右部点，即为一组最小点覆盖。在最大匹配的网络流图上即残量网络中 S 不可达的左部点和可达的右部点。

在指数上可以拆成卷积形式。 - 26.04.16 斯特林反演 实在不懂，记个结论先。大概就是 $g$ 乘第二类斯特林数求和得到 $f$ 的话，$f$ 乘第一类斯特林数和 $-1$ 的差值次方可得 $g$，$[0,n],[n,m]$ 求和都行。 $\displaystyle f(n)=\sum\limits_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k)\Longleftrightarrow g(n)=\sum\limits_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k)

行列式为 \sum_{p}(-1)^{c(p)} \prod a_{i,p_i}，有性质为交换两行时行列式取反，一行/列加上另一行/列乘某系数不改变行列式值。

于是类似高斯消元消成上三角矩阵，此时行列式即对角线 a_{i,i} 乘积。高斯消元可通过类似辗转相除，每两次使得 a_{i,i} 减半，复杂度 \mathcal O(n^3+n^2\log p)。

矩阵树定理为定义度数矩阵为 D，邻接矩阵为 A，则无向图生成树数量为 L=D-A 对任意 k 将第 k 行和第 k 列去掉后的行列式。

对于有向图，内向树将 D 改为出度，外向树将 D 改为出入度后同理。

BEST 定理：有向欧拉图欧拉回路数量为 T\prod (d_u-1)!，若固定起点还要枚举首条边，乘上 d_s。

$f_n=\sum_{i=n}^m{i\choose n} g_i\Longleftrightarrow g_n=\sum_{i=n}^m(-1)^{i-n}{i\choose n} f_i$。 可将左式代入右式的 $f_i$ 再交换求和号，通过组合数性质证明。 - 26.05.17 扩展 min-max 容斥 $\text{kthmax}(S)=\sum_{T\subseteq S,\left|T\right|\ge k} (-1)^{\left|T\right|-k}{\left|T\right|-1\choose k-1} \min(T)$。 先认为容斥系数为 $w(\left|T\right|)$，然后与 $f_i=[i=k]$ 二项式反演即可推出。 - 26.06.03 竞赛图三元环数量 答案为 ${n\choose 3} -\sum {d_i\choose 2}$，即减去三点不成环的方案数。