高等袋鼠

校内赛 高等袋鼠

题目描述

柴老师在上高等代数，今天老师讲到了矩阵树定理：

定义 Kirchhoff 矩阵为度数矩阵减去邻接矩阵，那么生成树个数就是 Kirchhoff 矩阵删掉第 ii 行第 ii 列后行列式的值…

作为代数学家的柴老师当然会这些啦，所以太过无聊听着听着就进入了梦乡。

在梦里，两幅无向图纠缠在一起，生成树怎么也看不清…

具体的，两幅无向图均为简单连通图，即无重边无自环，两幅图共享了顶点，即两幅图都有 nn 个顶点，编号为$ 1,\cdots,n$ 。

柴老师洋洋洒洒从第一幅图中随机地选出了一棵生成树，但转头一看，图变成了第二幅图！

也就是说，此前选出的生成树中，所有不在第二幅图中的边都消失了！

柴老师非常悲伤，想让你帮他算一下，所有可能的情况下他选出的生成树最后剩下的边数的和，答案对 998244353取模。

题目分析

trick：通过把矩阵里的元素变为${1+w_ex}$的多项式可以求出$\sum_{T\in Tree}\sum_{e\in T}w_e$

是trick的板子

//
// Created by mrx on 2022/10/4.
//
#include <vector>
#include <algorithm>
#include <iostream>
#include <array>
#include <functional>
#include <cassert>

using ll = long long;

template<typename T>
T inverse(T a, T b) {
	T u = 0, v = 1;
	while (a != 0) {
		T t = b / a;
		b -= t * a;
		std::swap(a, b);
		u -= t * v;
		std::swap(u, v);
	}
	assert(b == 1);
	return u;
}

template<typename T>
T power(T a, int b) {
	T ans = 1;
	for (; b; a *= a, b >>= 1) {
		if (b & 1)ans *= a;
	}
	return ans;
}

template<int Mod>
class Modular {
public:
	using Type = int;

	template<typename U>
	static Type norm(U& x) {
		Type v;
		if (-Mod <= x && x < Mod) v = static_cast<Type>(x);
		else v = static_cast<Type>(x % Mod);
		if (v < 0) v += Mod;
		return v;
	}

	constexpr Modular() : value() {}

	int val() const { return value; }

	Modular inv() const {
		return Modular(inverse(value, Mod));
	}

	template<typename U>
	Modular(const U& x) {
		value = norm(x);
	}

	const Type& operator ()() const {
		return value;
	}

	template<typename U>
	explicit operator U() const {
		return static_cast<U>(value);
	}

	Modular& operator +=(const Modular& other) {
		if ((value += other.value) >= Mod) value -= Mod;
		return *this;
	}

	Modular& operator -=(
			const Modular& other) {
		if ((value -= other.value) < 0) value += Mod;
		return *this;
	}

	template<typename U>
	Modular& operator +=(const U& other) { return *this += Modular(other); }

	template<typename U>
	Modular& operator -=(const U& other) { return *this -= Modular(other); }

	Modular& operator ++() { return *this += 1; }

	Modular& operator --() { return *this -= 1; }

	Modular operator ++(int) {
		Modular result(*this);
		*this += 1;
		return result;
	}

	Modular operator --(int) {
		Modular result(*this);
		*this -= 1;
		return result;
	}

	Modular operator -() const { return Modular(-value); }

	template<class ISTREAM_TYPE>
	friend ISTREAM_TYPE& operator >>(ISTREAM_TYPE& is, Modular& rhs) {
		ll v;
		is >> v;
		rhs = Modular(v);
		return is;
	}

	template<class OSTREAM_TYPE>
	friend OSTREAM_TYPE& operator <<(OSTREAM_TYPE& os, const Modular& rhs) {
		return os << rhs.val();
	}

	Modular& operator *=(const Modular& rhs) {
		value = ll(value) * rhs.value % Mod;
		return *this;
	}

	Modular& operator /=(const Modular& other) { return *this *= Modular(inverse(other.value, Mod)); }

	friend const Type& abs(const Modular& x) { return x.value; }

	friend bool operator ==(const Modular& lhs, const Modular& rhs) { return lhs.x == rhs.x; }

	friend bool operator <(const Modular& lhs, const Modular& rhs) { return lhs.x < rhs.x; }


	bool operator ==(const Modular& rhs) { return *this == rhs.value; }

