[BZOJ1002]&&[FJOI2007] 轮状病毒

2014-09-01
竞赛题解 / 数论
BZOJFJOI

描述 Description

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

[][img1] [img1]: http://61.187.179.132:808/JudgeOnline/upload/201604/1(3).png

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

[][img2] [img2]: http://61.187.179.132:808/JudgeOnline/upload/201604/2(3).png

输入格式 InputFormat

第一行有 1 个正整数 n。

输出格式 OutputFormat

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

样例输入 SampleInput

100

样例输出 SampleOutput

627376215338105766356982006981782561278125

BZOJ 1002

代码 Code

这题有各种做法，生成树计数、DP、递推、找规律都可以。

比如这里用的是 vfk 大神用基尔霍夫矩阵得出的递推式

\[ F(n)=3*F(n-1)-F(n-2)+2 , F(1)=1 , F(2)=5. \]

话说我之前用奇数偶数分开来找规律的做法不知道为什么在 BZOJ 上一直 WA。。。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct bigint
{
    int s[105];
    void adjust()
    {
        int i,j,t;
        for (i=1;i<=s[0];i++) if (s[i]>9)
        {
            s[i+1]+=s[i]/10;
            s[i]%=10;
            if (i==s[0]) s[0]++;
        }
        while (s[s[0]]==0) s[0]--;
    }
    bigint operator* (int x) const
    {
        int i,j,t;
        bigint ans;
        memset(ans.s,0,sizeof(ans.s));
        for (i=1;i<=s[0];i++) ans.s[++ans.s[0]]=s[i]*x;
        ans.adjust();
        return ans;
    }
    bigint operator- (bigint x) const
    {
        int i,j,t;
        bigint ans;
        memset(ans.s,0,sizeof(ans.s));
        t=0;
        for (i=1;i<=s[0];i++)
        {
            ans.s[i]=s[i]-t-x.s[i];
            if (ans.s[i]<0)
            {
                ans.s[i]+=10;
                t=1;
            }
            else t=0;
        }
        ans.s[0]=s[0];
        ans.adjust();
        return ans;
    }
    bigint operator+ (int x) const
    {
        int i,j,t;
        bigint ans;
        memset(ans.s,0,sizeof(ans.s));
        for (i=0;i<=s[0];i++) ans.s[i]=s[i];
        ans.s[1]+=x;
        ans.adjust();
        return ans;
    }
}f[105];
int main()
{
    read(n);
    f[1].s[1]=1;f[2].s[1]=5;
    f[1].s[0]=f[2].s[0]=1;
    for (i=3;i<=n;i++) f[i]=f[i-1]*3-f[i-2]+2;
    for (i=f[n].s[0];i>0;i--) printf("%d",f[n].s[i]);
    return 0;
}