题目描述
轮状病毒有很多变种。许多轮状病毒都是由一个轮状基产生。一个n轮状基由圆环上n个不同的基原子和圆心的一个核原子构成。2个原子之间的边表示这2个原子之间的信息通道，如图1。
n轮状病毒的产生规律是在n轮状基中删除若干边，使各原子之间有唯一一条信息通道。例如，共有16个不同的3轮状病毒，入图2所示。
给定n(N<=100)，编程计算有多少个不同的n轮状病毒。
输入输出格式
输入格式：
第一行有1个正整数n。
输出格式：
将编程计算出的不同的n轮状病毒数输出
输入输出样例
输入样例#1：
3
输出样例#1：
16
Solution：
本题打表找规律，高精码农题。
随便什么姿势(手推或者爆搜)，反正先打个表：$1,5,16,45,121,320,841,2205$。
可以用各种角度找规律：
1、稍微复杂点的规律：观察奇数项：$1^2,4^2,11^2,29^2$，指数均为$2$，而底数$a_i=3*a_{i-1}-a_{i-2},i>2$。再观察偶数项：$5*1^2,5*3^2,5*8^2,5*21^2$，系数均为$5$，指数均为$2$，而底数$a_i=3*a_{i-1}-a_{i-2},i>2$。所以我们可以奇偶分开求。
2、简单点的规律：直接整体看，发现$a_i=3*a_{i-1}-a_{i-2}+2,i>2$。
随便递推一波发现会爆long long，于是上线高精码农（~>_<~）。
代码：
/*Code by 520 -- 9.18*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int Base=1e5;
int n,m;
struct node{
ll f[],len;
il void Clr(){memset(f,,sizeof(f)),len=;}
il void Push(ll x){f[len=]=x;}
node operator + (const node &x) const {
node tp;tp.Clr();tp.len=max(len,x.len)+;
For(i,,tp.len)
tp.f[i]+=f[i]+x.f[i],
tp.f[i+]+=tp.f[i]/Base,
tp.f[i]%=Base;
For(i,,tp.len) tp.f[i+]+=tp.f[i]/Base,tp.f[i]%=Base;
while(tp.len&&!tp.f[tp.len]) tp.len--;
return tp;
}
node operator - (const node &x) const {
node tp;tp.Clr();tp.len=len+;
For(i,,tp.len) {
tp.f[i]+=f[i]-x.f[i];
if(tp.f[i]<) tp.f[i+]--,tp.f[i]+=Base;
}
For(i,,tp.len) tp.f[i+]+=tp.f[i]/Base,tp.f[i]%=Base;
while(tp.len&&!tp.f[tp.len]) tp.len--;
return tp;
}
node operator * (const node &x) const {
node tp;tp.Clr();tp.len=len+x.len+;
For(i,,len) For(j,,x.len)
tp.f[i+j-]+=f[i]*x.f[j],
tp.f[i+j]+=tp.f[i+j-]/Base,
tp.f[i+j-]%=Base;
For(i,,tp.len) tp.f[i+]+=tp.f[i]/Base,tp.f[i]%=Base;
while(tp.len&&!tp.f[tp.len]) tp.len--;
return tp;
}
il void Output(){
printf("%lld",f[len]);
Bor(i,,len-) printf("%05lld",f[i]);
}
}a[],tp[]; int main(){
cin>>n,tp[].Push(),tp[].Push();
a[].Push(),a[].Push();
For(i,,n) a[i]=a[i-]*tp[]-a[i-]+tp[];
a[n].Output();
return ;
}