	template<typename U>
	bool operator ==(U rhs) { return *this == Modular(rhs); }

	template<typename U>
	friend bool operator ==(U lhs, const Modular& rhs) { return Modular(lhs) == rhs; }

	bool operator !=(const Modular& rhs) { return *this != rhs; }

	template<typename U>
	bool operator !=(U rhs) { return *this != rhs; }

	template<typename U>
	friend bool operator !=(U lhs, const Modular& rhs) { return lhs != rhs; }

	bool operator <(const Modular& rhs) { return this->value < rhs.value; }

	Modular operator +(const Modular& rhs) { return Modular(*this) += rhs; }

	template<typename U>
	Modular operator +(U rhs) { return Modular(*this) += rhs; }

	template<typename U>
	friend Modular operator +(U lhs, const Modular& rhs) { return Modular(lhs) += rhs; }

	Modular operator -(const Modular& rhs) { return Modular(*this) -= rhs; }

	template<typename U>
	Modular operator -(U rhs) { return Modular(*this) -= rhs; }

	template<typename U>
	friend Modular operator -(U lhs, const Modular& rhs) { return Modular(lhs) -= rhs; }

	Modular operator *(const Modular& rhs) { return Modular(*this) *= rhs; }

	template<typename U>
	Modular operator *(U rhs) { return Modular(*this) *= rhs; }

	template<typename U>
	friend Modular operator *(U lhs, const Modular& rhs) { return Modular(lhs) *= rhs; }

	Modular operator /(const Modular& rhs) { return Modular(*this) /= rhs; }

	template<typename U>
	Modular operator /(U rhs) { return Modular(*this) /= rhs; }

	template<typename U>
	friend Modular operator /(U lhs, const Modular& rhs) { return Modular(lhs) /= rhs; }

private:
	Type value;
};

constexpr int mod = 998244353;
using Z = Modular<mod>;

struct node {
	Z x, y;

	node(Z x, Z y) : x(x), y(y) {}

	node() {}

	friend node operator +(const node& u, const node& v) {
		return node(u.x + v.x, u.y + v.y);
	}

	friend node operator -(const node& u, const node& v) {
		return node(u.x - v.x, u.y - v.y);
	}

	friend node operator *(const node& u, const node& v) {
		return node(u.x * v.y + u.y * v.x, u.y * v.y);
	}

	friend node operator /(const node& u, const node& v) {
		Z inv = v.y.inv();
		return node((u.x * v.y - u.y * v.x) * inv * inv, u.y * inv);
	}
};

struct matrix {
	std::vector<std::vector<node>> mat;

	int n, m;

	matrix(int n, int m) : mat(n, std::vector<node>(m, node(0, 0))), n(n), m(m) {}

	std::vector<node>& operator [](int idx) {
		return mat[idx];
	}

	Z gauss(int nn) {
		node res(0, 1);
		for (int i = 0; i < nn; ++i) {
			int nxt = i;
			for (; nxt < nn - 1; ++nxt)if (mat[nxt][i].y)break;
			if (mat[nxt][i].y) {
				std::swap(mat[nxt], mat[i]);
				if (nxt != i)res = res * node(0, -1);
				res = (res * mat[i][i]);
				node inv = node(0, 1) / mat[i][i];
				for (int j = i + 1; j < nn; ++j) {
					node div = mat[j][i] * inv;
					for (int k = i; k < nn; ++k) mat[j][k] = mat[j][k] - (div * mat[i][k]);
				}
			} else return 0;
		}
		return res.x;
	}
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n;
	std::cin >> n;
	std::vector<std::vector<int>> a(n, std::vector<int>(n));
	std::vector<std::vector<int>> b(n, std::vector<int>(n));
	std::vector<int> deg1(n), deg2(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			char x;
			std::cin >> x;
			a[i][j] = x - '0';
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			char x;
			std::cin >> x;
			b[i][j] = (x - '0');
		}
	}

	matrix mat(n, n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (a[i][j] == 1 && i >= j) {
				mat[i][i] = mat[i][i] + node(b[i][j] == 1, 1);
				mat[j][j] = mat[j][j] + node(b[i][j] == 1, 1);
				mat[i][j] = mat[i][j] - node(b[i][j] == 1, 1);
				mat[j][i] = mat[j][i] - node(b[i][j] == 1, 1);
			}
		}
	}
	std::cout << mat.gauss(n - 1) << '\n';

	return 0;
}