JZOJ 5154.【NOI2017模拟6.20】树形图求和 （矩阵树定理）

https://gmoj.net/senior/#main/show/5154

题解：

前置技能：
有根内向树方案=（出度矩阵-邻接矩阵）的删除第root行第root列后的行列式

发现就是对条边求经过它生成树方案。

考虑用总的-不经过它的，不经过它即在矩阵上把它删掉。

这样就\(O(m*n^3)\)了。

考虑不经过它 在矩阵上做的修改非常少（只修改了一行的两个位置）。

对于一个\(n*n\)（这题是\(n-1\)）的矩阵\(A\)，若把它的第\(i\)行\(B[1..n]\)，替换成新的一行\(C[1..n]\)，要求新的行列式，是可以做的。

考虑把\(C\)由\(A\)来线性表达，即找到一个行向量\(x[1..n]\)，满足\(c[j]=\sum_{i=1}^n a[i][j]*x[i]\)

这题中，矩阵\(A\)行列式不为0才有意义，所以一定可以找到。

那么\(dot(A‘(B替换成C))=dot(A)*x[i(B是第i行)]\)，证明由行列式性质显然。

那么只要求\(x[i]\)就好了。

我们有\(X*A=C\)，所以\(X=A^{-1}*C\)，\(A\)的逆矩阵在求行列式时顺便求出即可。

所以复杂度可以优化到\(O(n^3+m)\)。

另一种做法是修改矩阵元素的定义，重载乘法和出发，见Samjia博客：
https://blog.csdn.net/samjia2000/article/details/73520175

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int mo = 1e9 + 7;

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = x * x % mo)
		if(y & 1) s = s * x % mo;
	return s;
}

int n, m;

struct nod {
	int x, y, z;	
} b[100005];

const int N = 305;

ll a[N][N], c[N][N];

ll dot;

void work(ll (*a)[N], ll (*b)[N], int n) {
	dot = 1;
	fo(i, 1, n) b[i][i] = 1;
	fo(i, 1, n) {
		int u = -1;
		fo(j, i, n) if(a[j][i]) {
			u = j; break;
		}
		if(u == -1) {
			dot = 0;
			return;
		}
		if(u != i) {
			fo(k, 1, n) swap(a[i][k], a[u][k]), swap(b[i][k], b[u][k]);
			dot *= -1;
		}
		ll v = ksm(a[i][i], mo - 2);
		dot = dot * a[i][i] % mo;
		fo(k, 1, n) a[i][k] = a[i][k] * v % mo, b[i][k] = b[i][k] * v % mo;
		fo(j, 1, n) if(i != j && a[j][i]) {
			ll v = a[j][i];
			fo(k, 1, n) a[j][k] = (a[j][k] - a[i][k] * v) % mo, b[j][k] = (b[j][k] - b[i][k] * v) % mo;
		}
	}
}

int main() {
	freopen("calc.in", "r", stdin);
	freopen("calc.out", "w", stdout);
	scanf("%d %d", &n, &m);
	fo(i, 1, m) {
		scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].z);
		a[b[i].x][b[i].x] ++;
		a[b[i].x][b[i].y] --;
	}
	work(a, c, n - 1);
	ll ans = 0;
	fo(i, 1, m) {
		int x = b[i].x;
		if(x == n) continue;
		ans = (ans + (dot * (c[b[i].x][x] - c[b[i].y][x])) % mo * b[i].z) % mo;
	}
	ans = (ans % mo + mo) % mo;
	pp("%lld\n", ans);
}

JZOJ 5154.【NOI2017模拟6.20】树形图求和 （矩阵树定理）

原文：https://www.cnblogs.com/coldchair/p/12989850.html