洛谷 P2144 [FJOI2007]轮状病毒 题解【数学】【数列】【高精度】

点击量：174

    规律找了一半去看了OEIS……

目录

题目描述

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

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

 

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

输入输出格式

输入格式：

第一行有1个正整数n。

 

输出格式：

将编程计算出的不同的n轮状病毒数输出

 

输入输出样例

输入样例#1：

3

输出样例#1：

16

题解：

    这个题的规律不止一个，luogu的题解里就有不少。发现这个题输入一个数输出一个数，考虑暴力找规律。于是有了这样的代码：

#include<cstdio>
#include<cstring>
struct edge
{
    int x,y;
}e[201];
int s[101];
int chos[101],n;
void init()
{
    for(int i=0;i<=n;++i)
        s[i]=i;
}
int my_find(int x)
{
    if(x[s]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)//判断是不是生成树
{
    s[my_find(y)]=my_find(x);
}

int sum=0;
void dfs(int num,int x)
{
    chos[num]=x;
    if(num==n)
    {
        init();
        int flag=0;
        for(int i=1;i<=n;++i)
            if(my_find(e[chos[i]].x)!=my_find(e[chos[i]].y))
                my_union(e[chos[i]].x,e[chos[i]].y);
            else
                flag=1;
        if(!flag)
            ++sum;
        return;
    }
    for(int i=x+1;i<=n+num+1;++i)
        dfs(num+1,i);
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        e[i].x=0,e[i].y=i;
    for(int i=1;i<n;++i)
        e[n+i].x=i,e[n+i].y=i+1;
    e[2*n].x=n,e[2*n].y=1;
    for(int i=1;i<=n+1;++i)
        dfs(1,i);
    printf("%d\n",sum);
    return 0;
}

    于是答案是这样的：

    感觉在奇数项看到了好多平方数……而且偶数项也可以拆

$$\begin{cases}
1=1^2\\
5=1^2\times 5\\
16=4^2\\
45=3^2\times 5\\
121=11^2\\
320=8^2\times 5\\
841=29^2\\
2205=21^2\times 5\\
5776=76^2\\
15125=55^2\times 5
\end{cases}$$

    但是还是找不出规律…于是就上了OEIS。

    发现答案序列是卢卡斯数-2间隔一个。

卢卡斯数：1,3,4,7,11,18,29,47,76,123,199,322,521,843,1364,2207,3571,5778,9349

    卢卡斯数推导公式同斐波那契，\(f[i]=f[i-1]+f[i-2],f[1]=1,f[2]=3\)。

    但是没有接触过卢卡斯数的人也许会知道斐波那契的规律，但是根本不会联想到卢卡斯数还会-2。但是在上面推导的平方规律中，平方数却是满足斐波那契规律的，观察到\(1,3,8,21,55\)恰好是斐波那契数列的\(2,4,6,8,10\)个，如果我们用类似的方法在\(4,11,29,76\)之间增加类似斐波那契的中间项，会发现\((3,)4,(7,)11,(17,)29,(47,)76\)这个数列也满足斐波那契规律。并且，它就是卢卡斯数列！

    这样在判断\(n\)是奇数还是偶数后就可以套公式，接着进行高精度计算了。

    则\(ans_i=\left\{\begin{matrix} Fib_i&i=2k\\ Luc_i&i=2k+1 \end{matrix}\right.k\in \mathbb{Z}\)。

    这个题还有高深的递推做法……但是好像前置技能不太完全……

Code：

#include<cstdio>
#include<cstring>
int Max(int x,int y)
{
    return x>y?x:y;
}
int ten[10]={1,10,100,1000};
struct lll
{
    int num[300];
    lll(int n)
    {
        memset(num,0,sizeof(num));
        num[1]=n;
        num[0]=1;
    }
    lll()
    {
        memset(num,0,sizeof(num));
    }
    void print()
    {
        printf("%d",num[num[0]]);
        for(int i=num[0]-1;i;--i)
        {
            if(num[i]<1000)
                printf("0");
            if(num[i]<100)
                printf("0");
            if(num[i]<10)
                printf("0");
            printf("%d",num[i]);
        }
    }
    friend lll operator +(lll a,lll b)
    {
        a.num[0]=Max(a.num[0],b.num[0])+1;
        for(int i=1;i<=a.num[0];++i)
        {
            a.num[i]+=b.num[i];
            if(a.num[i]>10000)
            {
                a.num[i]-=10000;
                a.num[i+1]++;
            }
        }
        if(!a.num[a.num[0]])
            a.num[0]--;
        return a;
    }
    friend lll operator *(lll a,lll b)
    {
        lll c;
        c.num[0]=a.num[0]+b.num[0]+1;
        for(int i=1;i<=a.num[0];++i)
            for(int j=1;j<=b.num[0];++j)
                c.num[i+j-1]+=a.num[i]*b.num[j];
        for(int i=1;i<=c.num[0];++i)
            if(c.num[i]>10000)
            {
                c.num[i+1]+=c.num[i]/10000;
                c.num[i]%=10000;
            }
        while(!c.num[c.num[0]])
            c.num[0]--;
        return c;
    }
};
lll f[105];
int main()
{
    int n;
    scanf("%d",&n);
    if(n&1)
    {
        f[1]=lll(1);
        f[2]=lll(3);
        for(int i=3;i<=n;++i)
            f[i]=f[i-1]+f[i-2];
        f[n]=f[n]*f[n];
        f[n].print();
    }
    else
    {
        f[1]=lll(1);
        f[2]=lll(1);
        for(int i=3;i<=n;++i)
            f[i]=f[i-1]+f[i-2];
        f[n]=f[n]*f[n]*lll(5);
        f[n].print();
    }
    return 0;
}