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

panda_2134

2018-03-11 18:52:14

Solution

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