0%

LOJ3045 「ZJOI2019」开关

A(x)=i=0[操作 i 次之后状态为 s 的概率]xii!B(x)=i=0[操作 i 次之后状态为 000.....00 的概率]xii!

那么(可以类比奇自然数和偶自然数的 EGF)

A(x)=i=1nepiPx+(1)siepiPx2B(x)=i=1nepiPx+epiPx2

A(x)B(x) 都可以表示为 i=PPaieiPx 的形式。

A(x),B(x) 对应的 OGF 为 F(x),G(x)。(ecx 对应的 OGF 为 i=0(cx)i=11cx

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)

但是,因为 11PPx 这一项在 x=1 的时候没有定义,所以不能直接算。

H(x) 上下同时乘以 i=PP(1iPx),这时候的 F(x),G(x) 都是这样的形式:

i=1naiji(1jP)

此时的 F(x) 对应的 F(1),F(1) 为(由于 x=1,所以所有系数里面有 (1PPx) 的项都没了):

F(1)=aPiP(1iP)F(1)=iaiji(jP)ki,kj(1kPx)=iPai(1)ki,kP(1kP)+aPjP(jP)kP,kj(1kP)=(kP(1kP))(iP11iP(ai+aPiP))

G(1),G(1) 的计算同理。