Zoj练习

Published: by Creative Commons Licence

  • Tags:

ZOJ3754

一眼就可以看出是需要求期望步数,由于有环,因此需要矩阵运算。但是事实上,这样会TLE的。

我们可以简单推出递推公式:

\[f(i)=p_0f(0)+\sum_{j=3}p_jf(i+j)+1\]

上面f(i)表示当前值为i时,期望结束的步骤数。

很显然,当f(0)已知的情况下,上面的所有公式都是可以直接推出的,即不再存在循环依赖了。因此所有的f(i)都可以表示为关于f(0)的一阶多项式:

\[f(i)=a_if(0)+b_i\]

代入到之前的公式中,有:

\[f(i)=p_0f(0)+\sum_{j=3}p_jf(i+j)+1\\ =p_0f(0)+\sum_{j=3}p_j(a_{i+j}f(0)+b_{i+j})+1\\ =f(0)(p_0+\sum_{j=3}p_ja_{i+j})+(1+\sum_{j=3}p_jb_{i+j})\]

我们可以直接得到$a_i=p_0+\sum_{j=3}p_ja_{i+j}$,而$b_i=1+\sum_{j=3}p_jb_{i+j}$,而这里的递推公式是没有环的。直接求解即可。而$f(0)=\frac{b_i}{1-a_i}$。