[Python知识库]矩阵树+生成树计数+高精度

矩阵树+生成树计数+高精度

轮状病毒
https://darkbzoj.tk/problem/1002

Python特性非常奇怪
但是因为，高精度还是用Python写了

maxn = 102
D = [[0 for i in range(maxn)] for j in range(maxn)]
A = [[0 for i in range(maxn)] for j in range(maxn)]
mat = [[0 for i in range(maxn)] for j in range(maxn)]


def add(x, y):
    global D, A
    A[x][y] += 1
    A[y][x] += 1
    D[x][x] += 1
    D[y][y] += 1
    return


def swap(a, b):
    return b, a


if __name__ == '__main__':
    n = input()
    n = int(n)
    center = n
    for now in range(0, int(n)):
        add(now, center)
        add(now, (now + 1) % n)
    for i in range(0, n + 1):
        for j in range(0, n + 1):
            mat[i][j] = D[i][j] - A[i][j]
    # print(mat)
    # --det--
    res = 1
    for i in range(0, n):
        for j in range(i + 1, n):
            while mat[j][i] != 0:
                t = mat[i][i] / mat[j][i]
                for k in range(i, n):
                    mat[i][k] = mat[i][k] - t*mat[j][k]
                mat[i], mat[j] = swap(mat[i], mat[j])
                res = -res
        res = res * mat[i][i]
    print(int(res))

CPP ver
没有经过高精度处理

#include<bits/stdc++.h>
//#include<gl/glut.h>
//#include<ctime>
#define ll long long
#define mes(a,b) memset(a,b,sizeof(a))
#define ctn continue
#define ull unsigned long long
//#pragma warning(disable:4996)
#define tgg cout<<"---------------"<<endl;

const ll linf = 9223372036854775807;
const int inf = 0x3f3f3f3f;
using namespace std;
const double pi = acos(-1);
const ll maxn = 100 + 5;
const int mod = 1e9;
const double eps = 1e-8;
const ull p = 131;
const ull pc = 13331;

inline ll gcd(int a, int b) {
	while (b ^= a ^= b ^= a %= b);
	return a;
}

ll A[maxn][maxn], D[maxn][maxn];

struct Matrix {
	ll mat[maxn][maxn];
	void init(int n) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				mat[i][j] = D[i][j] - A[i][j];
				cout << mat[i][j] << " ";
			}
			cout << endl;
		}
	}
	ll det(int n) {
		ll res = 1;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				while (mat[j][i] != 0) {
					ll t = mat[i][i] / mat[j][i];
					for (int k = i; k < n; k++) {
						mat[i][k] = (mat[i][k] - t * mat[j][k]);
					}
					swap(mat[i], mat[j]);
					res = -res;
				}
			}
			res = (res * mat[i][i]);
		}
		return res;
	}
}mat;

void add(int x, int y) {
	//cout << x << " " << y << endl;
	++A[x][y];
	++A[y][x];
	++D[x][x];
	++D[y][y];
	return;
}

int main(int argc, char* argv[]) {
	int n;
	cin >> n;
	int center = n;
	for (int now = 0; now < n; now++) {
		add(now, center);
		add(now, (now + 1) % n);
	}
	mat.init(n + 1);
	cout << mat.det(n) << endl;
	return 0;
}