从头开始学组合数学，所以里面有大量很水的芝士。
抄袭来源
https://blog.csdn.net/litble/article/details/75913032
http://lanqi.org/skills/10939/
https://www.cnblogs.com/COLIN-LIGHTNING/p/8450053.html
http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion
https://blog.csdn.net/werkeytom_ftd/article/details/74701513
https://www.cnblogs.com/ivorysi/p/9058093.html
https://www.cnblogs.com/zwfymqz/p/8869956.html
https://www.cnblogs.com/asuldb/p/10917496.html
组合数一些神奇的性质
大部分 是从抄袭来源第一篇里整理来的。
1.$\sum\limits_{i=0}^mC_{n+i}^i=C_{m+n+1}^m$
证明：
$\sum\limits_{i=0}^mC_{n+i}^i$
$=C_n^0+C_{n+1}^1+C_{n+2}^2+…+C_{n+m}^{m}$
$=C_{n+1}^0+C_{n+1}^1+C_{n+2}^2+…+C_{n+m}^m$
$=C_{n+2}^1+C_{n+2}^2+…C_{n+m}^m$
$=C_{n+m+1}^m$
2.$C_m^nC_n^r=C_m^rC_{m-r}^{n-r}$
证明：
$C_m^nC_n^r$
$=\dfrac{m!}{n!(m-n)!}\dfrac{n!}{r!(n-r)!}$
$=\dfrac{m!}{(m-n)!}\dfrac{1}{r!(n-r)!}$
$=\dfrac{m!}{r!(m-r)!}\dfrac{(m-r)!}{(m-n)!(n-r)!}$
$=C_m^rC_{m-r}^{n-r}$
也可以考虑它的组合含义：
$C_m^nC_n^r$就是从大小为$m$的集合里选出大小为$n$的子集，再从这个子集选出大小为$r$的子集。
倒过来算，先选大小为$r$的子集，再算出它被多少个大小为$n$的子集包含，即$C_m^rC_{m-r}^{n-r}$
3.$(x+1)^n=\sum\limits_{i=0}^nC_n^ix^i$
根据二项式定理显然。
4.$\sum\limits_{i=0}^n(-1)^iC_n^i=0$
若$n$为奇数，根据$C_n^m=C_{n}^{n-m}$显然
若$n$为偶数，用递推公式展开：
$\sum\limits_{i=0}^n(-1)^iC_n^i$
$=C_n^0-C_n^1+C_n^2-C_n^3+…+C_n^n$
$=C_{n-1}^0-C_{n-1}^0-C_{n-1}^1+C_{n-1}^1+C_{n-1}^2-…+C_{n-1}^{n-1}$
$=0$
$update$：
被抄袭来源误导了，直接用二项式定理就行：
$\sum\limits_{i=0}^n(-1)^iC_n^i$
$=\sum\limits_{i=0}^nC_n^i(-1)^i1^{n-i}$
$=(-1+1)^n$
$=0$
5.$C_{m+n}^r=\sum\limits_{i=0}^rC_m^iC_n^{r-i}$
这玩意叫范德蒙恒等式。
把$m+n$分成两组，分别有$m$个物品和$n$个物品，枚举在这两组中各取几个。
特别的，当$r=n$时，根据$C_n^m=C_n^{n-m}$，有：
$C_{m+n}^n=\sum\limits_{i=0}^nC_m^iC_n^i$
更特别的，当$r=m=n$时，有：
$C_{2n}^n=\sum\limits_{i=0}^nC_n^iC_n^{n-i}=\sum\limits_{i=0}^n(C_n^i)^2$
6.$nC_m^n=mC_{m-1}^{n-1}$
证明：
$nC_m^n$
$=n\dfrac{m!}{n!(m-n)!}$
$=m\dfrac{(m-1)!}{(n-1)!(m-n)!}$
$=mC_{m-1}^{n-1}$
7.$\sum\limits_{i=1}^niC_n^i=n2^{n-1}$
证明：
$\sum\limits_{i=1}^niC_n^i$
$=\sum\limits_{i=1}^ni\dfrac{n!}{i!(n-i)!}$
$=n\sum\limits_{i=1}^n\dfrac{(n-1)!}{(i-1)!(n-i)!}$
$=n\sum\limits_{i=1}^nC_{n-1}^{i-1}$
$=n\sum\limits_{i=0}^{n-1}C_n^i$
$=n2^{n-1}$
8.$\sum\limits_{i=1}^ni^2C_n^i=n(n+1)2^{n-2}$
证明：
$\sum\limits_{i=1}^ni^2C_n^i$
$=\sum\limits_{i=1}^ni^2\dfrac{n!}{i!(n-i)!}$
$=n\sum\limits_{i=1}^ni\dfrac{(n-1)!}{(i-1)!(n-i)!}$
$=n\sum\limits_{i=0}^{n-1}(i+1)C_n^i$
$=n\left(\sum\limits_{i=0}^{n-1}iC_n^i+\sum\limits_{i=0}^{n-1}C_n^i\right)$
$=n\left((n-1)2^{n-2}+2^{n-1}\right)$
$=n(n+1)2^{n-2}$
9.$\sum\limits_{i=0}^nC_i^m=C_{n+1}^{m+1}$
考虑组合意义。从$n+1$个物品里选$m+1$个，枚举最后一个选的位置为$i+1$，在前$i$个里选$m$个，即$\sum\limits_{i=0}^nC_i^m$。
10.$\sum\limits_{i=0}^nC_n^i[2|i]=\sum\limits_{i=0}^nC_n^i[2\nmid i]=2^{n-1}$
考虑组合意义，在$n$个物品里选偶数个，先在前$n-1$个里任选，选了偶数个第$n$个就不选，选了奇数个就选第$n$个。
容斥
最近刷了刷容斥和二项式反演，感觉有点理解了，于是重写了一遍。
定义
容斥就是一个式子：
$|\bigcup\limits_{i=1}^nA_i|=\sum\limits_{1\le i\le n}|A_i|-\sum\limits_{1\le i< j\le n}|A_i\bigcap A_j|+\sum\limits_{1\le i < j <k\le n}|A_i\bigcap A_j\bigcap A_k|-…+(-1)^{n-1}|A_1\bigcap A_2…\bigcap A_n|$
简单来说（请$yy$一个维恩图出来）：
假设我们要求满足某几个条件的方案数。
算出总方案数，减去不合法的。分别算出不满足条件$1$的方案数、不满足条件$2$的方案数。。。
这时我们发现同时不满足$1,2$、$2,3$、$1,3$。。。的方案被减去了两次，于是要再把它们加回来。
然而同时不满足$1,2,3$、$2,3,4$、$1,2,4$。。。的方案又被加了两次，再减去。
算到$n$个条件都不满足就到头了，也就是答案。
形象的说，就是拆了东墙补西墙，补着补着。。。就补好了。
应用
一种最直接的应用就是根据定义去容斥，直接枚举子集算出方案数，乘上容斥系数$(-1)^{|S|}$。比如这道题（题解）
另一种是算出至少的方案数。其实说至少不太贴切，这里是指枚举有多少不合法的，钦定它们的方案，剩下的随便放。这样会有算重的，容斥减掉。
举个栗子，经典的错排问题：求出长度为$n$满足$p_i\neq i$的排列数。
枚举有多少位置$p_i=i$，$C_n^i$选出是那些位置，剩下位置$(n-i)!$随便放。
于是有$\sum\limits_{i=0}^n(-1)^iC_n^i(n-i)!$
也就是说涉及到“恰好”，就可以考虑容斥转到“至少/多”上了。而“至少/多”一般易于计算。
其他的容斥还有$\min-\max$容斥、子集容斥，甚至莫比乌斯反演也算是容斥。我太菜了就不说了。
二项式反演
就是几个式子：
$f(n)=\sum\limits_{i=0}^n(-1)^iC_n^ig(i)\leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^iC_n^if(i)$
$f(n)=\sum\limits_{i=0}^nC_n^ig(i)\leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}C_n^if(i)$
$f(i)=\sum\limits_{j=i}^n(-1)^jC_j^ig(j)\leftrightarrow g(i)=\sum\limits_{j=i}^n(-1)^jC_j^if(j)$
$f(i)=\sum\limits_{j=i}^nC_j^ig(j)\leftrightarrow g(i)=\sum\limits_{j=i}^n(-1)^{j-i}C_j^if(j)$
其中第二个和第四个用的最多。
证明可能以后会搞。
二项式反演本质就是容斥。但是有的时候用二项式反演更无脑，因为你只要设出两个函数，找到关系，反演过去就没了。
一般用二项式反演也是涉及“恰好”，在求恰好$k$个#!%&@时尤有奇效。根据套路，设$f(i)$为恰好有$i$个#!%&@，$g(i)$为至少有$i$个#!%&@（这里的至少和容斥里的类似）。
$g(i)$一般比较好算，还是钦定$i$个#!%&@，剩下的随意。有的时候要结合$DP$来算。
这时会发现对于一种恰好有$i$个#!%&@的方案，它会在$g(j)$中被计算$C_j^i$次。
于是就能列出式子$g(i)=\sum\limits_{j=i}^nC_j^if(j)$
二项式反演得$f(i)=\sum\limits_{j=i}^n(-1)^{j-i}C_j^ig(j)$，对于任意的$i$我们都可以用这个式子求了。
求至多类似。例题已经没有什么好害怕的了（题解）。里面至少要用$DP$求。
另一种二项式反演的套路是把所有方案分类。比如集合计数。
套路大概是设$f(i)$为恰好，$g(n)$为$n$个东西的总方案数。列出$g(n)=\sum\limits_{i=0}^nC_n^if(i)$的式子反演过去。
卢卡斯定理
当$C_n^m$的$n,m$太大时或者超过了模数，就得上卢卡斯：
$C_n^m=C_{n/p}^{m/p}C_{n\%p}^{m\%p}(\bmod p)$
其中$p$为质数。
然后递归计算$C_{n/p}^{m/p}$即可，复杂度$O(\log_pn)$
代码：
const int mod = 2333;
int fac[mod],inv[mod];//阶乘、阶乘逆元
int C(int n,int m){
if(n<m)return 0;
if(n>=mod)return 1ll*C(n/mod,m/mod)*C(n%mod,m%mod)%mod;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
并不想也不会证明。
当然卢卡斯也不光能干这个，比如这道题。
还有扩展卢卡斯，可以解决模数非质数情况。不过好像没什么用就没学。
卡特兰数
公式
我考一考你。卡特兰数的第$n$项，怎么算的？
卡特兰数有四种算法，你知道吗？
1.$C_n=\dfrac{C_{2n}^n}{n+1}=C_{2n}^n-C_{2n}^{n-1}$
2.$C_n=\dfrac{\sum\limits_{i=0}^n(C_n^i)^2}{n+1}$
3.$C_{n+1}=\sum\limits_{i=0}^nC_iC_{n-i},C_0=1$
4.$C_{n+1}=\dfrac{4n+2}{n+2}C_n,C_0=1$
模型
坐标系游走
在一个坐标系中从原点出发，只能向右或向上走，有多少种走法不跨越直线$y=x$到达点$(n,n)$？
如图（图片来源）
以此来推导一下卡特兰数：
总方案数有$C_{2n}^n$种，考虑不合法的方案数。
如果跨越了$y=x$这条直线，则一定到达直线$y=x+1$。
对某条不合法的路线，沿$y=x+1$翻折一下：
（图片来源）
起点就变成了$(-1,1)$。则不合法的情况为从$(-1,1)$走到$(n,n)$的方案数，即$C_{2n}^{n-1}$。
所以$C_n=C_{2n}^n-C_{2n}^{n-1}$
合法出栈序列
一个足够大的栈的入栈序列为$1,2,3,…n$，求有多少种合法的出栈序列？（也可以是合法的括号序列数）
设$f(n)$为答案。枚举最后一个出栈的是几号元素，设为$i$。
那么在$i$入栈前，$1\sim i-1$都要先出栈，有$f(i-1)$种序列。
在$i$出栈前，$i+1\sim n$都要先出栈，有$f(n-i)$种序列。
所以$f(n)=\sum\limits_{i=1}^nf(i-1)f(n-i)$，即卡特兰数。
或者抽象成坐标系游走，入栈看作向右走，出栈看作向上走。
满2B树计数
求节点数为$2n+1$的满二叉树个数。
设$f(n)$为答案。枚举根节点左右子树节点的个数，就有$f(n)=\sum\limits_{i=0}^{n-1}f(i)f(n-1-i)$，还是卡特兰数。
噶凸多边形
求连接一个凸$n+3$边形的对角线使它们互不相交，将其分成若干个三角形的方案数。
同样设$f(n)$为答案，从一个顶点开始枚举它连向的点，还是有$f(n)=\sum\limits_{i=0}^{n-1}f(i)f(n-1-i)$
造楼梯
求用$n$个任意尺寸的矩形造出高度为$n$的楼梯的方案数。
如图（图片来源）
设$f(n)$为答案。选一个高度$k$，在这一层上覆盖一个大长方形（下图红色部分）。
然后填满蓝色区域和绿色区域，有$f(n-k)f(k-1)$种方案。每个高度加起来，就是卡特兰数。
（吐槽一句：题水就拿高精凑）
奥义·强化坐标系游走！
如果坐标系游走终点为$(n,m)$，有多少种方案？
属于卡特兰数的拓展。
总方案数为$C_{n+m}^n$，和坐标系游走一样推导，易知不合法方案数为$C_{n+m}^{m-1}$
所以答案为$C_{n+m}^n-C_{n+m}^{m-1}$
Prufer序列
一棵无根树可以唯一对应一个$prufer$序列。
用来解决有关节点度数的无根树计数问题。
构造
不断找到当前编号最小的叶节点，把与它相连的点的编号写入$prufer$序列中并删除该叶节点，直到整棵树只有$2$个节点。
也就是说$n$个节点的无根树$prufer$序列长度为$n-2$。
比如这棵无根树：
它的$prufer$序列为$\{2,7,2,1,1\}$
容易发现$prufer$序列的一个重要性质：某个点在$prufer$序列中出现次数等于它的度数-1。
还原
维护一个点集$P$，初始包含$n$个点。
不断找到$P$中不在$prufer$序列中出现的编号最小的节点，把它与$prufer$序列中第一个点相连，在$P$中删除它并删去$prufer$序列的第一个点，直到$prufer$序列为空。最后把$P$中剩余的$2$个点相连。
应用
n个点的有标号无根树计数
或者说$n$个点的完全图生成树计数。
相当于值域为$[1,n]$、长为$n-2$的序列计数。
即$n^{n-2}$。
这个也叫$Cayley$公式。
限制度数的无根树计数
也就是点$i$在$prufer$序列中出现次数为$d(i)-1$。
用一下无标号转有标号再转回无标号的$trick$易知答案为$\dfrac{(n-2)!}{\prod\limits_{i=1}^n(d(i)-1)!}$
这个题比较坑的就是高精和判无解。
若存在$d(i)=0$且$n>1$，或$\sum\limits_{i=1}^nd(i)-1\neq n-2$则无解。
有标号有根树计数
给一棵无根树任意定根，有$n$种情况。
即$n^{n-1}$。
斯特林数
第二类斯特林数
定义
用$\begin{Bmatrix}n\\m\end{Bmatrix}$表示把$n$个有标号元素划分成$m$个无标号集合（不允许有空集）的方案数。也可写作$S(n,m)$。
递推公式
考虑第$n$个元素的去向。可以单独一个集合，也可以放到已经有的$m$个集合里。
$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\times\begin{Bmatrix}n-1\\m\end{Bmatrix}$
边界：$\begin{Bmatrix}0\\0\end{Bmatrix}=1,\begin{Bmatrix}n\\0\end{Bmatrix}=0(n>0)$
通项公式
先计算集合有标号的方案数，用容斥。
枚举至少有多少个集合是空的，$C_m^i$选出来，剩下$m-i$个集合放$n$个元素，转无标号除以$m!$：
$\begin{Bmatrix}n\\m\end{Bmatrix}=\dfrac{1}{m!}\sum\limits_{i=0}^m(-1)^iC_m^i(m-i)^n$
把组合数拆开：$\sum\limits_{i=0}^m\dfrac{(-1)^i}{i!}\cdot\dfrac{(m-i)^n}{(m-i)!}$
惊奇地发现这是个卷积的形式。于是可以用$FFT/NTT$在$O(m\log n)$内算出$\begin{Bmatrix}n\\0\sim m\end{Bmatrix}$。（板子）
应用
自然数幂次方转下降幂
简单说一下下降幂：$m^{\underline n}=m(m-1)(m-2)\cdots(m-n+1)=\dfrac{m!}{(m-n)!}=A_m^n$
考虑$m^n$的含义：把$n$个有标号小球放进$m$个有标号盒子里（允许有空盒子）的方案数。这和第二类斯特林数有点像。
以非空集的个数把$m^n$种方案分类：
$m^n=\sum\limits_{i=1}^n\begin{Bmatrix}n\\i\end{Bmatrix}C_m^ii!=\sum\limits_{i=1}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}$
当然下标从$0$开始也可以，反正$\begin{Bmatrix}n\\0\end{Bmatrix}=0$。
而$i$的上界其实是$\min\{n,m\}$，$i>m$时$C_m^i=0$，$i>n$时$\begin{Bmatrix}n\\i\end{Bmatrix}=0$。所以写$n,m$皆可。
自然数幂次方和
用上面那个来推。
$\sum\limits_{i=0}^ni^k$
$=\sum\limits_{i=0}^n\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}C_i^jj!$
$=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=0}^nC_i^j$
（上文提到过$\sum\limits_{i=0}^nC_i^m=C_{n+1}^{m+1}$）
$=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!C_{n+1}^{j+1}$
$=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\dfrac{(n+1)^{\underline{j+1}}}{j+1}$
不考虑斯特林数的复杂度，如果预处理出阶乘和逆元可以做到$O(n)$预处理，$O(k)$回答；如果暴力算后面那一坨的话可以做到$O(k^2)$回答。
朴素的算法是$O(n\log k)$的。通过斯特林数我们得到了去掉$\log$的算法和与$n$无关的算法，普天同庆皆大欢喜啊。
第一类斯特林数
定义
用$\begin{bmatrix}n\\m\end{bmatrix}$表示把$n$个有标号元素形成$m$个环（圆排列）的方案数。也可写作$s(n,m)$。
递推公式
还是考虑第$n$个元素的去向，单独成环，或者与放在前$n-1$个元素里任意一个元素前面。
$\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}$。
边界：$\begin{bmatrix}0\\0\end{bmatrix}=1,\begin{bmatrix}n\\0\end{bmatrix}=\begin{bmatrix}0\\m\end{bmatrix}=0(n,m>0)$
这个递推可以用生成函数搞一搞但我不会生成函数告辞。
应用
证明什么的好麻烦啊自己搜去吧
阶乘相关
$n!=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}$
下降幂转幂次方
$x^{\underline n}=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i$
斯特林反演
式子
一个不会证的式子：
$\sum\limits_{i=1}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\m\end{Bmatrix}=\sum\limits_{i=1}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}\begin{bmatrix}i\\m\end{bmatrix}=[n=m]$
由这个我们可以推出：
$f(n)=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i)$
$f(n)=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}g(i)\leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}f(i)$
栗子
一个$n$行$m$列的矩阵，每个格子填入一个$[1,c]$的数。求任意两行、任意两列均不同的方案数。$n,m\le 5000$
设$g(i)$为$n$行$i$列的矩阵，任意两行不同的方案数。
容易得到$g(i)=A_{c^i}^n$。
设$f(i)$为$n$行$i$列的矩阵的答案。
枚举$g(m)$有多少种不同的列把$g(m)$分类：
$g(m)=\sum\limits_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}f(i)$
解释一下：把$i$种不同列看作$i$个集合，把$m$列分配进$i$个集合里，即$\begin{Bmatrix}m\\i\end{Bmatrix}$。而对列去重之后就是一个$n$行$i$列的行列都不同的矩阵，即$f(i)$。
反演得$f(m)=\sum\limits_{i=0}^m(-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix}g(i)$
矩阵树定理
绝大部分内容不予证明。
行列式
定义
行列式是一个数。
记$\det(A)$或$|A|$为$n$阶矩阵$A$的行列式，$P$为$(p_1,p_2…p_n)$，即$1\sim n$的一个排列，$r(P)$为$P$的逆序对数。
$\det(A)=\sum\limits_P(-1)^{r(P)}\prod\limits_{i=1}^na_{i,p_i}$
性质
1.$\det(A)=\det(A^T)$
2.将矩阵任意两行交换，行列式取相反数
交换两行可以看做交换排列中的两个数。
假设交换$i,j$行，则会影响到的只有$i,j$之间的逆序对。
记$k$为$i,j$之间任意一行。若$p_k<\min\{p_i,p_j\}$或$p_k>\max\{p_i,p_j\}$对逆序对数显然没有影响；若$p_i<p_k<p_j$，交换后就多了$2$个逆序对，反过来就是少了$2$个逆序对，也就是说$i,j$之间逆序对数变化一定是偶数。
最后$i,j$两者之间一定有$\pm1$的贡献，所以总逆序对数变化量为奇数。行列式取相反数。
推论：存在两行相同时，行列式的值为$0$
3.任意一行乘$k$，行列式的值乘$k$
4.任意一行减去另一行乘$k$，行列式不变
5.根据性质2,4用高斯消元把$A$消成新的上三角矩阵记为$A’$，则$\det(A)=\det(A’)$
计算
显然一个上三角矩阵的行列式就是对角线的数的乘积。
根据性质$4$，把矩阵$O(n^3)$消成上三角直接求即可。
但是矩阵树定理一般会涉及到取模的问题，不能直接用两个浮点数做运算。
考虑高斯消元的过程，我们只是想使对应位置消成$0$。
使用辗转相除法。具体地说，如果矩阵有两行：
$\begin{bmatrix}a_1\cdots\\a_2\cdots\end{bmatrix}$
第$1$行减去第$2$行乘$\left\lfloor\frac{a_1}{a_2}\right\rfloor$，再交换两行（根据性质$2$答案要取相反数）得到新矩阵：
$\begin{bmatrix}a_2\cdots\\a_1\bmod a_2\cdots\end{bmatrix}$
类似于求$\gcd$，不断辗转相除，最终使得第$2$行第$1$列为$0$，复杂度多一个$\log$，但保证了取模问题。
代码见下文。
矩阵树定理
内容
矩阵树定理用于解决无向图生成树计数问题。
记$n$阶矩阵$D$为度数矩阵，$A$为邻接矩阵。
$D_{i,i}$为$i$的度数，$A_{i,j}$为$i,j$之间的边数。
令基尔霍夫（Kirchhoff）矩阵$K=D-A$。
对于任意$i$，去掉$K$的第$i$行和第$i$列，所得矩阵的行列式等于改无向图的生成树计数。
实际使用中，对于一条边$(x,y)$，++a[x][x],++a[y][y],--a[x][y],--a[y][x]，对$a$的$2\sim n$或$1\sim n-1$行求行列式即可。
代码
#define maxn 105
const int mod = 998244353;
int a[maxn][maxn],n;
inline void add(int x,int y){++a[x][x],++a[y][y],--a[x][y],--a[y][x];}
int Gauss(){
int ans=1;
for(register int i=2;i<=n;++i){
for(register int j=i+1;j<=n;++j){
while(a[j][i]){
int t=a[i][i]/a[j][i];
for(register int k=i;k<=n;++k)(a[i][k]-=1ll*t*a[j][k]%mod)%=mod,swap(a[i][k],a[j][k]);
ans=-ans;
}
}
ans=1ll*ans*a[i][i]%mod;
}
return (ans+mod)%mod;
}
变元矩阵树定理
把$D_{i,i}$的定义改为与$i$相连的边权之和，$A_{i,j}$改为$i,j$之间边权之和，就能求出所有生成树边权之积的和。
水题
详情请咨询没意思的算法の学习笔记
广义二项式定理
推广组合数
首先推广组合数到实数域：$C_n^m=\dfrac{n^{\underline{m}}}{m!}$
这里的组合数就没什么实际意义了，只是作为一个式子。
由此能得出负数下的组合数：
$C_n^m(n<0)$
$=\dfrac{n(n-1)(n-2)\dots(n-m+1)}{m!}$
$=(-1)^m\dfrac{-n(-n+1)(-n+2)\dots(-n+m-1)}{m!}$
$=(-1)^m\dfrac{(m-n-1)^{\underline{m}}}{m!}$
$=(-1)^mC_{m-n-1}^m$
推广二项式定理
把$(x+y)^k=\sum\limits_{n=0}^kC_k^nx^ny^{k-n}$推广到实数域。
展开$(x+y)^\alpha,\alpha\in R$。
这时我们不能确定$n$取到多少这个组合数为$0$，所以上界为$+\infty$
$(x+y)^\alpha=\sum\limits_{n=0}^\infty C_\alpha^nx^ny^{\alpha-n}$
这就是牛顿广义二项式定理。
