BZOJ 1002--[FJOI2007]轮状病毒（高精度）

1002: [FJOI2007]轮状病毒

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 6858  Solved: 3745
[Submit][Status][Discuss]

Description

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

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

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

Input

　　第一行有1个正整数n

Output

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

Sample Input

3

Sample Output

16

题目链接：

　　　　http://www.lydsy.com/JudgeOnline/problem.php?id=1002

Solution

　　f[i]=(f[i-1]*3-f[i-2]+2)

　　然而我也不会推，只会摸鱼。。

代码

#include<iostream>

#include<cstdio>

#define LL long long

using namespace std;

int n;

int b[50],c[50],e[100];

void jia(){

    int tmp=0;

    for(int i=0;i<50;i++){

        e[i]=c[i];

        c[i]=b[i]+c[i]+tmp;

        tmp=0;

        if(c[i]>9){tmp=c[i]/10;c[i]=c[i]%10;}

        b[i]=e[i];

    }

}

void cheng(){

    int tmp=0,f;

    for(int i=0;i<=50;i++)e[i]=0;

    for(int i=0;i<30;i++){

        for(int j=0;j<30;j++)

            e[i+j]+=b[i]*b[j];

        for(int j=0;j<=48;j++){

            e[j]+=tmp;

            tmp=0;

            if(e[j]>9){tmp=e[j]/10;e[j]=e[j]%10;}

        }

    }

}

void jian(){

    e[0]-=4;

    for(int i=0;i<=48;i++){

        if(e[i]>=0)break;

        e[i]+=10;e[i+1]-=1;

    }

}

int main(){

    int f;

    b[0]=1;c[0]=3;

    scanf("%d",&n);

    for(int i=2;i<=n;i++) jia();

    cheng();

    if(n%2==0)jian();

    f=0;

    for(int i=49;i>=0;i--){

        if(e[i]>0) f=1;

        if(f==1) printf("%d",e[i]);

    }

    return 0;

}

　　

　　

This passage is made by Iscream-2001.