LOJ3045 「ZJOI2019」开关 Posted on 2020-04-11 my submission on loj.ac 参考了 zsy的博客 设 操作次之后状态为的概率操作次之后状态为的概率A(x)=∑i=0∞[操作 i 次之后状态为 s 的概率]xii!B(x)=∑i=0∞[操作 i 次之后状态为 000.....00 的概率]xii!那么(可以类比奇自然数和偶自然数的 EGF) A(x)=∏i=1nepiPx+(−1)sie−piPx2B(x)=∏i=1nepiPx+e−piPx2A(x) 和 B(x) 都可以表示为 ∑i=−PPaieiPx 的形式。 设 A(x),B(x) 对应的 OGF 为 F(x),G(x)。(ecx 对应的 OGF 为 ∑i=0∞(cx)i=11−cx) 设 操作次之后第一次达到的概率H(x)=∑i=0∞[操作 i 次之后第一次达到 s 的概率]xii!则 H(x)G(x)=F(x)H(x)=F(x)G(x)答案是 H(1)′=F′(1)G(1)−F(1)G′(1)G2(1)。 但是,因为 11−PPx 这一项在 x=1 的时候没有定义,所以不能直接算。 对 H(x) 上下同时乘以 ∏i=−PP(1−iPx),这时候的 F(x),G(x) 都是这样的形式: ∑i=1nai∏j≠i(1−jP)此时的 F(x) 对应的 F(1),F′(1) 为(由于 x=1,所以所有系数里面有 (1−PPx) 的项都没了): F(1)=aP∏i≠P(1−iP)F′(1)=∑iai∑j≠i(−jP)∏k≠i,k≠j(1−kPx)=∑i≠Pai(−1)∏k≠i,k≠P(1−kP)+aP∑j≠P(−jP)∏k≠P,k≠j(1−kP)=−(∏k≠P(1−kP))⋅(∑i≠P11−iP(ai+aP⋅iP))G(1),G′(1) 的计算同理。 Post author: zhongyuwei Post link: http://zhongyuwei.github.io/2020/04/11/LOJ3045-「ZJOI2019」开关/ Copyright Notice: All articles in this blog are licensed under BY-NC-SA unless stating additionally.