设 S=n∑i=1pi。
由于不同开关的操作之间有顺序，即有标号，考虑对每个开关的操作构造 EGF 并乘起来。
设 Fi(x)=∞∑n=0[n≡si(mod2)]pniS⋅xnn! 及 F(x)=n∏i=1Fi(x) F(x) 即序列 {fn} 的 EGF，其中 fn=n![xn]F(x) 表示 n 次达到指定状态的概率。
但是容易发现题目要求第一次达到指定状态的期望次数，考虑再构造一些东西。
设 gn 表示 n 次关闭全部开关的概率，hn 表示 n 次达到期望状态且是首次达到的概率。
设 f(x),g(x),h(x) 分别为 {fn},{gn},{hn} 的 OGF，则容易发现 f(x)=h(x)⋅g(x) 即 h(x)=f(x)g(x)。
再根据一些基本知识，易知所谓期望步数即 ∞∑n=0n⋅hn=∞∑n=0[xn]h′(x)=h′(1)。
考虑如何求答案。
首先易知 F(x)=n∏i=1exp(piSx)+(−1)siexp(−piSx)2G(x)=n∏i=1exp(piSx)+exp(−piSx)2
考虑把 F(x),G(x) 看做关于 exp(1Sx) 的多项式。
设 F(x)=S∑i=−SFiexp(iSx)G(x)=S∑i=−SGiexp(iSx)
系数可以通过背包 DP 求出。
易得 f(x)=S∑i=−SFi1−iSxg(x)=S∑i=−SGi1−iSx
那么根据基本知识 h′(x)=f′(x)g(x)+f(x)g′(x)g2(x)，考虑求 f(1),f′(1),g(1),g′(1)。
但是可惜的是它们并不收敛……
考虑把 f,g 乘上 (1−x)，再推一推，可得答案为 1G2iS−1∑i=−S(FiGS−FSGi)Si−S
代码：
1 |
|