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("
")
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
", ans);
}