生成树计数。
基尔霍夫矩阵为度数矩阵减去邻接矩阵。
无向图生成树计数为基尔霍夫矩阵的行列式
可得递推方程
$ans = 3 \times f(n - 1) - 2 \times f(n - 2) - 2$
$f(n) = 3 \times f(n - 1) - f(n - 2)$
加上高精度即可。
注意算行列式时多写几行容易看。
#include <bits/stdc++.h> using namespace std; struct Bigi { int a[600], len; Bigi() { memset(a, 0, sizeof(a)); len = 1; } friend Bigi operator * (int x, Bigi b) { Bigi res; res.len = b.len + 10; for (int i = 1; i <= res.len; i++) { res.a[i] += b.a[i] * x; res.a[i + 1] += res.a[i] / 10; res.a[i] %= 10; } while (res.len > 1 && res.a[res.len] == 0) res.len--; return res; } friend Bigi operator - (Bigi x, Bigi y) { Bigi res; res.len = x.len; for (int i = 1; i <= res.len; i++) { res.a[i] = x.a[i] - y.a[i]; while (res.a[i] < 0) { res.a[i] += 10; x.a[i + 1]--; } } while (res.len > 1 && res.a[res.len] == 0) res.len--; return res; } friend Bigi operator + (Bigi x, int y) { Bigi res = x; res.a[1] += y; for (int i = 1; i <= res.len; i++) { if (res.a[i] >= 10) { res.a[i] -= 10; res.a[i + 1]++; } else { break; } } while (res.a[res.len + 1]) res.len++; return res; } void print() { for (int i = len; i; i--) printf("%d", a[i]); puts(""); } } big[150], ans; int main() { int n; scanf("%d", &n); big[1] = big[1] + 3; big[2] = big[2] + 8; if (n <= 2) { big[n].print(); return 0; } for (int i = 3; i <= n; i++) big[i] = 3 * big[i - 1] - big[i - 2]; ans = 3 * big[n - 1] - 2 * big[n - 2]; ans = ans + (-2); ans.print(); return 0; }View Code