[BZOJ 1002]轮状病毒
转载请注明出处：http://danihao123.is-programmer.com/
根据Matrix-Tree定理，这题可以求出基尔霍夫矩阵，然后当成行列式求值即可
这样做并没有什么错，大概也能AC，但是时间复杂度是立方级的，并且写起来并不简单（要用到高斯消元什么的，更何况此题还要用高精度）
或许DP也可以？
不过有一个简单的递推式：d[n]=d[n-1]*3-d[n-2]+2
证明比较麻烦（绝大多数人是找规律出来的），可以到这找：http://vfleaking.blog.163.com/blog/static/17480763420119685112649
这题要用高精也太烦人了，我就用了Python写（Python语法真特么烦人啊）
Q：真要考试你交Python啊？
A：我用Python打出来表然后交表啊。
代码：
d=[0,1,5]
n=int(raw_input())
if n < 3:
print d[n]
else:
for i in range(3,n+1):
d.append(d[-1]*3-d[-2]+2)
print d[n]
评论 (0)
