BZOJ1002 [FJOI2007]轮状病毒(最小生成树计数)

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 7125  Solved: 3878
[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

题解：基尔霍夫矩阵（我也不知道是什么）推出f[i]=(f[i-1]*3-f[i-2]+2)；

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define eps 1e-8
using namespace std;
const int maxn=105;
struct bign{
    int len,s[maxn];  
    bign(){memset(s,0,sizeof(s));len=1;}
    bign(int num){*this=num;}
    bign(const char *num){*this=num;}
    bign operator = (const int num){
        char s[maxn];  sprintf(s,"%d",num);  
        *this = s;return *this;
    }
    bign operator = (const char *num){
        for(int i=0;num[i]=='0';num++);
        len=strlen(num);  
        for(int i=0;i<len;i++) s[i]=num[len-i-1]-'0';  
        return *this;
    }
    bign operator + (const bign &b) const{
        bign c;c.len=0;
        for(int i=0,g=0;g||i<max(len,b.len);i++)  {
            int x=g;
            if(i<len) x+=s[i];  
            if(i<b.len) x+=b.s[i];
            c.s[c.len++]=x%10;  
            g=x/10;
        } return c;  
    }
    void clean(){while(len > 1 && !s[len-1]) len--;return;}
    bign operator * (const bign &b){
        bign c;
        c.len=len+b.len;  
        for(int i=0;i<len;i++) for(int j=0;j<b.len;j++) c.s[i+j]+=s[i]*b.s[j];  
        for(int i=0;i<c.len;i++){
            c.s[i+1]+=c.s[i]/10;  
            c.s[i]%=10;
        } c.clean();return c;  
    }
    bign operator - (const bign &b){
        bign c;c.len=0;
        for(int i=0,g=0;i<len;i++){
            int x=s[i]-g;if(i<b.len) x-=b.s[i];  
            if(x>=0) g=0;  
            else g=1,x+=10;
            c.s[c.len++]=x;
        } c.clean();return c;  
    }
    bign operator / (const bign &b)  {
        bign c,f=0;
        for(int i=len-1;i>=0;i--){
            f=f*10;f.s[0]=s[i];
            while(!(f<b)) f=f-b,c.s[i]++;
        } c.len=len;c.clean();return c;  
    }
    bign operator % (const bign &b)  {
        bign r = *this / b;
        r = *this - r*b;
        return r;
    }
    bool operator < (const bign &b)  {
        if(len!=b.len) return len<b.len;  
        for(int i=len-1;i>=0;i--){
            if(s[i]!=b.s[i]) return s[i]<b.s[i];  
        } return false;
    }
    bool operator > (const bign &b){
        if(len!=b.len) return len>b.len;  
        for(int i=len-1;i>=0;i--){
            if(s[i]!=b.s[i]) return s[i]>b.s[i];  
        } return false;  
    }
    bool operator == (const bign &b){
        return !(*this>b)&&!(*this<b);  
    }
    bool operator >= (const bign &b){
        return (*this>b)||(*this==b);
    }
    void print(){
        for(int i=len-1;i>=0;i--) putchar(s[i]+'0');return;
    }
}f[maxn];
inline int read(){
    int x=0,sig=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
    while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
    return x*=sig;
}
inline void write(int x){
    if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
    int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
    for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
}
int n;
void init(){
    n=read();f[1]=1;f[2]=5;
    return;
}
void work(){
    for(int i=3;i<=n;i++) f[i]=f[i-1]*3-f[i-2]+2;
    return;
}
void print(){
    f[n].print();
    return;
}
int main(){init();work();print();}