行列式与矩阵树定理

行列式取模板子：对于模数非质数采用辗转相除

消元操作是$ Θ(n^3)$的，辗转相除法是 $Θ(log⁡p)$ 的，因为辗转相除和消元每次必然使得数变小，势能只会减少，所以这个是均摊到$ Θ(n^2)$ 的，最终有复杂度 $Θ(n^2log⁡n+n^3)$。

P7112 【模板】行列式求值 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

ll MOD;
int cal(vector<vector<int>>& a, int n) {
    ll flag = 1;
    // 转化成上三角矩阵
    for (int i = 1; i <= n; ++i) {  // 枚举行
        for (int k = i + 1; k <= n; ++k) {
            while (a[i][i]) {  // 辗转相除
                ll tim = a[k][i] / a[i][i];
                for (int j = i; j <= n; ++j)
                    a[k][j] = (a[k][j] - tim * a[i][j] % MOD + MOD) % MOD;
                swap(a[k], a[i]);  // 把较小的放上去
                flag = -flag;
            }
            swap(a[k], a[i]);
            flag = -flag;
        }
    }
    ll res = 1;
    for (int i = 1; i <= n; ++i)
        res = res * a[i][i] % MOD;
    res *= flag;
    return (res + MOD) % MOD;
}
void solve() {
    int n;
    cin >> n >> MOD;
    vector b(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> b[i][j];
    ll ans = cal(b, n);
    cout << ans << endl;
}

Matrix-Tree 矩阵树定理 - OI Wiki (oi-wiki.org)

  • 本篇中的图，无论无向还是有向，都允许重边，但是默认没有自环。自环并不影响生成树的个数，也不影响下文中 Laplace 矩阵的计算，故而矩阵树定理对有自环的情形依然成立。

无向图的 Laplace 矩阵所有n-1阶主子式都相等，且都等于图的生成树的个数。

$ Laplace 矩阵 =度数矩阵D-邻接矩阵A$

  • 度数矩阵：G的度数矩阵 D 是一个 n×n 的矩阵，并且满足：当 $$ i\neq j $$时, $d_{ij}=0$；当 i=j时，$dij $等于 i 的度数。
  • 邻接矩阵：如果i和j之间有边相连，则$A_{ij}=1$,否则为0.

有向图分为根向树形图和叶向树形图。

  • 定义出度矩阵：$𝐷_{ij}^{out} (𝐺) = deg_{i}^{out}, 𝐷_{ij}^{out} = 0, 𝑖 ≠ 𝑗$
  • 定义入度矩阵：$𝐷_{ij}^{in} (𝐺) = deg_{i}^{in}, 𝐷_{ij}^{in} = 0, 𝑖 ≠ 𝑗$
  • 设𝑒(𝑖, 𝑗) 为点𝑖 指向点𝑗 的有向边数，并定义邻接矩阵𝐴 为：
    $𝐴_{𝑖𝑗}(𝐺) = 𝑒(𝑖, 𝑗), 𝑖 ≠ 𝑗$
  • $定义出度Laplace 矩阵𝐿_{𝑜𝑢𝑡} 为：𝐿^{𝑜𝑢𝑡}(𝐺) = 𝐷^{𝑜𝑢𝑡}(𝐺) − 𝐴(𝐺)$
  • $定义入度Laplace 矩阵𝐿_{in} 为：𝐿^{in}(𝐺) = 𝐷^{in}(𝐺) − 𝐴(𝐺)$

记图𝐺 的以𝑟 为根的所有根向树形图个数为$𝑡^{r𝑜𝑜𝑡}(𝐺, 𝑟)$。所谓根向树形图，是说这张图的基图是一棵树，所有的边全部指向父亲。

记图𝐺 的以𝑟 为根的所有叶向树形图个数为$𝑡^{leaf}(𝐺, 𝑟)$。所谓叶向树形图，是说这张图的基图是一棵树，所有的边全部指向儿子。

那有向图的生成树如何求呢？

定理3（矩阵树定理，有向图根向形式）对于任意的𝑘，都有有向图的出度Laplace 矩阵删去第 k行第 k列得到的主子式等于以 k为根的叶向树形图的个数。

定理4（矩阵树定理，有向图叶向形式）对于任意的𝑘，都有有向图的入度Laplace 矩阵删去第 k行第 k列得到的主子式等于以 k为根的根向树形图的个数。

SPOJ.com - Problem HIGH $n \le 12$

int cal(vector<vector<int>>& a, int n) {
    ll flag = 1;
    // 转化成上三角矩阵
    for (int i = 1; i <= n; ++i) {  // 枚举行
        for (int k = i + 1; k <= n; ++k) {
            while (a[i][i]) {  // 辗转相除
                ll tim = a[k][i] / a[i][i];
                for (int j = i; j <= n; ++j)
                    a[k][j] = (a[k][j] - tim * a[i][j]);
                swap(a[k], a[i]);  // 把较小的放上去
                flag = -flag;
            }
            swap(a[k], a[i]);
            flag = -flag;
        }
    }
    ll res = 1;
    for (int i = 1; i <= n; ++i)
        res = res * a[i][i];
    res *= flag;
    return res;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> b(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        b[u][u]++;
        b[v][v]++;
        b[u][v]--;
        b[v][u]--;
    }
    int ans = cal(b, n - 1);
    cout << ans << endl;
}