矩阵行列式-矩阵树定理-P4111小Z的房间-学习笔记-解题报告-模板

· · 题解

行列式

何为行列式？ 一个矩阵对应一个行列式（数字）；

行列式有什么用？ 目前看来，只有矩阵树定理用上了它；

行列式怎么求？

好博客

简单来说，转置矩阵，行列式不变；

交换两行/列位置，行列式取相反数；

对一行/列乘以某数，行列式也乘以某数；

用一行的倍数减去另一行，行列式的值不变；

一个上三角行列式的值等于对角线的乘积

所以我们可以联想一下高斯消元的做法，把它削成上三角矩阵（注意，不是对角线矩阵），因为在剩余系下没有除法，所以我们要辗转相除；

il int det() {
    int ans = 1;
    for (ri i = 1; i <= sz; ++i) {  // 当前在消第i个（i，i)
        for (ri j = i + 1, t; j <= sz; ++j) {  // 把它下面对应的位置消成0
            while (m[j][i]) { // 直到为0
                t = m[i][i] / m[j][i];  // 计算第j行相应的数是第i行的几倍
                for (ri k = i; k <= sz; ++k) {  // 一个一个消去并交换数字（消去后之前的位置变小）
                    mod(m[i][k] -= m[j][k] * t);
                    swap(m[i][k], m[j][k]); // 交换
                }
                ans *= -1; // 记得交换是，行列式取反
            }
        }
        if (m[i][i] == 0) return 0; // 如果有零，就不用继续做了
        else mod(ans *= m[i][i]); // 更新ans
    }
    return (ans % md + md) % md;
}

牢牢记住

矩阵树定理

（度数矩阵（对角线矩阵）-邻接矩阵）的行列式等于该图生成树个数；

题目总结

矩阵树定理裸题

数据范围

能过

解题思路

如之前所说，直接做；

易错误区

1.！！！要建好图，有的地方不是节点

2.求行列式不要写错，是缩成上三角；

代码展示

//%:pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<bitset>
#include<deque>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define pb push_back
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
il char gc() {
    static const int BS = 1 << 22;
    static unsigned char buf[BS], *st, *ed;
    if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);
    return st == ed ? EOF : *st++;
}
#define gc getchar
template<class T>void in(T &x)
{
    x = 0; bool f = 0; char c = gc();
    while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
    while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
    if (f) x = -x;
}
#undef gc
void out(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) out(x / 10);
    putchar(x % 10 + '0');
}
#define int ll
int n, m;
char tc[2];
bool h[12][12];
#define Maxsz 150
#define md 1000000000
il void mod(int &x) {
    x = (x % md + md) % md;
}
struct Mat {
    int sz;
    int m[Maxsz][Maxsz];
    il void clear() {mem0(m);}
    il Mat () {sz = 0; clear();}
    il int* operator[](int x) {
        return this->m[x];
    }
    il Mat operator*(const Mat &x)const {
        Mat res; res.sz = sz;
        for (ri i = 1; i <= sz; i++) {
            for (ri k = 1; k <= sz; k++) {
                for (ri j = 1; j <= sz; j++)
                    mod(res.m[i][j] += m[i][k] * x.m[k][j] % md);
            }
        }
        return res;
    }
    il void operator*=(const Mat &x) {
        *this = (*this) * x;
    }
    il void operator+=(const Mat &x) {
        for (ri i = 1; i <= sz; ++i) {
            for (ri j = 1; j <= sz; ++j) {
                mod(m[i][j] += x.m[i][j]);
            }
        }
    }
    il Mat operator+(const Mat &x)const {
        Mat res = *this;
        res += x;
        return res;
    }
    il void operator-=(const Mat &x) {
        for (ri i = 1; i <= sz; ++i) {
            for (ri j = 1; j <= sz; ++j) {
                m[i][j] -= x.m[i][j];//mod(m[i][j] -= x.m[i][j]);
            }
        }
    }
    il Mat operator-(const Mat &x)const {
        Mat res = *this;
        res -= x;
        return res;
    }
    il void print() {
        for (ri i = 1; i <= sz; i++) {
            for (ri j = 1; j <= sz; j++)
                printf("%lld ", m[i][j]);
            puts("");
        }
    }
    il void e() {
        clear();
        for (ri i = 1; i <= sz; i++)
            m[i][i] = 1;
    }
    il Mat qpow(int x) {
        Mat res, mul = *this;
        if (x == 0) {
            res.e();
            return res;
        }
        res = *this; --x;
        for (; x; x >>= 1, mul *= mul) if (x & 1) res *= mul;
        return res;
    }
    il int det() {
        int ans = 1;
        for (ri i = 1; i <= sz; ++i) {
            for (ri j = i + 1, t; j <= sz; ++j) {
                while (m[j][i]) {
                    t = m[i][i] / m[j][i];
                    for (ri k = i; k <= sz; ++k) {
                        mod(m[i][k] -= m[j][k] * t);
                        swap(m[i][k], m[j][k]);
                    }
                    ans *= -1;
                }
            }
            if (m[i][i] == 0) return 0;
            else mod(ans *= m[i][i]);
        }
        return (ans % md + md) % md;
    }
} d, g, s;
int cnt;
int xx[4] = {0, 1, 0, -1}, yy[4] = { -1, 0, 1, 0};
il bool check(int x, int y) {
    return (x >= 1) && (y >= 1) && (x <= n) && (y <= m) && (h[x][y] == 1);
}
signed main() {
    in(n), in(m);
    for (ri i = 1; i <= n; ++i) {
        for (ri j = 1; j <= m; ++j) {
            scanf("%1s", tc);
            h[i][j] = (tc[0] == '.');
        }
    }
    for (ri i = 1; i <= n; ++i) {
        for (ri j = 1; j <= m; ++j) {
            if (h[i][j]) {
                s[i][j] = ++cnt;
                if (check(i, j - 1)) {
                    g[s[i][j]][s[i][j - 1]] = 1;
                    g[s[i][j - 1]][s[i][j]] = 1;
                }
                if (check(i - 1, j)) {
                    g[s[i][j]][s[i - 1][j]] = 1;
                    g[s[i - 1][j]][s[i][j]] = 1;
                }
            }
        }
    }
    for (ri i = 1; i <= cnt; ++i) {
        for (ri j = 1; j <= cnt; ++j) {
            if (g[i][j])
                d[i][i]++;
        }
    }
    d.sz = g.sz = cnt;
    d -= g; --d.sz;
    printf("%lld", d.det());
    return 0;
}