题解 P2144 【[FJOI2007]轮状病毒】

2018-03-11 18:52:14


矩阵树定理裸题。
中间的点度数为n,其他点度数为3,定义基尔霍夫矩阵为度数矩阵减去邻接矩阵,划去一行一列求行列式值即可。
但是long double都存不下。由于 $0 \le n \le 100$,我们可以愉快地 python 打表再交表。
python代码如下,写了个用Decimal的高斯消元。

#!/usr/bin/env python3
from decimal import Decimal, getcontext
getcontext().prec = 50

def main():
    n = int(input())
    if n == 1:
        print(1)
    elif n == 2:
        print(5)
    else: # 生成基尔霍夫矩阵A
        A = [[Decimal(3 * int(i == j) - int(j == (i-1+n)%n or j == (i+1+n) % n)) \
             for j in range(n)] for i in range(n)]
        for i in range(n): # 高斯消元
            r = i
            for j in range(i+1, n):
                if abs(A[j][i]) > abs(A[r][i]):
                    r = j
            if r != i:
                A[r], A[i] = A[i], A[r]
            for t in range(i+1, n):
                k = A[t][i] / A[i][i]
                for j in range(n):
                    A[t][j] -= A[i][j] * k
        Ans = Decimal('1')
        for i in range(n):
            Ans *= A[i][i]
        print("{:.0f}".format(Ans))
if __name__ == '__main__':
    main()