汉诺塔是很著名的数学和算法游戏：有三根柱子和若干能串在柱子上、大小不同的盘子。初始时所有盘子按从上到下从大到小的顺序依次串在最左边的柱子上，每次只能把一根柱子最顶端的盘子移到另一根柱子的最顶端，且大盘子不能移到小盘子的上方，最终目的是要把所有盘子按从上到下从小到大的顺序转移到最右边的柱子。

现考虑此游戏的一个变体：取数轴的1到k部分，在a,b,c处放有三根柱子，其中$a < b < c$都是整数。a位置处的柱子上按从上到下从大到小的顺序有n个盘子。

张三从位置b开始，其目标是按普通汉诺塔规则那样把所有盘子移动到c处的柱子上，且他只能在有柱子的地方捡起或放下盘子。

不过很遗憾张三喝醉了，因此他每次移动时都将以相同的概率向左或向右走一步（除非在位置1和位置k处，此时他只能向一个方向移动）。不过，即使是在喝醉的状态下，他也仍然能按照规则来合理选择如何捡起或放下盘子。

记$E(n,k,a,b,c)$为张三按最优的方式完成游戏所需要走过的路程的期望值，此处的最优是指其捡起盘子的次数最少。

有趣的是该结果总是整数，例如可以验证$E(2,5,1,3,5)=60$以及$E(3,20,4,9,17)=2358$。

求$\sum_{n=1}^{10000}E(n,10n,3n,6n,9n)$的最后九位数字。

本题难度:

解答

令$f(a,b)$为人从a柱到b柱的期望次数，若$n$是偶数则 $$f(a,b)=f(a,c)=f(b,c)=f(c,b)=\frac{2^{n+1}-2}{6}, \quad f(b,a)=\frac{2^{n+1}-8}{6}, \quad f(c,a)=\frac{2^{n+1}+4}{6},$$ 否则 $$f(a,b)=f(b,c)=f(c,a)=f(c,b)=\frac{2^{n+1}-4}{6}, \quad f(b,a)=f(a,c)=\frac{2^{n+1}+2}{6}.$$ 令$E(a,b)$为从$a$点到$b$点的期望步数，则$e(a,b)=(b-1)^2-(a-1)^2$或$(k-a)^-(k-b)^2$（到两侧墙的距离之差）。

递推计算$\sum_{i,j=a}^cf(i,j)e(i,j)$即得最终结果$684901360$。

a=b=c=d=1
p=0
mod=10**9
res=0
for n in range(1,10001):
  a,b,c,d=3*a%mod,6*b%mod,9*c%mod,10*d%mod
  if n%2==1:
    res+=((c-1)*(c-1)-(a-1)*(a-1)+(d-a)*(d-a)-(d-c)*(d-c))*p+(c-1)*(c-1)-(a-1)*(a-1)+(d-a)*(d-a)-(d-b)*(d-b)
    p=(p*2+2)%mod
  else:
    res+=((c-1)*(c-1)-(a-1)*(a-1)+(d-a)*(d-a)-(d-c)*(d-c))*p+(d-a)*(d-a)-(d-b)*(d-b)-((d-a)*(d-a)-(d-c)*(d-c))
    p=p*2%mod
print res%mod