BZOJ上轮状病毒的题解，博客挂了，暂时发在这里存档。
参考：http://vfleaking.blog.163.com/blog/static/17480763420119685112649/
预备知识：
1.行列式的定义（包括余子式的定义）
2.行列式的几个性质
3.基尔霍夫矩阵的定义
4.矩阵树定理

问题建模：在一个具有特殊性的无向图上求生成树个数
特殊性指的就是题目中图的特定结构（一个中心连接一个环上每点）
忽略特殊性的话，对于一般的无向图，矩阵树定理告诉我们一个n点无向图的生成树个数=它的基尔霍夫矩阵的任意一个n-1余子式的行列式。
注意到用这个定理我们已经可以求解了，但是直接用行列式定义求解，复杂度爆炸。
题目中的特殊结构使得它的基尔霍夫矩阵很特别
把中心点对应的行列去掉的n-1余子式（如果把中心点视为0号点那么一共有n
+1个点，对应n余子式）都是形如：
3 -1 0 0 0 ... 0 0 0 -1
-1 3 -1 0 0 ... 0 0 0 0
0 -1 3 -1 0 ... 0 0 0 0
.......................
0 0 0 0 0 ... 0 -1 3 -1
-1 0 0 0 0 ... 0 0 -1 3

接下来的思路就是通过行列式的性质来变换行列式，使得最终行列式是一个三角行列式，再利用三角行列式的值=其对角线上的乘积这个性质计算答案

1.行列式交换两行会变号
2.将行列式中第a行乘上k在加到第b行上，行列式值不变
3.行列式某行乘上k，行列式值也乘上k

先通过性质1把第1行移动到最后一行（保持其他行的相对关系不变），设原来行列式值为B，如今A=(-1)^(n-1)*B

现在行列式长这样：

-1 3 -1 0 0 ... 0 0 0 0
0 -1 3 -1 0 ... 0 0 0 0
.......................
0 0 0 0 0 ... 0 -1 3 -1
-1 0 0 0 0 ... 0 0 -1 3
3 -1 0 0 0 ... 0 0 0 -1

我们把第1行乘上3加到最后一行，则最后一行变成
0 8 -3 0 0 ... 0 0 0 -1
再把第2行乘上8加到最后一行，最后一行又变成
0 0 21 -8 0 ... 0 0 0 -1
注意到了没？我们逐步使得原来在该行最左端的两个非0数字右移了
我们把最开始的两个数字分别记为F(1),G(1),
第k个阶段，数字分别为F(k),G(k)
一般的
若最后一行是
0 0 ... F(k) G(k) 0 ... 0 0 0 -1
总能找到
0 0 ... -1 3 -1 ... 0 0 0 -1
使得将后者乘上F(k)再加到前者使得前者的数字继续右移
F(k+1)=G(k)+3F(k)
G(k+1)=-F(k)
k in 1~n-3
当k=n-2时候有些特殊，因为这时最右边的-1要参与计算了
F(n-1)=G(n-2)+3F(n-2)
G(n-1)=-F(n-2)-1
或者我们仍然使用之前的公式，但是修改对应位置上的数字表示（不再是F(n-1),G(n-1)）
执行完这些操作后最后一行只剩下最右边两个数字了，设它们为h,i(h=F(n-1),i=G(n-1)-1)

然后我们同理变换倒数第2行，其实只要把倒数第2行左边-1,0看成3,-1就和最后一行很相似，但是倒数第二行的右边有两个数字，所以方程稍作修改
F2(1)=-1,G2(1)=0
F2(k+1)=G2(k)+3F2(k)
G2(k+1)=-F2(k)
现在倒数第二行只剩最后两个右边的数字，设为f,g（f=F2(n-1)-1,g=G2(n-1)+3)
只要把最后一行第n-1个数字消掉就形成三角矩阵了！

0 0 0 0 0 0 0 ... 0 f g
0 0 0 0 0 0 0 ... 0 h i
把倒数第2行乘上(-h/f)再加到最后一行（这里f不会为0，可以用数列知识证明）
0 0 0 0 0 0 0 ... 0 f g
0 0 0 0 0 0 0 ... 0 0 i-g*h/f
答案就是(-1)^(n-2)*f*(i-g*h/f)
根据之前提到的A=(-1)^(n-1)*B
B=f(g*h/f-i)=g*h-i*f代入化简得到F2(n)+F(n-1)-1+
|F(n-1) F2(n-1)|
|F(n-2) F2(n-2)|

之后懒得写了
参考vfk的博客吧
推出公式
轮状病毒的方案数满足递推式F(n)=3F(n-1)-F(n-2)+2，其中F(1)=1,F(2)=5