题目

点这里看题目。

给定一棵 \(n\) 个结点的树。

进行如下过程：

  1. 初始时，所有结点都是白色，且计数器变量 \(c=0\)。

  2. 重复一下两个步骤：

    1. 如果所有结点都是黑色，停止该过程。

    2. 从所有不“好”的结点中，随机选择一个，将它染成黑色，并令 \(c\) 为 \(c+1\)。

一个结点为“好”的，当且仅当它和它的所有祖先都是黑色。

求过程结束时的 \(E[c] \bmod 998244353\)。

所有数据满足 \(1\le n\le 2\times 10^5\)（原版）或 \(1\le n\le 10^7\)（加强版）。

分析

有一个看起来很合理，但是貌似又不太合理的转化：

对于 \(u\in V\)，设随机变量 \(X_u\) 为 \(u\) 在随机过程中，被选中并染成黑色的次数。

因为 \(c=\sum_u X_u\)，所以 \(E[c]=\sum_u E[X_u]\)。

不用担心，这个推理过程完全完全正确。问题是，如何才能正确地计算 \(E[X_u]\)？

可以使用全期望公式吗？比如枚举一种黑色状态，计算这种状态下 \(u\) 被选中的概率？那么这种算法怎么处理“黑色状态没有改变，\(u\) 却被多次选中”的情况？

我们捋一下“随机过程”这个概念。在本题中，随机过程可以看作是一个概率空间列 \(\{(\Omega_k,\mathscr F_k,P_k)\}_{k\ge 0}\)，其中 \(\Omega_k=V^k,\mathscr F_k=2^{\Omega_k}\)。

概率测度怎么定义？首先，\(P_0[()]\) 显然应当是成立的。此后，我们当然可以按照题意，直接递推出每一个 \(P_k\)。然而，为了后续叙述不绕弯，我们此处认为 \(P_k(\omega)=n^{-k},\omega\in \Omega_k\)。

Note.

这其实就是一个经典的转化：允许“好”的结点被选中并继续被染黑，这样原先一个过程可能被插入若干个冗余“好”的结点。

相应地，新序列的概率和原先概率计算方式不同。所以在这样的变化之后原先某一个过程的概率不发生改变。具体可以自行计算验证。

进一步地，一个随机过程，其实就是一个序列列 \(\mathscr S=\{S_k\}_{k=0}^m\)，满足：

  1. 对于 \(0\le k\le m,S_k\in \Omega_k\)。

  2. 对于 \(0\le k<m\)，存在 \(u\in V\)，\(u\) 在 \(S_k\) 中从未出现过。而 \(S_m\) 恰好包含所有结点。

  3. 对于 \(0<k\le m\)，\(S_{k-1}\) 为 \(S_k\) 的长度为 \(k-1\) 的前缀（长度为 \(0\) 的前缀即为空序列）

不过，此时的随机变量似乎就不能叫做“随机变量”了。在解题中这不是一个特别重要的点，我们仍然沿用 \(X_u\) 的记号，不过一个 \(\mathscr S\) 对应的 \(X_u\) 为 \(\sum_{k=0}^m[S_k[k]=u]\)。

回头考察 \(E[X_u]\)，那就是 \(\sum_{k=0}^mP(S_k[k]=u)\)。我们要计算的就是，在任何一个合法的过程“前缀”下，\(u\) 被选中概率之和。

结合题意，我们发现 \(\sum_{k=0}^mP(S_k[k]=u)\) 可以很简单地讨论出来：如果 \(u\) 要被选中，则要么 \(u\) 的父亲还不是“好”的结点，要么 \(u\) 的父亲已经是好的结点，且 \(u\) 在前缀中还没有出现过。

要求某个结点是“好”的结点或反之都可以容斥计算。设 \(u\) 的父亲的深度为 \(d\)，我们于是有：

\[\begin{aligned} P_1&=\sum_{k=1}^d(-1)^{k-1}\binom{d}{k}\sum_{j\ge 0}\left(\frac{n-k}{n}\right)^j\\ P_2&=\sum_{k=0}^d(-1)^k\binom{d}{k}\sum_{j\ge 0}\left(\frac{n-k-1}{n}\right)^j \end{aligned} \]

