题目描述

轮状病毒有很多变种。许多轮状病毒都是由一个轮状基产生。一个n轮状基由圆环上n个不同的基原子和圆心的一个核原子构成。2个原子之间的边表示这2个原子之间的信息通道,如图1。

n轮状病毒的产生规律是在n轮状基中删除若干边,使各原子之间有唯一一条信息通道。例如,共有16个不同的3轮状病毒,入图2所示。

给定n(N<=100),编程计算有多少个不同的n轮状病毒。

Input

第一行有1个正整数n。

Output

将编程计算出的不同的n轮状病毒数输出

Sample Input

3

Sample Output

16


基尔霍夫矩阵推出来的(什么玩意我也不知道QAQ)
式子是$$ f[i]=3f[i-1]-2f[i-2]-2 $$

f[1]=1,f[2]=5

然后就直接拿py3水过了

 


分类: 数学题解

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
maoxiangui Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
maoxiangui
游客
maoxiangui

orz