1002: [FJOI2007]轮状病毒
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 4381 Solved: 2393
[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
用基尔多夫矩阵推出一个递推式：f[i]=f[i-1]*3-f[i-2]+2 （我也不会证）
关于基尔多夫矩阵，传送门：http://www.cnblogs.com/chty/p/5868327.html
当然，得用到高精度。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
struct bignum{int len,num[];}f[],p;
int n;
bignum add(bignum a,bignum b)
{
int len; bignum c;
memset(c.num,,sizeof(c.num));
if(a.len>=b.len) len=a.len;
else len=b.len;
for(int i=;i<=len;i++)
{
c.num[i]+=a.num[i]+b.num[i];
if(c.num[i]>=)
{
c.num[i+]+=;
c.num[i]-=;
}
}
if(c.num[len]>)
len++;
c.len=len;
return c;
}
bignum Mull(bignum a,int b)
{
int i,len; bignum c;
len=a.len;
memset(c.num,,sizeof(c.num));
for(i=;i<=len;i++)
{
c.num[i]+=(a.num[i]*b);
if(c.num[i]>=)
{
c.num[i+]=c.num[i]/;
c.num[i]=c.num[i]%;
}
}
len=len+;
while(c.num[len]>)
{
c.num[len+]=c.num[len]/;
c.num[len++]%=;
}
c.len=--len;
return c;
}
bignum sub(bignum a1,bignum b1)
{
int len;
if(a1.len>b1.len) len=a1.len;
else len=b1.len;
for(int i=;i<=len;i++)
{
a1.num[i]=a1.num[i]-b1.num[i];
if(a1.num[i]<)
{
a1.num[i]+=;
a1.num[i+]--;
} }
while(a1.num[len]==&&len>) len--;
a1.len=len;
return a1;
} void print(bignum c)
{
for(int i=c.len;i>;i--)
printf("%d",c.num[i]);
printf("\n");
}
int main()
{
scanf("%d",&n);
f[].len=f[].len=p.len=;
f[].num[]=; f[].num[]=; p.num[]=;
for(int i=;i<=n;i++)
f[i]=sub(add(Mull(f[i-],),p),f[i-]);
print(f[n]);
return ;
}