链接

题目描述

随机一棵以 $1$ 为根,且节点编号满足小根堆性质的树的期望最大深度。
$n \leq 200$

题解

这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。

一开始的一个想法是记 $f_{i,j}$ 表示前 $i$ 个点深度为 $j$ 的树的个数,然后发现不太能转移需要记录最后一层的节点个数。。然后还要记录前面层的所以复杂度就炸了。
然后我们考虑放宽限制,对森林计数,并且我们不妨做一步容斥:设 $f_{i,j}$ 表示 $i$ 个节点,最大深度 $\leq j$ 的树的个数,$g_{i,j}$ 表示 $i$ 个节点,最大深度为 $j$ 的森林的个数。
我们首先预处理出 $dp_{i,j}$ 表示从 $i$ 个点中选出 $j$ 个点组成一棵树的概率,转移
$$dp_{i,j} = dp_{i-1,j-1} * \frac{j-1}{i} + dp_{i-1,j} * \frac{i-j}{i}$$
用 $g$ 转移 $f$ 的时候我们可以考虑变出一个根把这些树都接到根上,有 $f_{i,j} = g_{i-1,j-1}$
用 $f$ 转移 $g$ 其实是一个经典套路:我们枚举编号最小的点所在的树的大小,那么有转移
$$g_{i,j} = \sum_{k=1}^i f_{k,j} * dp_{i,k} * g_{i-k,j}$$
其中 $f_{k,j} * dp_{i,k}$ 是计算了拿出 $k$ 个点组成一棵树的概率,所以我们不需要关系组合计数那一堆东西了(有时候把概率引入到状态就是好用)
答案统计就不说了。

反思

对于树的计数:如果对度数进行限制就对 prufer 序列进行计数,对深度进行限制可以考虑利用森林辅助转移。
其实树是点的集合,森林是树的集合,如果我们固定 $j$,那么树的生成函数 $F$ 和森林的生成函数 $G$ 满足 $e^F = G$(虽然这个题目只能提高复杂度)
并且考试一定要把所有性质读完,要不然会导致漏掉性质把会做的题不会做
概率问题计数不可做可以考虑直接设概率为状态(就是不知道会不会有计数转概率最后再乘回去的)

题解

/*
 * Author: RainAir
 * Time: 2019-11-01 14:54:40
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;
int n,ha;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int getf(int,int);
int getg(int,int);

int f[MAXN][MAXN],g[MAXN][MAXN],dp[MAXN][MAXN];

inline int getf(int i,int j){
    if(f[i][j] != -1) return f[i][j];
    return f[i][j] = getg(i-1,j-1);
}

inline int getg(int i,int j){
    if(j < 0) return 0;
    if(!i) return 1;
    if(!j) return 0;
    if(g[i][j] != -1) return g[i][j];
    int &res = g[i][j];res = 0;
    FOR(k,1,i){
        (res += 1ll*getg(i-k,j)*getf(k,j)%ha*dp[i][k]%ha) %= ha;
    }
    return res;
}

int t[MAXN];

int main(){
//    freopen("toy.in","r",stdin);
//    freopen("toy.out","w",stdout);
    scanf("%d%d",&n,&ha);
    CLR(f,-1);CLR(g,-1);
    dp[1][1] = 1;
    FOR(i,2,n){
        FOR(j,1,i){
            int inv = qpow(i);
            dp[i][j] = (1ll*dp[i-1][j-1]*(j-1)%ha*inv%ha+1ll*dp[i-1][j]*(i-j)%ha*inv%ha)%ha;
        }
    }
    FOR(i,1,n) t[i] = getf(n,i);
    ROF(i,n,1) t[i] = (t[i]+ha-t[i-1])%ha;
    int ans = 0;
    FOR(i,2,n) (ans += 1ll*t[i]*(i-1)%ha) %= ha;
    printf("%lld\n",1ll*ans%ha);
    return 0;
}

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/936/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