题目描述

Description

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

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

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

Input

第一行有1个正整数n

Output

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

Sample Input

3

Sample Output

16

题目分析

很抱歉我不会证明QAQ 写这题只是为了练习高精度重载运算符

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
struct your
{
    int len,a[105],mod;
    your() { memset(a,0,sizeof a); len=1; mod=10000; }
    your(int num) { *this=num; return ; }
    your(const char *num) { *this=num; return ; }
    your operator = (const int num)
    {
        char s[105]; 
        sprintf(s,"%d",num),*this=s;
        return *this;        
    }
    your operator = (const char *num)
    {
        for(int i=0;num[i]=='0';num++);
        int tot=strlen(num);
        for(int i=0;i<tot;)
        {
            int tmp=1;
            if(i==tot) break;
            for(int j=1;j<=4;j++)
            {
                if(i==tot) break;
                a[len]+=(num[tot-i-1]-'0')*tmp;
                tmp*=10,i++;
            }
            len++;
        }
        while(len&&a[len]==0) len--;
        return *this;
    }
    your operator + (const your &x)
    {
        your tmp;
        tmp.len=max(len,x.len);
        int t=0;
        for(int i=1;i<=tmp.len;i++)
        {
            tmp.a[i]=(a[i]+x.a[i]+t)%mod;
            t=(a[i]+x.a[i]+t)/mod;
        }
        while(t) tmp.a[++tmp.len]=t%mod,t/=mod;
        return tmp;
    }
    your operator - (const your &x)
    {
        your tmp=*this;
        for(int i=1;i<=len;i++)
        {
            tmp.a[i]-=x.a[i];
            if(tmp.a[i]<0) tmp.a[i]+=mod,--tmp.a[i+1];
        }
        while(tmp.len&&tmp.a[tmp.len]==0) tmp.len--;
        return tmp;
    }
    your operator * (const your &x)
    {
        your tmp;
        tmp.len=len+x.len+1;
        for(int i=1;i<=len;i++)
            for(int j=1;j<=x.len;j++)
                tmp.a[i+j-1]+=(a[i]*x.a[j]);
        for(int i=1;i<=tmp.len;i++)
            tmp.a[i+1]+=tmp.a[i]/mod,tmp.a[i]%=mod;
        while(tmp.len&&!tmp.a[tmp.len]) tmp.len--;
        return tmp;
    }
    your operator += (const your &x)
    {
        *this=*this+x;
        return *this;
    }
    void print()
    {
        printf("%d",a[len]);
        for(int i=len-1;i>=1 ;i--) printf("%04d",a[i]);
        printf("\n");    
    }
}f[1052],iop,empt;
char sa[1050];
int main()
{   
    int n;
    scanf("%d",&n);
    f[1]=1,f[2]=5;
    for(int i=3;i<=n;i++)
    {
        iop=empt,iop=3,f[i]=f[i-1]*iop;
        iop=empt,iop=2,f[i]=f[i]+iop; 
        f[i]=f[i]-f[i-2];
    }
    f[n].print();
    return 0;
}