danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26247

[BZOJ 1002]轮状病毒

2016年1月24日 12:53 | Comments(0) | Category:题解 | Tags:

根据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打出来表然后交表啊。

代码: