高爸很久前教我的技巧，现在突然想起来，正好记录一下。
线性求欧拉数单项。
求长度为 n 的排列恰有 m 个降低的方案数。每出现一个 p_i>p_{i+1} 即为一个降低。
首先先把问题变为求有严格小于 m 个降低的概率，差分一下即可。
把排列映射到 [0,1] 间的随机实数。由于正好取到某个点的概率为 0，所以并不需要很在意边界问题。设这些实数为 a_{1\dots n}。我们要求的就是 a 有严格小于 m 个降低的概率。
我们把每个 a_i 都放到一个长度为 1 的环上，然后按照 0\rightarrow a_1\rightarrow a_2\rightarrow\dots\rightarrow a_n 的顺序顺时针地在环上移动。
显然每次走的长度也是一个 [0,1] 间的随机实数。设第 i 次走的长度为 b_i。此时可以把排列有严格小于 m 个降低这个条件转化为 \sum b_i\le m。
我们可以从离散的角度考虑这个问题，设 V 为 [0,1] 间的实数个数（这样的表述并不严谨，但易于理解）。
问题变为了 n 个 [1,V] 间的随机整数，它们的和 \le mV 的概率。我们要求的是 V 趋向于 +\infty 时的值。
对于一个比较正常的 V，这是一个经典的 容斥原理 + 插板法 解决的问题，可以列出式子：
\dfrac{1}{V^n}\sum\limits_{i=0}^m(-1)^i\dbinom{n}{i}\dbinom{(m-i)V}{n}
$$\dfrac{1}{n!}\sum\limits_{i=0}^m(-1)^i\dbinom{n}{i}(m-i)^n$$
于是就做完了！
---
给定 $a,b,p,k$，其中 $p$ 是奇质数。求 $n$ 满足 $a^n\equiv b\pmod{p^k}$。
暴力做法是 exBSGS，时间复杂度 $O(\sqrt{p^k})$。这里提供一种更优的做法。
先特判掉 $p|a$ 的情况。剩下的情况一定满足 $\gcd(a,p)=\gcd(b,p)=1$。
求出 $p^k$ 的一个原根 $g$，问题转化为求 $n$ 满足 $g^n\equiv a\pmod{p^k}$。
我们考虑在 $p$ 进制下按位进行调整。
先求出 $m$ 满足 $g^m\equiv a\pmod p$。
初始时令 $n=m$，此时只有 $p^0$ 位是正确的。
从小到大枚举 $i\in[1,k)$，每次需要将 $[0,i]$ 中的位全部调整正确。
考虑一个数 $g^{\varphi(p^i)}$，这个数在 $\bmod p^i$ 意义下一定是 $1$，并且在 $\bmod p^{i+1}$ 意义下一定不是 $1$。
求出 $b_1,b_2,b_3$ 分别表示 $a$，当前的 $g^n$，$g^{\varphi(p^i)}$ 这三个数的 $p^i$ 位。我们希望将 $n$ 加上若干个 $\varphi(p^i)$ 使得 $p^i$ 位被调整正确。
设 $n$ 加上了 $c\times\varphi(p^i)$，可以得到
$$b_2+ab_3c\equiv b_1\pmod p$$
因为 $p$ 是质数，且这些数都不会是 $p$ 的倍数，所以一定有逆元，可以得到
$$c=\dfrac{b_1-b_2}{ab_3}\pmod p$$
直接按照这个式子求出 $c$，然后执行 $n\leftarrow n+c\times\varphi(p^i)$ 即可。
时间复杂度 $O(\sqrt{p}+k\log p)$。
---
$\mathbb{Z}_2$ 线性空间求交。
设给定的两个线性空间分别为 $V_1,V_2$。
设 $V_3,V_4$ 为两个新的线性空间。初始 $V_3=V_1$，$V_4$ 为空。
设 $S_1,S_2,S_3,S_4$ 分别为 $V_1,V_2,V_3,V_4$ 的一组基。
我们钦定在任意时刻 $S_1\subseteq S_3\subseteq S_1\bigcup S_2$。
依次考虑 $S_2$ 中的每一个向量，设当前向量为 $a$，并进行讨论：
- 如果 $a\in V_3$，那么我们找到 $S_3$ 中的若干元素表示出 $a$。我们找出这个表示中所有在 $S_1$ 中的向量，设它们的和为 $b$，可以证明 $b\notin V_4$，并将 $b$ 加入 $S_4$。
- 如果 $a\notin V_3$，那么将 $a$ 加入 $S_3$。
有 $V_4=V_1\bigcap V_2$，而 $V_3=\operatorname{span}(V_1\bigcup V_2)$。
---
设 $F(x)$ 为 Catalan 数的生成函数，求 $[x^n]F^m(x)$。
这个问题可以直接使用拉格朗日反演，但我们在这里给出一种利用组合意义的方法。
接下来我们默认二叉树无标号，但区分左右儿子。
考虑从根开始不断向左走得到一条点数为 $m-1$ 的链，我们需要在这 $m-1$ 个点的右儿子和最后一个点的左儿子处挂一棵子树，要求这些子树的大小之和恰好为 $n$。显然这个方案数就等于我们要求的式子。
考虑这个问题的另一种形式：共有 $n+m-1$ 个点，并且满足极左链长度 $\ge m-1$ 的二叉树个数。
将二叉树转成括号序列，可以发现极左链长度 $\ge m-1$ 等价于括号序列中最开始的 $m-1$ 个都是左括号。这个方案数就是 $(m-1,m-1)\rightarrow (2(n+m-1),0)$ 每次往右上或者右下走一步，并且不穿过 $y=0$ 的方案数。
直接使用经典的反射容斥可以得到答案为：
$$\dbinom{2n+m-1}{n}-\dbinom{2n+m-1}{n-1}$$
---
给定两个 $n\times n$ 的矩阵 $A,B$，求 $|Ax+B|$。
直接插值的时间复杂度是 $O(n^4)$。这里我们介绍一种 $O(n^3)$ 的做法。
显然有：
$$|P||Ax+B||Q|=|PAQx+PBQ|$$
其中 $P$ 对应初等行变换，$Q$ 对应初等列变换。
因此我们可以同时对 $A,B$ 进行消元。
先将 $A$ 消成 $01$ 对角矩阵，在 $B$ 中也作对应的变换。
然后我们尝试在保持 $A$ 为 $01$ 对角矩阵的前提下将 $B$ 消成上海森堡矩阵。
依次考虑每个 $i\in [2,n]$，我们希望将 $B_{i+1\dots n,i-1}$ 都消成 $0$。
如果 $\exists t\in [i,n],B_{t,i-1}\neq 0$ 满足 $A_{t,t}=0$，那么我们可以进行如下变换：
- 交换第 $i,t$ 行，交换第 $i,t$ 列。
- 对于每个 $j\in (i,n],B_{j,i-1}\neq 0$，设 $B_{j,i-1}=w$ 将第 $j$ 行加上第 $i$ 行的 $-\dfrac{w}{B_{i,i-1}}$ 倍。
如果 $\forall t\in [i,n],B_{t,i-1}\neq 0$ 满足 $A_{t,t}=1$，那么我们可以进行如下变换：
- 交换第 $i,t$ 行，交换第 $i,t$ 列。
- 对于每个 $j\in (i,n],B_{j,i-1}\neq 0$，将第 $j$ 行加上第 $i$ 行的 $-\dfrac{w}{B_{i,i-1}}$ 倍，将第 $i$ 列加上第 $j$ 列的 $\dfrac{w}{B_{i,i-1}}$ 倍。
可以发现，这样的消元方法不会破坏 $A$ 的性质。
最后对上海森堡矩阵使用 dp 计算行列式即可。注意消元过程中可能会产生一些系数。时间复杂度 $O(n^3)$。
---
$n\times n$ 的矩阵 $A$ 满足 $A_{i,j}=b^{(i-1)a_j}$。求 $A^{-1}$。保证 $A$ 可逆。
显然有 $(A^{-1})^T=(A^T)^{-1}$，我们考虑如何求出后者。
设列向量 $\alpha,\beta$ 满足 $A^T\alpha=\beta$。显然 $(A^T)^{-1}\beta=\alpha$。
由于 $A$ 的特殊性，我们可以将 $\alpha$ 看作一个 $n-1$ 次多项式的系数。
即 $f(x)=\sum\limits_{i=0}^{n-1}\alpha_{i+1}x^i$。此时 $\beta_i=f(b^{a_i})$。
因此 $(A^T)^{-1}$ 就对应了从 $n$ 个点值还原为系数的矩阵，使用拉格朗日插值公式即可 $O(n^2)$ 求出。
---
给定 $a,b,n,p$，求 $\min\limits_{0\le x\le n}\{(ax+b)\bmod p\}$。
考虑 $y=(ax+b)\bmod p$ 随 $x$ 的变化方式。
初始 $y=b$，每次增加 $a$，如果当前 $\ge p$ 就减去 $p$。减去 $p$ 之后会到达一个 $[0,a)$ 内的点。
如果当前到达了 $[0,a)$，那么下一次到达 $[0,a)$ 时一定有 $y'=(y-p)\bmod a$。
而我们可以发现，最小值一定在 $x=0$ 或某次减去 $p$ 时取到，因此我们只需要考虑 $y=b$ 或 $y\in [0,a)$ 时的情况。
我们可以尝试将问题按照类似于欧几里得算法的方式递归为一个子问题。
设 $f(a,b,c_1,c_2,n,p)$ 为问题的答案。其中 $c_1$ 表示当前这一步不会减去 $p$ 时产生的代价，$c_2$ 表示当前这一步会减去 $p$ 时产生的代价，要求总代价不超过 $n$。我们要求的即为 $f(a,b,1,1,n,p)$。
不妨设 $b<p$。
考虑以如下方式递归：
- 如果 $n<0$，那么 $f(a,b,c_1,c_2,n,p)=+\infty$。
- 如果 $a\ge p$，那么 $f(a,b,c_1,c_2,n,p)=f(a\bmod p,b,c_2,c_2,n,p)$。
- 如果 $a\le b$，那么设 $t=\left\lceil\dfrac{p-b}{a}\right\rceil$，有 $f(a,b,c_1,c_2,n,p)=\min\{b,f(a,b,c_1,c_2,n-(t-1)c-d,p)\}$。
- 否则设 $t=\left\lfloor\dfrac{p}{a}\right\rfloor$，有 $f(a,b,c_1,c_2,n,p)=f(a-(a\bmod p),b,c_1(t+1)+c_2,c_1t+c_2,n,a)$。
可以发现这样做的时间复杂度为 $O(\log p)$。
---
Powerful Number 筛
定义 Powerful Number 为所有质因子幂次都 $\ge 2$ 的数。
我们要求积性函数 $f$ 的前缀和，设 $g,h$ 为积性函数满足 $f=gh$。
可以发现 $f(p)=g(1)h(p)+g(p)h(1)$，即 $f(p)-g(p)=h(p)$。
而我们又有：
$$\sum\limits_{i=1}^nf(i)$$
$$=\sum\limits_{i=1}^n\sum\limits_{j|i}g(i)h\left(\dfrac{i}{j}\right)$$
$$=\sum\limits_{i=1}^nh(i)\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(j)$$
我们选择一个合适的 $g$，使得 $f(p)=g(p)$，即质数处取值相等，并且 $g$ 的前缀和可以快速计算。
此时可以发现 $h$ 只在 Powerful Number 处取值不为 $0$。只需要枚举 $[1,n]$ 中所有 Powerful Number 作为 $i$ 计算答案即可。
$[1,n]$ 中的 Powerful Number 个数为 $O(\sqrt n)$。
---
求 $\prod\limits_{i=0}^{n-1}(1+\omega_n^i)$。可以证明答案为整数。
考虑单位根的定义，有：
$$x^n-1=\prod\limits_{i=0}^{n-1}(x-\omega_n^i)$$
代入 $x=-1$ 可以得到：
$$(-1)^n-1=(-1)^n\prod\limits_{i=0}^{n-1}(1+\omega_n^i)$$
$$\prod\limits_{i=0}^{n-1}(1+\omega_n^i)=(-1)^{n+1}+1$$
---
给定一张无向图 $G=(V,E),n=|V|,m=|E|$，每个点 $u$ 的点权 $a_u$ 在 $[0,1]$ 内等概率随机，求 $E(\max\limits_{(u,v)\in E}\{a_u+a_v\})$。
算法一：
设 $f(x)$ 表示 $\forall (u,v)\in E,a_u+a_v\le x$ 的概率。
不妨考虑固定 $x>1$ 时怎么求 $f(x)$，$x\le 1$ 时是类似的。
将 $u$ 按照是否满足 $a_u\le\dfrac{x}{2}$ 分为两部分考虑。
设 $b_u=\min\{a_u,x-a_u\},c_u=[a_u>\dfrac{x}{2}]$。
将所有点按照 $b_u$ 递增排序。设排完序的结果为 $p_{1\dots n}$。
对于 $u,v$ 满足 $b_u<b_v$，可得：
- 如果 $c_u=c_v=0$，那么 $a_u+a_v\le x$。
- 如果 $c_u=0,c_v=1$，那么 $a_u+a_v\le x$。
- 如果 $c_u=1,c_v=0$，那么 $a_u+a_v>x$。
- 如果 $c_u=c_v=1$，那么 $a_u+a_v>x$。
整合一下即为 $a_u+a_v\le x$ 当且仅当 $c_u=0$。
因此我们相当于要枚举满足以下条件的二元组 $(p,c)$：
- $\forall i<j$，如果 $c_{p_i}=1$，那么 $(p_i,p_j)\notin E$。
此时 $b$ 需要满足：
- $\forall i\in [1,n),b_{p_i}\le b_{p_{i+1}}$。
- $\forall u$，如果 $c_u=1$，那么 $b_u\in [0,\dfrac{x}{2}]$，否则 $b_u\in [x-1,\dfrac{x}{2}]$。
设 $t$ 为最小的数满足 $c_{p_{t+1}}=1$，如果不存在则 $t=n$。
此时 $b$ 对应的概率为：
$$\sum\limits_{i=0}^t\dfrac{1}{i!(n-i)!}(x-1)^i(1-\dfrac{x}{2})^{n-i}$$
这是一个关于 $x$ 的 $O(n)$ 次多项式，并且只与 $t$ 有关。
因此我们可以枚举 $t$，然后使用 dp 在 $O(n2^n)$ 时间内求出 $t$ 对应的 $(p,c)$ 的方案数，然后再利用每个 $t$ 的方案数在 $O(\operatorname{poly}(n))$ 的时间复杂度求出 $f(x)$。
总时间复杂度为 $O(n^22^n)$。
算法二：
设 $f(G,x,y)$ 表示 $\forall u,a_u\le x$ 且 $\forall (u,v)\in E,a_u+a_v\le y$ 的概率。
我们可以归纳地认为 $f(G,x,y)$ 是关于 $x,y$ 的 $O(n)$ 次二元多项式。
如果 $x\le\dfrac{y}{2}$，那么显然 $f(G,x,y)=x^n$。只需要考虑 $x>\dfrac{y}{2}$ 的情况。
不妨设 $x\le y$。
设 $t=\max\limits_u\{a_u\}$。
显然 $t\le\dfrac{y}{2}$ 时的贡献为 $\left(\dfrac{y}{2}\right)^n$。
考虑 $t>\dfrac{y}{2}$ 的情况。枚举点 $u$，并要求 $a_u=t$。
对于 $u$ 的所有相邻点 $v$，一定有 $a_v\le y-t$。
而我们又知道剩下的所有点权都 $\le t$，因此这些 $v$ 不会对其它点产生影响，可以归纳到一个子问题。
具体地，设 $G_u$ 表示从 $G$ 中删除 $u$ 及其所有相邻点之后得到的新图，那么有：
$$f(G,x,y)=\left(\dfrac{y}{2}\right)^n+\sum_u\int_{\frac{y}{2}}^{x}f(G_u,t,y)(y-t)^{deg_u}\text{d}t$$
直接插值 + 状压 dp 即可做到 $O(n^32^n)$。
当 $G$ 不连通时可以直接拆成多个连通块答案相乘，否则再按照上述方法递归计算。这个算法时间复杂度未知，但实际效率非常高。
---
求有多少个长度为 $2n$ 的括号序列中恰好有 $m$ 对括号相邻。
考虑二项式反演，钦定 $i$ 对相邻的括号，则答案为：
$$
\sum\limits_{i=m}^n(-1)^{i-m}\dbinom{i}{m}C_{n-i}\dbinom{2n-i}{i}
$$
其中 $C$ 为卡特兰数。
展开组合数可得：
$$
=\sum\limits_{i=m}^n(-1)^{i-m}\dfrac{i!(2n-2i)!(2n-i)!}{m!(i-m)!(n-i)!(n-i+1)!i!(2n-2i)!}
$$
$$
=\sum\limits_{i=m}^n(-1)^{i-m}\dfrac{(2n-i)!}{m!(i-m)!(n-i)!(n-i+1)!}
$$
$$
=\dfrac{(n-1)!}{m!(n-m)!}\sum\limits_{i=m}^n(-1)^{i-m}\dbinom{2n-i}{n-1}\dbinom{n-m}{i-m}
$$
$$
=\dfrac{\dbinom{n}{m}}{n}\sum\limits_{i=0}^{n-m}(-1)^i\dbinom{2n-m-i}{n-1}\dbinom{n-m}{i}
$$
$$
=\dfrac{\dbinom{n}{m}}{n}[x^{n-m+1}]\dfrac{1}{(1-x)^n}(1-x)^{n-m}
$$
$$
=\dfrac{\dbinom{n}{m}}{n}[x^{n-m+1}]\dfrac{1}{(1-x)^m}
$$
$$
=\dfrac{\dbinom{n}{m}\dbinom{n}{m-1}}{n}
$$
---
求线性拟阵 $\alpha_1\dots\alpha_n$ 的对偶。
不妨设 $\alpha_1\dots\alpha_r$ 为一组基。
对于 $i\in [1,n-r]$，考虑 $\alpha_{r+i}$ 的表出 $\alpha_{r+i}=
\sum\limits_{j=1}^r k_j\alpha_j$，则我们令 $\beta_{j,i}=k_j$。
再令 $\beta_{r+i}=e_i$。
则 $\beta_1\dots\beta_n$ 为 $\alpha_1\dots\alpha_n$ 的对偶线性拟阵。
---
令
$$
f(a,b)=\sum\limits_{i=0}^nw_i\dbinom{i}{a}\dbinom{n-i}{b}
$$
给定 $w_0\dots w_n$，对于所有 $1\le a,b\le n$ 求 $f(a,b)$。
由组合数定义有：
$$
(i+1)\dbinom{i}{a}\dbinom{n-i}{b}=(a+1)\dbinom{i+1}{a+1}\dbinom{n-i}{b}
$$
$$
=(a+1)\left(\dbinom{i}{a}+\dbinom{i}{a+1}\right)\dbinom{n-i}{b}
$$
$$
(n-i+1)\dbinom{i}{a}\dbinom{n-i}{b}=(b+1)\dbinom{i}{a}\dbinom{n-i+1}{b+1}
$$
$$
=(b+1)\dbinom{i}{a}\left(\dbinom{n-i}{b}+\dbinom{n-i}{b+1}\right)
$$
两式相加得：
$$
(n+2)\dbinom{i}{a}\dbinom{n-i}{b}
$$
$$=(a+b+2)\dbinom{i}{a}\dbinom{n-i}{b}+(a+1)\dbinom{i}{a+1}\dbinom{n-i}{b}+(b+1)\dbinom{i}{a}\dbinom{n-i}{b+1}$$
移项得：
$$
(n-a-b)\dbinom{i}{a}\dbinom{n-i}{b}
$$
$$=(a+1)\dbinom{i}{a+1}\dbinom{n-i}{b}+(b+1)\dbinom{i}{a}\dbinom{n-i}{b+1}
$$
因此有：
$$
(n-a-b)f(a,b)=(a+1)f(a+1,b)+(b+1)f(a,b+1)
$$
显然有边界 $f(a,n-a)=1$，递推计算即可。
时间复杂度 $O(n^2)$。