[FJOI2007]轮状病毒

题目描述

轮状病毒有很多变种。许多轮状病毒都是由一个轮状基产生。一个n轮状基由圆环上n个不同的基原子和圆心的一个核原子构成。2个原子之间的边表示这2个原子之间的信息通道，如图1。

n轮状病毒的产生规律是在n轮状基中删除若干边，使各原子之间有唯一一条信息通道。例如，共有16个不同的3轮状病毒，入图2所示。

给定n(N<=100)，编程计算有多少个不同的n轮状病毒。

图见https://www.lydsy.com/JudgeOnline/problem.php?id=1002

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

题解：打表，能发现n=1，2，3，4，5……时，ans=1，5，16，45，121……

1，16，121都是完全平方数，5+4=9，45+4=49也是完全平方数。

因此处理后开方：

1，3，4，7，11……

这是一个变形的斐波那契数列。

还需要高精。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct big
{
    int s[105],len;
    void init()
    {
        len = 1;
        for(int i=1;i<=100;i++)
            s[i]=0;
    }
    void j4()
    {
        s[1]-=4;
        for(int i=1;s[i]<0;i++)
        {
            s[i+1]--;
            s[i]+=10;
        }
    }
}f[105];
int n;
big operator + (big a,big b)
{
    big ret;
    ret.init();
    ret.len = max(a.len,b.len);
    for(int i=1;i<=ret.len;i++)
        ret.s[i] = a.s[i]+b.s[i];
    for(int i=1;i<=ret.len;i++)
    {
        if(ret.s[i]>9)
        {
            ret.s[i+1]++;
            ret.s[i]%=10;
            ret.len+=(i+1>ret.len);
        }
    }
    return ret;
}
big operator * (big a,big b)
{
    big ret;
    ret.init();
    ret.len = a.len+b.len-1;
    for(int i=1;i<=a.len;i++)
        for(int j=1;j<=b.len;j++)
            ret.s[i+j-1] += a.s[i]*b.s[j];
    for(int i=1;i<=ret.len;i++)
    {
        if(ret.s[i]>9)
        {
            ret.s[i+1]+=ret.s[i]/10;
            ret.s[i]%=10;
            ret.len+=(i+1>ret.len);
        }
    }
    return ret;
}
int main()
{
    scanf("%d",&n);
    f[1].len=f[2].len=1;
    f[1].s[1]=1;
    f[2].s[1]=3;
    for(int i=3;i<=n;i++)
        f[i] = f[i-2] + f[i-1];
    f[n] = f[n] * f[n];
    if(n%2==0)f[n].j4();
    for(int i=f[n].len;i>=1;i--)
        printf("%d",f[n].s[i]);
    printf("
");
    return 0;
}