【FJOI2007】bzoj1002 輪狀病毒

Description

　　輪狀病毒有很多變種，所有輪狀病毒的變種都是從一個輪狀基産生的。一個N輪狀基由圓環上N個不同的基原子

和圓心處一個核原子構成的，2個原子之間的邊表示這2個原子之間的資訊通道。如下圖所示

　　N輪狀病毒的産生規律是在一個N輪狀基中删去若幹條邊，使得各原子之間有唯一的資訊通道，例如共有16個不 同的3輪狀病毒，如下圖所示

　　現給定n(N<=100)，程式設計計算有多少個不同的n輪狀病毒

Input

　　第一行有1個正整數n Output

　　計算出的不同的n輪狀病毒數輸出

用矩陣樹定理long double精度過不了，隻好上網搜到遞推式 fi=3fi−1−fi−2+2 。我也不知道為什麼。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int p=;
struct big
{
    int a[],l;
    big operator + (const big &b) const
    {
        big ret;
        ret.a[]=;
        for (int i=;i<=l||i<=b.l;i++)
        {
            ret.a[i]+=a[i]+b.a[i];
            ret.a[i+]=ret.a[i]/p;
            ret.a[i]%=p;
        }
        ret.l=max(l,b.l);
        if (ret.a[ret.l+]) ret.l++;
        return ret;
    }
    big operator + (const int &x) const
    {
        big ret;
        ret.a[]=x;
        for (int i=;i<=l;i++)
        {
            ret.a[i]+=a[i];
            ret.a[i+]=ret.a[i]/p;
            ret.a[i]%=p;
        }
        ret.l=l;
        if (ret.a[ret.l+]) ret.l++;
        return ret;
    }
    big operator - (const big &b) const
    {
        big ret;
        ret.a[]=;
        for (int i=;i<=l;i++)
        {
            ret.a[i]+=a[i]-b.a[i];
            if (ret.a[i]<)
            {
                ret.a[i+]=-;
                ret.a[i]+=p;
            }
            else ret.a[i+]=;
        }
        ret.l=l;
        while (!ret.a[ret.l]) ret.l--;
        return ret;
    }
    big operator * (const int &x) const
    {
        big ret;
        ret.a[]=;
        for (int i=;i<=l;i++)
        {
            ret.a[i]+=a[i]*x;
            ret.a[i+]=ret.a[i]/p;
            ret.a[i]%=p;
        }
        ret.l=l;
        if (ret.a[ret.l+]) ret.l++;
        return ret;
    }
    void out()
    {
        printf("%d",a[l]);
        for (int i=l-;i;i--)
        {
            if (a[i]<) putchar('0');
            if (a[i]<) putchar('0');
            if (a[i]<) putchar('0');
            printf("%d",a[i]);
        }
        putchar('\n');
    }
}f[];
int n;
int main()
{
    scanf("%d",&n);
    f[].l=f[].a[]=f[].l=;
    f[].a[]=;
    for (int i=;i<=n;i++)
        f[i]=f[i-]*-f[i-]+;
    f[n].out();
}