1002: [FJOI2007]轮状病毒
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 6917 Solved: 3777
[Submit][Status][Discuss]
Description
轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示
N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不
同的3轮状病毒，如下图所示
现给定n(N<=100)，编程计算有多少个不同的n轮状病毒
Input
第一行有1个正整数n
Output
计算出的不同的n轮状病毒数输出
Sample Input
3
Sample Output
16
HINT
Source
题解：
一道及其艰辛的推导题；（感觉bzoj的前两个题对新人不太友好啊）
当然可以用基尔霍夫矩阵；
打表可得$g_i = 3g_{i-1} - g_{i-2} + 2$；再用一个高精度就好了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=,base = 1e4;
int n;
struct Bign{
int c[N],len;
Bign(){memset(c,,sizeof(c));len=;}
void zero(){while(len&&!c[len])len--;}
void print(){
zero();
printf("%d",c[len]);
Don(i,len-,)printf("%04d",c[i]);
puts("");
}
Bign operator -(const Bign&A){
Bign ret;
ret.len = len;
for(int i=;i<=len;i++){
ret.c[i] += c[i] - A.c[i];
if(ret.c[i]<){
ret.c[i] += base;
ret.c[i + ] --;
}
}
ret.zero();
return ret;
}
Bign operator +(const int&A){
Bign ret;
ret = *this;
ret.len = len + ;
ret.c[] += A;
for(int i=;i<=len;i++){
if(ret.c[i]>=base){
ret.c[i] -= base;
ret.c[i+] ++;
}
}
ret.zero();
return ret;
}
Bign operator *(const int&A){
Bign ret;
ret.len = len + ;
for(int i=;i<=len;i++){
ret.c[i] = c[i] * A;
}
for(int i=;i<=len;i++){
if(ret.c[i]>=base){
ret.c[i+]+=ret.c[i]/base;
ret.c[i] %= base;
}
}
ret.zero();
return ret;
}
}f[N];
int main(){
freopen("bzoj1002.in","r",stdin);
freopen("bzoj1002.out","w",stdout);
scanf("%d",&n);
f[].len = ;
f[].c[] = ;
f[].len = ;
f[].c[] = ;
//f[1].print();
//f[2].print();
for(int i=;i<=n;i++){
f[i] = f[i-]* - f[i-] + ;
// f[i].print();
}
f[n].print();
return ;
}//by tkys_Austin;