<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
　　轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子 
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示 
<div class='image'><a href='http://www.lydsy.com/JudgeOnline/upload/201604/1%283%29.png' target='_blank' rel='noopener noreferrer'><img src="http://www.lydsy.com/JudgeOnline/upload/201604/1%283%29.png" /></a></div>
　　N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不 
同的3轮状病毒，如下图所示 
<div class='image'><a href='http://www.lydsy.com/JudgeOnline/upload/201604/2%283%29.png' target='_blank' rel='noopener noreferrer'><img src="http://www.lydsy.com/JudgeOnline/upload/201604/2%283%29.png" /></a></div>
　　现给定n(N&lt;=100)，编程计算有多少个不同的n轮状病毒
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
　　第一行有1个正整数n
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
　　计算出的不同的n轮状病毒数输出
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
3
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
16
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
可以画出 <code>4</code> 时为 <code>45</code> 
也即
<table>
<thead>
<tr>
<th style="text-align:center">n</th>
<th style="text-align:center">结果</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">1</td>
<td style="text-align:center">1</td>
</tr>
<tr>
<td style="text-align:center">2</td>
<td style="text-align:center">5</td>
</tr>
<tr>
<td style="text-align:center">3</td>
<td style="text-align:center">16</td>
</tr>
<tr>
<td style="text-align:center">4</td>
<td style="text-align:center">45</td>
</tr>
</tbody>
</table>
可以找到 <code>dp[i] = dp[i-1] * 3 - dp[i-2] + 2</code> 的规律
虽然很难找,但是通过分类画图,应该能得出一部分,再加上猜测或许能找到规律
由于最后结果很大,因此需要 高精度计算
模板的减法有问题,耽误了好久
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cmath&gt;
#include &lt;cstring&gt;
#include &lt;iomanip&gt;
#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;string&gt;
#include &lt;vector&gt;
#include &lt;bitset&gt;
#include &lt;functional&gt;

using namespace std;

typedef long long LL;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

string ans[] = {&#34;0&#34;,&#34;1&#34;,&#34;5&#34;,&#34;16&#34;,&#34;45&#34;,&#34;121&#34;,&#34;320&#34;,&#34;841&#34;,&#34;2205&#34;,&#34;5776&#34;,&#34;15125&#34;,&#34;39601&#34;,&#34;103680&#34;,&#34;271441&#34;,&#34;710645&#34;,&#34;1860496&#34;,&#34;4870845&#34;,&#34;12752041&#34;,&#34;33385280&#34;,&#34;87403801&#34;,&#34;228826125&#34;,&#34;599074576&#34;,&#34;1568397605&#34;,&#34;4106118241&#34;,&#34;10749957120&#34;,&#34;28143753121&#34;,&#34;73681302245&#34;,&#34;192900153616&#34;,&#34;505019158605&#34;,&#34;1322157322201&#34;,&#34;3461452808000&#34;,&#34;9062201101801&#34;,&#34;23725150497405&#34;,&#34;62113250390416&#34;,&#34;162614600673845&#34;,&#34;425730551631121&#34;,&#34;1114577054219520&#34;,&#34;2918000611027441&#34;,&#34;7639424778862805&#34;,&#34;20000273725560976&#34;,&#34;52361396397820125&#34;,&#34;137083915467899401&#34;,&#34;358890350005878080&#34;,&#34;939587134549734841&#34;,&#34;2459871053643326445&#34;,&#34;6440026026380244496&#34;,&#34;16860207025497407045&#34;,&#34;44140595050111976641&#34;,&#34;115561578124838522880&#34;,&#34;302544139324403592001&#34;,&#34;792070839848372253125&#34;,&#34;2073668380220713167376&#34;,&#34;5428934300813767249005&#34;,&#34;14213134522220588579641&#34;,&#34;37210469265847998489920&#34;,&#34;97418273275323406890121&#34;,&#34;255044350560122222180445&#34;,&#34;667714778405043259651216&#34;,&#34;1748099984655007556773205&#34;,&#34;4576585175559979410668401&#34;,&#34;11981655542024930675232000&#34;,&#34;31368381450514812615027601&#34;,&#34;82123488809519507169850805&#34;,&#34;215002084978043708894524816&#34;,&#34;562882766124611619513723645&#34;,&#34;1473646213395791149646646121&#34;,&#34;3858055874062761829426214720&#34;,&#34;10100521408792494338631998041&#34;,&#34;26443508352314721186469779405&#34;,&#34;69230003648151669220777340176&#34;,&#34;181246502592140286475862241125&#34;,&#34;474509504128269190206809383201&#34;,&#34;1242282009792667284144565908480&#34;,&#34;3252336525249732662226888342241&#34;,&#34;8514727565956530702536099118245&#34;,&#34;22291846172619859445381409012496&#34;,&#34;58360810951903047633608127919245&#34;,&#34;152790586683089283455442974745241&#34;,&#34;400010949097364802732720796316480&#34;,&#34;1047242260609005124742719414204201&#34;,&#34;2741715832729650571495437446296125&#34;,&#34;7177905237579946589743592924684176&#34;,&#34;18791999880010189197735341327756405&#34;,&#34;49198094402450621003462431058585041&#34;,&#34;128802283327341673812651951847998720&#34;,&#34;337208755579574400434493424485411121&#34;,&#34;882823983411381527490828321608234645&#34;,&#34;2311263194654570182037991540339292816&#34;,&#34;6050965600552329018623146299409643805&#34;,&#34;15841633607002416873831447357889638601&#34;,&#34;41473935220454921602871195774259272000&#34;,&#34;108580172054362347934782139964888177401&#34;,&#34;284266580942632122201475224120405260205&#34;,&#34;744219570773534018669643532396327603216&#34;,&#34;1948392131377969933807455373068577549445&#34;,&#34;5100956823360375782752722586809405045121&#34;,&#34;13354478338703157414450712387359637585920&#34;,&#34;34962478192749096460599414575269507712641&#34;,&#34;91532956239544131967347531338448885552005&#34;,&#34;239636390525883299441443179440077148943376&#34;,&#34;627376215338105766356982006981782561278125&#34;,&#34;1642492255488433999629502841505270534891001&#34;};

bool Do() {
 int n;
 if(!(cin &gt;&gt; n))
 return false;

 cout &lt;&lt; ans[n] &lt;&lt; endl;
 return true;
}


int main() {
 cin.tie(0);
 cin.sync_with_stdio(false);

 while(Do());

 return 0;
}
</pre>

HYSBZ 1002.轮状病毒