BZOJ 1002 - 轮状病毒 - [基尔霍夫矩阵（待补）+高精度]

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1002

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] \times 3 - f[i-2] + 2$。

题解：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

struct BigInt

{

    static const int maxdigit=;

    int len,d[maxn];

    void clean(){while(len> && !d[len-]) len--;}

    string str()const

    {

        string s;

        for(int i=;i<len;i++) s+=d[len--i]+'';

        return s;

    }

    BigInt(){memset(d,,sizeof(d));len=;}

    BigInt(int num){*this=num;}

    BigInt(char* num){*this=num;}

    bool operator<(const BigInt& oth)const

    {

        if(len!=oth.len) return len<oth.len;

        for(int i=len-;i>=;i--) if(d[i]!=oth.d[i]) return d[i]<oth.d[i];

        return false;

    }

    bool operator>(const BigInt& oth)const{return oth<*this;}

    bool operator<=(const BigInt& oth)const{return !(oth<*this);}

    bool operator>=(const BigInt& oth)const{return !(*this<oth);}

    bool operator!=(const BigInt& oth)const{return oth<*this || *this<oth;}

    bool operator==(const BigInt& oth)const{return !(oth<*this) && !(*this<oth);}

    BigInt operator=(const char* num)

    {

        memset(d,,sizeof(d));

        len=strlen(num);

        for(int i=;i<len;i++) d[i]=num[len--i]-'';

        clean();

        return *this;

    }

    BigInt operator=(int num)

    {

        char s[];

        sprintf(s,"%d",num);

        return *this=s;

    }

    BigInt operator+(const BigInt& oth)const

    {

        BigInt c;

        c.len=max(len,oth.len);

        for(int i=;i<=c.len;i++) c.d[i]=;

        for(int i=;i<c.len;i++)

        {

            c.d[i]+=(i<len?d[i]:)+(i<oth.len?oth.d[i]:);

            c.d[i+]+=c.d[i]/;

            c.d[i]%=;

        }

        c.len+=(c.d[c.len]>);

        c.clean();

        return c;

    }

    BigInt operator-(const BigInt& oth)const

    {

        BigInt c=*this;

        if(c<oth) printf("Produce negative number!\n");

        int i;

        for(i=;i<oth.len;i++)

        {

            c.d[i]-=oth.d[i];

            if(c.d[i]<) c.d[i]+=, c.d[i+]--;

        }

        while(c.d[i]<) c.d[i++]+=, c.d[i]--;

        c.clean();

        return c;

    }

    BigInt operator*(const BigInt& oth)const

    {

        BigInt c;

        for(int i=;i<len;i++) for(int j=;j<oth.len;j++) c.d[i+j]+=d[i]*oth.d[j];

        for(int i=;i<len+oth.len || !c.d[i];c.len=++i) c.d[i+]+=c.d[i]/, c.d[i]%=;

        c.clean();

        return c;

    }

    BigInt operator/(const BigInt& oth)const

    {

        BigInt c=*this, r=;

        for(int i=;i<len;i++)

        {

            r=r*+c.d[len--i];

            int j;

            for(j=;j<;j++) if(r<oth*(j+)) break;

            c.d[len--i]=j;

            r=r-oth*j;

        }

        c.clean();

        return c;

    }

    BigInt operator%(const BigInt& oth)

    {

        BigInt r=;

        for(int i=;i<len;i++)

        {

            r=r*+d[len--i];

            int j;

            for(j=;j<;j++) if(r<oth*(j+)) break;

            r=r-oth*j;

        }

        return r;

    }

    BigInt operator+=(const BigInt& oth)

    {

        *this=*this+oth;

        return *this;

    }

    BigInt operator*=(const BigInt& oth)

    {

        *this=*this*oth;

        return *this;

    }

    BigInt operator-=(const BigInt& oth)

    {

        *this=*this-oth;

        return *this;

    }

    BigInt operator/=(const BigInt& oth)

    {

        *this=*this/oth;

        return *this;

    }

};

istream& operator>>(istream& in, BigInt& x)

{

    string s;

    in>>s;

    x=s.c_str();

    return in;

}

ostream& operator<<(ostream& out,const BigInt& x)

{

    out<<x.str();

    return out;

}

int n;

BigInt f[maxn];

int main()

{

    cin>>n;

    f[]=;

    f[]=;

    for(int i=;i<=n;i++) f[i]=(f[i-]*-f[i-]+);

    cout<<f[n]<<endl;

}