首先，用等比数列求和将 \(\sum_j\) 这层和式收起来：

\[\begin{aligned} P_1&=\sum_{k=1}^d(-1)^{k-1}\binom{d}{k}\frac{n}{k}\\ P_2&=\sum_{k=0}^d(-1)^k\binom{d}{k}\frac{n}{k+1} \end{aligned} \]

注意到 \(\frac{1}{k+1}=\left.(\mathrm{E}^kx^{\underline{-1}})\right|_{x=0}\)，我们可以先用高阶差分将第二项收起来：

\[\begin{aligned} P_2 &=(-1)^dn\left.\left(\Delta^dx^{\underline {-1}}\right)\right|_{x=0}\\ &=\frac{nd!}{(d+1)!}\\ &=\frac{n}{d+1} \end{aligned} \]

不幸的是，\(P_1\) 的和式不能手动补齐 \(k=0\) 的项，因为会出现 \(\frac{n}{0}\) 而直接 GG。不过，我们可以直接手算前面若干项，可以发现有 \(1,\frac{3}{2},\frac{3}{2}+\frac{1}{3}\) 的规律，这让我们想起了调和级数。也就是说，我们可以猜测：

\[P_1=nH_d \]

猜到了结论，证明可以直接归纳法。如果不喜欢猜结论，为了让 \(k\) 可以被吸收进组合数里，我们也可以使用 \(\binom{d}{k}=\sum_{r=k-1}^{d-1}\binom{r}{k-1}\) 来降下指标，而这就是最终结果是一个级数而非单项的原因！

Remark.

如果引入 \(\frac{1}{0}\)，我们可以附加变量 \(x\)，并计算 \(x\rightarrow -1\) 的极限。理论上来说可以使用洛必达，然而我技术不过关算不出来 😢。

总而言之，如果 \(u\) 的深度为 \(d_u\)，那么答案为 \(\frac{1}{n}(P_1+P_2)=H_{d_u}\)。预处理调和级数就可以 \(O(n)\) 计算辣！

Remark.

本题的官方题解有两种做法。一种更复杂，甚至需要用到 NTT；另一种则运用了奇妙的构造，直接推出了这里的结论。我的题解写到的做法复杂程度大约介于二者之间。

我的观点是：一时的灵感可以提供很大的帮助，但是真正有效的还应该是强有力的数学工具。自己解决问题的时候，首先应该多多考虑怎么转换（比如本题如果连线性性都忘了那基本没法做），充分转换并且经过化简之后再让数学工具进行介入。

像第二种题解做法里面的构造显得过于特别，没什么参考价值。第一种题解做法倒是更加值得学习，至少按照黑点数量划分随机过程的阶段，再利用线性性计算跨过相邻阶段的期望轮数是我一直忽略了的。

代码

#include <cstdio>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 998244353;
const int MAXN = 2e5 + 5;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

int fac[MAXN], ifac[MAXN], H[MAXN];

int fa[MAXN], dep[MAXN];

int N;

inline int Qkpow( int, int );
inline int Inv( const int &a ) { return Qkpow( a, mod - 2 ); }
inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }

inline int Qkpow( int base, int indx ) {
    int ret = 1;
    while( indx ) {
        if( indx & 1 ) MulEq( ret, base );
        MulEq( base, base ), indx >>= 1;
    }
    return ret;
}

inline void Init( const int &n ) {
    fac[0] = 1; rep( i, 1, n ) fac[i] = Mul( fac[i - 1], i );
    ifac[n] = Inv( fac[n] ); per( i, n - 1, 0 ) ifac[i] = Mul( ifac[i + 1], i + 1 );
    rep( i, 1, n ) H[i] = Add( H[i - 1], Mul( ifac[i], fac[i - 1] ) );
}

int main() {
    int ans = 0;
    Read( N ), Init( N );
    rep( i, 2, N )
        Read( fa[i] ), dep[i] = dep[fa[i]] + 1;
    rep( i, 1, N ) AddEq( ans, H[dep[i] + 1] );
    Write( ans ), putchar( '\n' );
    return 0;
}

原文地址：http://www.cnblogs.com/crashed/p/16793148.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性