[FJOI2007]轮状病毒
Time Limit:500MS Memory Limit:165536K
Total Submit:141 Accepted:63
Case Time Limit:100MS
Description
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
Input
第一行有1个正整数n。
Output
将编程计算出的不同的n轮状病毒数输出
Sample Input
Sample Output
Source
16
3
16
3做了N久的八中OJ才做第二题晕。。。
这道题首先我的想法是破环为链，再想办法做。。
对于一个链来说，设Dp[i]为长度为i的链和一个“中心”的生成树数量，可以Dp之。。
然后考虑环，枚举1节点所在的环的长度，设为Len，那么这个环的位置有Len种情况，这个环与中心连接也有Len种情况，那么这个节点对答案的贡献就是Len^2*Dp[n-Len]。。
写个高精度+一下久OK了。。。
orz刚好看到你刷过这题
本菜先写了个暴力行列式，发现精度不行，又推了个公式……囧
回复ad饕饕不绝:神牛!!!Orz!!!
回复Nehzilrz:是生成数的通用公式么。。Orz!!!
这题还可以用特增根法优化到log级别….
orz..这题我又不会做了…
回复bonism5604：Orz神牛！！！！我的是O(n^2)的囧。。。
这题存在 O(C * logn)的算法
回复WJBZBMR：DP[0]=DP[1]=1;DP[2]=3;DP[i] = DP[i-1]*3-DP[i-2];ANS = DP[i]*3-DP[i-1]*2-2DP[i]可以利用矩阵二分球的,矩阵大小3 * 3所以复杂度O(27 * log n)
回复ad饕饕不绝:神牛阿!!!!!
回复WJBZBMR：恩 我写的也是n^2的 logn没什么必要…
回复WJBZBMR：我错了，矩阵是2*2的……
回复WJBZBMR：显然是这道题的……
ORZ
丽洁神牛。。这题N^3能过么。。BZOJ又挂了没法测。。
不用测了。。凸然发现在我写的方程的一个不起眼的地方摆着一个除号。。不写了。。