洛谷 P2144 BZOJ 1003 [FJOI2007]轮状病毒

题目描述

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

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

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

输入输出格式

输入格式：

第一行有1个正整数n。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

吐槽

　　今天(应该是昨天了)我的ubuntu感染wncry(想哭)2.0(惨痛经历)，重装了快一整个前半夜的系统，我感到极端的不爽，于是想把这道WC2017时就想a掉但一直搁置的题切了，发泄心中的郁闷。

解题思路

　　%%%伏特跳蚤国王VFK大佬的博客http://vfleaking.blog.163.com/blog/static/17480763420119685112649/ //555……网易博客关了，看不了了

　　答案是求一个行列式的值，经过一大长串的公式推导化简(留坑)，得到一个递推式——f[1]=1，f[2]=5，f[n+2]=f[n+1]*3-f[n]+2，n>=1（或者f[n]=f[n-1]*3-f[n-2]+2，n>=3），于是开始敲吧。

源代码

　　一开始我写了个__in128版本的

#include<bits/stdc++.h>

using namespace std;

int n;

__int128 a,b,c;

void print(__int128 x)

{

    if (x==) return;

    if (x) print(x/);

    putchar(x%+'');

}

int main()

{

    a=,b=;

    cin>>n;

    if(n==)

    {

        printf("1\n");

        return ;

    }

    if(n==)

    {

        printf("5\n");

        return ;

    }

    n-=;

    while(n--)

    {

        c=b*-a+;

        a=b;

        b=c;

    }

    print(c);

    printf("\n");

    return ;

}

　　得了90分(评测记录)。第二个n=99的点wa了，n=99时__int128都爆了，但由于不想写高精，换成了unsigned __int128，照wa不误(评测记录)

　　而且BZOJ还不支持C++11，于是只得写高精了

#include<bits/stdc++.h>

using namespace std;

int n;

int a[],b[],c[];

void print(int * c)

{

    int i=;

    while(c[i]==) i--;

    while(i>=) printf("%d",c[i--]);

}

int main()

{

    a[]=,b[]=;

    scanf("%d",&n);

    if(n==)

    {

        printf("1\n");

        return ;

    }

    if(n==)

    {

        printf("5\n");

        return ;

    }

    for(int k=;k<=n;k++)

    {

        int len=;

        while(b[len]==) len--;

        for(int i=;i<=len;i++)

        {

            c[i]=b[i]*-a[i];

        }

        c[]+=;

        for(int i=;i<;i++)

        {

            if(c[i]>)

            {

                c[i+]+=c[i]/;

                c[i]%=;

            }

            if(c[i]<)

            {

                while(c[i]<)

                    c[i]+=,c[i+]--;

            }

        }

        for(int i=;i<;i++)

        {

            a[i]=b[i],b[i]=c[i];

        }

    }

    print(c);

    printf("\n");

    return ;

}

　　想想也有几个月没写过高精了，这么基础的姿势居然都忘的差不多了，我硬是调了快1个小时……在刷裸题学习新算法的时候还是不能忘记基础啊，还要多做点综合性的题目才行啊！

巴特西

洛谷 P2144 BZOJ 1003 [FJOI2007]轮状病毒

题目描述

输入输出格式

输入输出样例

吐槽

解题思路

源代码

最新文章

热门文章