[FJOI2007]轮状病毒

[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了。。。

17 thoughts on “[FJOI2007]轮状病毒

  1. 回复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)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>