繁凡出品的全新系列：解題報告系列 —— 超高質量演算法題單，配套我寫的超高質量題解和代碼，題目難度不一定按照題號排序，我會在每道題后面加上題目難度指數（ 1 ～ 5 1 \sim 5 1～5），以模板題難度 1 1 1 為基準，
這樣大家在學習演算法的時候就可以執行這樣的流程：
%
閱讀我的【學習筆記】 / 【演算法全家桶】學習演算法 ? \Rightarrow ? 閱讀我的相應演算法的【解題報告】獲得高質量題單 ? \Rightarrow ? 根據我的一句話題解的提示嘗試自己解決問題 ? \Rightarrow ? 點開我的詳細題解鏈接學習鞏固（好耶）%
解題報告系列合集：【解題報告系列】超高質量題單 + 題解（ICPC / CCPC / NOIP / NOI / CF / AT / NC / P / BZOJ）
本題單前置知識：【學習筆記】樹的計數，prufer（Prüfer）編碼，Cayley公式及相應例題
1. prufer \text{prufer} prufer 序列
Prufer數列是無根樹的一種數列，在組合數學中，Prufer數列由有一個對于頂點標過號的樹轉化來的數列，點數為n的樹轉化來的Prufer數列長度為n-2，
2. prufer \text{prufer} prufer 序列的性質
性質1： prufer \text{prufer} prufer 序列與無根樹一一對應，
顯然
性質2： 度數為 d i d_i di? 的節點會在 prufer \text{prufer} prufer 序列中出現 d i ? 1 d_i-1 di??1 次，
當某個節點度數為 1 1 1 時，會直接被刪掉，否則每少掉一個相鄰的節點，它就會在序列中出現 1 1 1 次，
因此共出現 d i ? 1 d_i-1 di??1 次，
性質3： 一個 n 個節點的完全圖的生成樹個數為 n n ? 2 n^{n-2} nn?2 （Cayley 公式），
對于一個 n n n 個點的無根樹，它的 prufer \text{prufer} prufer 序列長為 n ? 2 n-2 n?2 ，而每個位置有 n n n 種可能性，因此可能的 prufer \text{prufer} prufer 序列有 n n ? 2 n^{n-2} nn?2 種，
又由于 prufer \text{prufer} prufer 序列與無根樹一一對應，因此生成樹個數應與 prufer \text{prufer} prufer 序列種樹相同，即 n n ? 2 n^{n-2} nn?2 ，
性質4： 對于給定度數為 d 1 ～ n d_{1\sim n} d1～n? 的一棵無根樹共有 ( n ? 2 ) ! ∏ i = 1 n ( d i ? 1 ) ! \cfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!} ∏i=1n?(di??1)!(n?2)!? 種情況，
由上面的性質可以知道，度數為 d i d_i di? 的節點會在 prufer \text{prufer} prufer 序列中出現 d i ? 1 d_i-1 di??1 次，
則就是要求出 d i ? 1 d_i-1 di??1 個 i ( 1 ≤ i ≤ n ) i(1\le i\le n) i(1≤i≤n)的全排列個數，
而上面那個式子就是可重全排列公式，（即全排列個數除以重復元素內部的全排列個數）
3. Cayley \text{Cayley} Cayley 公式的推論
-
n n n 個無序點的有根樹個數為 n n ? 1 n^{n-1} nn?1
-
n n n 個無序點的無根樹個數為 n n ? 2 n^{n-2} nn?2
-
n n n 個有序點的有根樹個數為 n n ? 1 × ( n ? 1 ) ! n^{n-1}\times (n-1)! nn?1×(n?1)!
-
n n n 個有序點的無根樹個數為 n n ? 2 × ( n ? 1 ) ! n^{n-2}\times (n-1)! nn?2×(n?1)!
A、（P6086 【模板】）Prufer 序列
Weblink
https://www.luogu.com.cn/problem/P6086
Problem
請實作 Prufer 序列和無根樹的相互轉化，
為方便你實作代碼，盡管是無根樹，我們在讀入時仍將 n 設為其根，
對于一棵無根樹，設 f 1 … n ? 1 f_{1\dots n-1} f1…n?1? 為其父親序列（ f i f_i fi? 表示 i 在 n 為根時的父親），設 p 1 … n ? 2 p_{1 \dots n-2} p1…n?2? 為其 Prufer 序列，
另外，對于一個長度為 m 的序列 a 1 … m a_{1 \dots m} a1…m? ，我們設其權值為 xor ? i = 1 m i × a i \operatorname{xor}_{i = 1}^m i \times a_i xori=1m?i×ai? ，
Solution
由無根樹得到其 prufer 序列：
找到編號最小的度數為1的點
洗掉該節點并在序列中添加與該節點相連的節點的編號
重復1,2操作，直到整棵樹只剩下兩個節點
雙指標 O ( n ) O(n) O(n) 實作： 指標指向編號最小的葉節點，每次刪掉它之后，如果產生了新的葉節點且編號比指標指向的更小，則直接繼續刪掉，否則自增找到下一個編號最小的葉節點，
由 prufer 序列還原該無根樹：
每次取出prufer序列中最前面的元素u
在點集中找到編號最小的沒有在prufer序列中出現的元素v
給u,v連邊然后分別洗掉
最后在點集中剩下兩個節點，給它們連邊
雙指標 O ( n ) O(n) O(n) 實作： 指標指向編號最小的度數為 1 的節點，每次將它與當前列舉到的 Prufer 序列的點連接之后，如果產生了新的度數為 1 的節點且編號比指標指向的更小，則直接繼續將它與下一個 Prufer 序列的點連接，否則自增找到下一個編號最小的度數為 1 的節點，
Code
const int N = 6e6 + 7, mod = 1e9 + 7;
int n, m, t;
int p[N], f[N], d[N];
ll ans = 0;
void TtoP()
{
for(int i = 1; i <= n - 1; ++ i) {
scanf("%d", &f[i]);
d[f[i]] ++ ;
}
for(int i = 1, j = 1; i <= n - 2; ++ i, ++ j) {
while(d[j]) ++ j;//從小到大找到第一個度數為 1 (d[j] == 0) 的結點
p[i] = f[j];//將父結點放入 prufer 序列里
while(i <= n - 2 && -- d[p[i]] == 0 && p[i] < j)
p[i + 1] = f[p[i]], ++ i;
}
ans = 1ll * p[1];
for(int i = 2; i <= n - 2; ++ i) {
ans ^= 1ll * i * p[i];
}
}
void PtoT()
{
for(int i = 1; i <= n - 2; ++ i) {
scanf("%d", &p[i]);
d[p[i]] ++ ;
}
p[n - 1] = n;
for(int i = 1, j = 1; i <= n - 1; ++ i, ++ j) {
while(d[j]) ++ j;
f[j] = p[i];
while(i <= n - 1 && -- d[p[i]] == 0 && p[i] < j)
f[p[i]] = p[i + 1], ++ i;
}
ans = 1ll * f[1];
for(int i = 2; i <= n - 1; ++ i)
ans ^= 1ll * i * f[i];
}
int main()
{
scanf("%d%d", &n, &m);
if(m == 1) TtoP();
else PtoT();
printf("%lld\n", ans);
return 0;
}
B、（P2290 [HNOI2004]）樹的計數
Weblink
https://www.luogu.com.cn/problem/P2290
Problem
一個有 n n n 個節點的樹，設它的節點分別為 v 1 , v 2 , … , v n v_1,v_2,\ldots,v_n v1?,v2?,…,vn? ，已知第 i i i 個節點 v i v_i vi? 的度數為 d i d_i di? ，問滿足這樣的條件的不同的樹有多少棵，
Solution
由 性質4： 對于給定度數為 d 1 ～ n d_{1\sim n} d1～n? 的一棵無根樹共有 ( n ? 2 ) ! ∏ i = 1 n ( d i ? 1 ) ! \cfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!} ∏i=1n?(di??1)!(n?2)!? 種情況，我們可以直接用公式求解，但是這個公式可能會爆 long long ，不想寫高精，所以考慮另一種思路，
我們發現題目其實可以轉化成一共有 n ? 2 n-2 n?2 個位置，要放 n n n 個數，其中數 i i i 要占 d [ i ] ? 1 d[i]-1 d[i]?1 個位置，顯然答案為： a n s = ∏ i = 1 n C d [ i ] ? 1 s u m ans \ = \prod_{i=1}^n\ C_{d[i] - 1} ^ {sum} ans =∏i=1n? Cd[i]?1sum? ，其中 s u m sum sum 為剩余的位置數，
最后需要特判一下不合法的情況：
-
圖不合法，即有點的度數為 0 0 0 ，說明不是連通圖，也就不是樹，輸出 0 0 0，
-
prufer序列不合法，即 ∑ d i ? 1 ! = n ? 2 \sum d_i-1!=n-2 ∑di??1!=n?2
-
若 n = 1 n=1 n=1 ，當 d 1 = 0 d_1=0 d1?=0 合法，輸出
1，否則不合法，輸出0，
Code
const int N = 507;
ll c[N][N];
int n, m;
ll d[N], sum;
void solve()
{
scanf("%d", &n);
if(n == 1) {
int d;
scanf("%lld", &d);
if(d == 0)
puts("1");
else puts("0");
return ;
}
bool flag = 0;
for(int i = 1; i <= n; ++ i) {
scanf("%lld", &d[i]);
if(d[i] == 0) flag = 1;
sum += d[i] - 1;
}
if(sum != n - 2 || flag) {
puts("0");
return ;
}
c[0][0] = c[1][0] = c[1][1] = 1;
for(int i = 2; i <= sum; ++ i) {
c[i][0] = 1;
for(int j = 1; j <= sum; ++ j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
ll ans = 1;
for(int i = 1; i <= n; ++ i) {
ans *= c[sum][d[i] - 1];
sum -= d[i] - 1;
}
printf("%lld\n", ans);
return ;
}
int main()
{
solve();
}
C、（CF156D） Clues
Weblink
https://www.luogu.com.cn/problem/CF156D
Problem
給定一個 n n n 個點 m m m 條邊的帶標號無向圖，它有 k k k 個連通塊，求添加 k ? 1 k-1 k?1 條邊使得整個圖連通的方案數，答案對 p p p 取模，
Solution
結論： a n s = n k ? 2 × ∏ i = 1 k s i \displaystyle ans=n^{k-2}\times \prod_{i=1}^ks_i ans=nk?2×i=1∏k?si?
其中 s i s_i si? 為第 i i i 個連通塊的點數，
我們直接用并查集計算一下連通塊的點的數量即可，
證明：
Code
const int N = 1e5 + 7, mod = 1e9 + 7;
int n, m, p, k;
int fa[N];
int s[N];
int qpow(int a, int b)
{
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}
int Find(int x)
{
if(fa[x] == x) return x;
return fa[x] = Find(fa[x]);
}
void Union(int x, int y)
{
int fx = Find(x), fy = Find(y);
fa[fx] = fy;
}
int main()
{
scanf("%d%d%d", &n, &m, &p);
if(p == 1) return puts("0"), 0;
for(int i = 1; i <= n; ++ i)
fa[i] = i;
for(int i = 1; i <= m; ++ i) {
int x, y;
scanf("%d%d", &x, &y);
Union(x, y);
}
for(int i = 1; i <= n; ++ i)
s[Find(i)] ++ ;
ll ans = 1;
for(int i = 1; i <= n; ++ i)
if(i == Find(i)) ++ k, ans = (ans * 1ll * s[i]) % p;
if(k == 1) return puts("1"), 0;
ans = (ans * 1ll * qpow(n, k - 2)) % p;
printf("%lld\n", ans);
return 0;
}
D、UVA10843 Anne’s game
Weblink
https://www.luogu.com.cn/problem/UVA10843
Problem
A n n e Anne Anne 喜歡玩一個游戲：
- 她在一張紙上畫一個圓
- 然后再畫一個圓，并用一條線將其與另一個圓連接起來
- 接著再畫一個圓，并用一條線將其與前兩個圓中的任意一個連接起來
- 重復上述操作，直至她畫了 n n n 個圓，且每個圓都與先前繪制的任意一個圓連接，所有圓都不相交，且每一條線也不相交
- 最后，她在這些圓中隨機填入 1 1 1 ~ n n n 這些數字（每個圓僅填入一個數字）
那么，
A
n
n
e
Anne
Anne 可以得到多少種不同的圖？
兩幅圖不同的條件：其中一幅圖有一條線連接了編號為
i
i
i 和編號為
j
j
j 的圓，而另一幅圖沒有，
1 < n ≤ 100 1<n\le100 1<n≤100
Solution
隨機填入編號 —— 無序點， n n n 個無序點的無根樹個數為 n n ? 2 n^{n-2} nn?2，
直接輸出即可，
Code
const int N = 1e5 + 7, p = 2000000011;
int n, m, k, kcase, t;
int qpow(int a, int b)
{
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}
int main()
{
scanf("%d", &t);
while(t -- ) {
scanf("%d", &n);
if(n <= 2) {
printf("Case #%d: 1\n", ++ kcase);
continue;
}
printf("Case #%d: %d\n", ++ kcase, qpow(n, n - 2));
}
return 0;
}
E、（P4430） 小猴打架
Problem
一開始森林里面有N只互不相識的小猴子，它們經常打架，但打架的雙方都必須不是好朋友，每次打完架后，打架的雙方以及它們的好朋友就會互相認識，成為好朋友，經過N-1次打架之后，整個森林的小猴都會成為好朋友， 現在的問題是，總共有多少種不同的打架程序， 比如當N=3時，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六種不同的打架程序，
Solution
其實就是有 n n n 個結點，經過 n ? 1 n-1 n?1 次連邊形成一棵樹，問有多少種連邊程序，不止是連邊的方案數，最后生成的樹的不同方案也算方案數，
首先顯然 n n n 個無序點的無根樹的方案數為 n n ? 2 n^{n-2} nn?2，并且有 n ? 1 n-1 n?1 次連邊，也就是有 ( n ? 1 ) ! (n-1)! (n?1)! 種連邊方案，總方案數為 ( n ? 1 ) ! × n n ? 2 (n-1)!\times n^{n-2} (n?1)!×nn?2，
const int N = 1e5 + 7, mod = 9999991;
int n, m, ans;
int main()
{
ans = 1;
scanf("%d", &n);
for(int i = 1; i <= n - 2; ++ i) ans = 1ll * ans * n % mod;
for(int i = 1; i <= n - 1; ++ i) ans = 1ll * ans * i % mod;
printf("%d\n", ans);
return 0;
}
F、（BZOJ1005） 明明的煩惱
Problem
給出標號為 1 到 N 的點，以及某些點最終的度數，允許在任意兩點間連線，可產生多少棵度數滿足要求的樹？
1 ≤ n ≤ 1000 1\le n\le 1000 1≤n≤1000
Solution
https://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266009.html
標籤：其他
上一篇：Java之簡易版飛機大戰
下一篇：積水幾何