UOJ351 新年的叶子

前言

本来打算这星期不写题解的(周末就NOIP啦),不过这题实在是太有趣了所以还是要写一下。

题目描述

题意很容易读错啊,比如我考试的时候以为它不只涂黑叶子节点…

分析

我们先考虑原来直径是偶数的情况(奇数类似),那么所有直径的中点都是同一个。以这个中点为根,将中点每个子树内深度为直径的一半的叶子节点放入一个集合。这时候,只要有两个不同的集合中的点没有被完全涂黑,直径就一定没有缩小。
于是考虑通过枚举剩下的一个没有被涂黑的集合来计算。

声明

  • sz_i为第i个集合的大小
  • totsz为所有集合大小之和
  • totlf为叶子节点总数

Solution 1

我们考虑集合中的点被一个个涂黑的顺序,那么总共的方案数就是totsz!.
枚举最后剩下没有被完全涂黑的集合,设为i.
首先我们需要从这个集合中选出若干个被涂黑的点,若涂黑了j个,方案数为{sz_i\choose j};然后考虑最后一个被涂黑的点,它不会属于我们枚举的集合(我们涂黑了这个点直径变小因此应该属于其他集合),这个点的选法有totsz-sz_i种;剩下的totsz-(sz_i -j)-1个点可以任意排列,方案数是(totsz-sz_i +j-1)!;当然最后我们不要忘记考虑不被涂黑的点的顺序。当我们涂到剩下m个白点的时候,可以发现再涂黑一个白点的期望是\frac {totlf} {m}. 推导很简单也很关键,我还是写一写:

设期望为x,则x=\frac {m} {totlf}+\frac {totlf-m} {totlf} (x+1),得到x=\frac {totlf} {m}

由乘法原理得:

\sum\limits_{j=0}^{sz_i-1} \frac {1} {totsz!}\ast {sz\choose j}\ast (totsz-sz_i+j-1)!\ast (totsz-sz_i)\ast \Bigg( \sum\limits_{k=sz_i -j+1}^{totsz}\frac {totlf} {k} \Bigg)\ast (sz_i -j)!

Solution 2

这是一种极为简单的方法,但是十分巧妙。
类似的,考虑留下一个集合不被完全涂黑;反过来,就是要关心其它点是否被完全涂黑,类似上面的方法,我们可以推出当我们要涂黑所有关心的点的期望也是一个和式。不过注意,这时候我们只关心了我们需要涂黑的点是否被完全涂黑,可能再这个过程中,我们假定要留下的集合已经被先完全涂黑了,我们应该舍去这种情况。令f[i]表示还剩下i个被关心的点没被涂黑还需要的期望步数,所以每个集合的贡献就是f[totsz-sz_i]-(f[totsz]-t_i)t_i表示i集合在最后被涂黑的情况,因为所有t_i相加就是f[totsz],所有结果就是\sum f[totsz-sz_i]-(L-1)f[S]L为集合总数).

参考程序

Solution 1

#define forsn(u) for (int v, e = last[u]; e; e = E[e].next)

typedef std::pair<int, int> Pii;
typedef int IntAr[MAXN];

struct Edge {
    int to, next;
} E[MAXN << 1];

int N, tote, totsz, totlf, tot;
IntAr last, fac, inv, sigma, nxt, dgr;
std::vector<int> slv;

int main() {
//  Read in, add edge...

    for (int i = 1; i <= N; i++)
        if (dgr[i] == 1) ++totlf;
    int rt = dfs(1, 0).sec;
    Pii tmp = dfs(rt, 0);
    int u = rt, d = tmp.fir >> 1;
    for (; d--; u = nxt[u]);
    if (tmp.fir & 1) {
    //  直径长为奇数,分为两个集合即可
        tot = 0;
        dfs(u, nxt[u], tmp.fir >> 1);
        slv.pb(tot), totsz += tot;
        tot = 0;
        dfs(nxt[u], u, tmp.fir >> 1);
        slv.pb(tot), totsz += tot;
    }
    else {
        d = (tmp.fir >> 1) - 1;
        forsn(u) {
            tot = 0;
            dfs(v = E[e].to, u, d);
            if (!tot) continue;
            slv.pb(tot), totsz += tot;
        }
    }
    init();
    LL ans = 0;
    for (auto sz : slv)
        for (int i = 0; i < sz; i++)
            (ans += C(sz, i) * fac[totsz - sz + i - 1] % MOD * (totsz - sz) % MOD * sigma[sz - i + 1] % MOD * fac[sz - i]) %= MOD;
    (ans *= inv[totsz]) %= MOD;

    printf("%lld\n", ans);
    return 0;
}

void init() {
//  预处理阶乘、阶乘逆元...
    for (int i = totsz; i > 0; i--) sigma[i] = (sigma[i + 1] + totlf * get_inv(i) % MOD) % MOD;
}

Pii dfs(int u, int fa) {
    Pii ret(0, u);
    nxt[u] = 0;
    forsn(u) {
        if ((v = E[e].to) == fa) continue;
        Pii tmp = dfs(v, u);
        ++tmp.fir;
        if (tmp > ret) {
            ret = tmp;
            nxt[u] = v;
        }
    }
    return ret;
}

void dfs(int u, int fa, int dep) {
    if (!dep) return (void)++tot;
    forsn(u) {
        if ((v = E[e].to) == fa) continue;
        dfs(v, u, dep - 1);
    }
}

Solution 2

//  大部分声明与上面程序类似
int main() {
//  前面预处理直径、集合类似
    LL ans = 0;
//  递推求f
    for (int i = 1; i <= totlf; i++) f[i] = (f[i - 1] + (LL)totlf * get_inv(i) % MOD) % MOD;
    for (auto sz : slv) (ans += f[totsz - sz]) %= MOD;

    printf("%lld\n", ((ans - LL(cnts - 1) * f[totsz] % MOD) % MOD + MOD) % MOD);
    return 0;
}

总结

这题首先题意不能读错…
然后第一种方法可以暴力推到,至于第二种方法实在是巧妙,我和yyk理解了一个晚上…
精髓在于分析问题时我们忽略其他因素只考虑关心的元素的思想,还有将涂黑的过程转化为一个形象的排列来分析。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注