題意

給你 \(n\) 個(gè)點(diǎn)的無向完全圖，指定一棵樹 \(S\)，問有多少棵生成樹和這棵樹的公共邊數(shù)量為 \(k\in[0,n-1]\)

\(n\leq 100\)

分析

• 考慮矩陣樹定理，把對(duì)應(yīng)的樹邊的邊權(quán)設(shè)置成 \(x\) 然后構(gòu)造基爾霍夫矩陣， 結(jié)果記為 \(val\) ，有

  \[val=\sum_\limits{i=0}^{n-1}x^ians_i\]

  其中 \(ans_i\) 表示和 \(S\) 的公共邊數(shù)量為 \(i\) 的生成樹的個(gè)數(shù)。

• 發(fā)現(xiàn)這是一個(gè)關(guān)于 \(x\) 的多項(xiàng)式，我們要求每一項(xiàng)的系數(shù) \(ans_i\) ，所以搞出 \(x\in[0, n -1]\) 的 \(val\) 然后高斯消元即可。

• 總時(shí)間復(fù)雜度為 \(O(n^4)\)。

代碼

#include<bits/stdc++.h> using namespace std; typedef long long LL; #define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to) #define rep(i, a, b) for(int i = a; i <= b; ++i) #define pb push_back inline int gi() {int x = 0,f = 1;char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48;ch = getchar();}return x * f; } template <typename T> inline void Max(T &a, T b){if(a < b) a = b;} template <typename T> inline void Min(T &a, T b){if(a > b) a = b;} const int N = 104, mod = 1e9 + 7; int n; LL a[N][N], G[N][N], gg[N][N]; LL Pow(LL a, LL b) {LL res = 1ll;for(; b; b >>= 1, a = a * a % mod) if(b & 1) res = res * a % mod;return res; } void Gauss(int n, int m, LL (*G)[N]) {for(int u =0, col = 0; col <= m; ++col, ++u) {int sel = u;for(;sel <= n && !G[sel][col]; ++sel);if(sel > n) { --u; continue;}if(sel ^ u) {for(int i = 1; i <= m + 1; ++i) swap(G[u][i], G[sel][i]);}LL inv = Pow(G[u][col], mod - 2);for(int i = col; i <= m + 1; ++i) G[u][i] = G[u][i] * inv % mod;for(int v = 1; v <=n; ++v)if(u ^ v) {LL x = G[v][col];for(int i = col; i <= m + 1; ++i) G[v][i] = ((G[v][i] - G[u][i] * x) % mod + mod) % mod;}} } LL det(int n, int m, LL (*G)[N]) {LL c = 0;for(int u = 2, col = 2; col <= m; ++col, ++u) {int sel = u;for(;sel <= n && !G[sel][col]; ++sel);if(sel > n) { u--; continue;}if(sel ^ u) {c ^= 1; for(int i = 1; i <= m; ++i) swap(G[u][i], G[sel][i]);}for(int v = u + 1; v <= n; ++v) while(G[v][col]) {LL x = G[v][col] / G[u][col];for(int i = col; i <= m; ++i) G[v][i] = ((G[v][i] - x * G[u][i])%mod + mod) % mod;if(!G[v][col]) break;c ^= 1;for(int i = 1; i <= m; ++i) swap(G[u][i], G[v][i]);}}LL ans = 1ll;for(int i = 2; i <= n; ++i) ans = ans * G[i][i] % mod;if(c) ans = mod - ans;return ans; } int main() {n = gi();rep(i, 1, n - 1){int u = gi(), v = gi();a[u][v] ++, a[v][u] ++;}rep(x, 0, n - 1) {memset(G, 0, sizeof G);rep(i, 1, n)rep(j, 1, n) {G[j][j] += (a[i][j] ? x : 1);G[i][j] -= (a[i][j] ? x : 1);}rep(i, 1, n)rep(j, 1, n) if(G[i][j] < 0) G[i][j] += mod;gg[x][n] = det(n, n, G);LL tmp = 1;for(int i = 0; i < n; ++i, tmp = tmp * x % mod) gg[x][i] = tmp;}Gauss(n - 1, n - 1, gg);for(int i = 0; i < n; ++i) printf("%lld%c", gg[i][n], i == n?'\n':' ');return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/yqgAKIOI/p/10157076.html

總結(jié)

以上是生活随笔為你收集整理的[CF917D]Stranger Trees[矩阵树定理+解线性方程组]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。