P2144 [FJOI2007]轮状病毒

题目描述

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

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

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

输入输出格式

输入格式：

第一行有1个正整数n。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

Solution：

　　本题打表找规律，高精码农题。

　　随便什么姿势(手推或者爆搜)，反正先打个表：$1,5,16,45,121,320,841,2205$。

　　可以用各种角度找规律：

　　　　1、稍微复杂点的规律：观察奇数项：$1^2,4^2,11^2,29^2$，指数均为$2$，而底数$a_i=3*a_{i-1}-a_{i-2},i>2$。再观察偶数项：$5*1^2,5*3^2,5*8^2,5*21^2$，系数均为$5$，指数均为$2$，而底数$a_i=3*a_{i-1}-a_{i-2},i>2$。所以我们可以奇偶分开求。

　　　　2、简单点的规律：直接整体看，发现$a_i=3*a_{i-1}-a_{i-2}+2,i>2$。

　　随便递推一波发现会爆long long，于是上线高精码农（~>_<~）。

代码：

/*Code by 520 -- 9.18*/

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define RE register

#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)

using namespace std;

const int Base=1e5;

int n,m;

struct node{

    ll f[],len;

    il void Clr(){memset(f,,sizeof(f)),len=;}

    il void Push(ll x){f[len=]=x;}

    node operator + (const node &x) const {

        node tp;tp.Clr();tp.len=max(len,x.len)+;

        For(i,,tp.len)

            tp.f[i]+=f[i]+x.f[i],

            tp.f[i+]+=tp.f[i]/Base,

            tp.f[i]%=Base;

        For(i,,tp.len) tp.f[i+]+=tp.f[i]/Base,tp.f[i]%=Base;

        while(tp.len&&!tp.f[tp.len]) tp.len--;

        return tp;

    }

    node operator - (const node &x) const {

        node tp;tp.Clr();tp.len=len+;

        For(i,,tp.len) {

            tp.f[i]+=f[i]-x.f[i];

            if(tp.f[i]<) tp.f[i+]--,tp.f[i]+=Base;

        }

        For(i,,tp.len) tp.f[i+]+=tp.f[i]/Base,tp.f[i]%=Base;

        while(tp.len&&!tp.f[tp.len]) tp.len--;

        return tp;

    }

    node operator * (const node &x) const {

        node tp;tp.Clr();tp.len=len+x.len+;

        For(i,,len) For(j,,x.len)

            tp.f[i+j-]+=f[i]*x.f[j],

            tp.f[i+j]+=tp.f[i+j-]/Base,

            tp.f[i+j-]%=Base;

        For(i,,tp.len) tp.f[i+]+=tp.f[i]/Base,tp.f[i]%=Base;

        while(tp.len&&!tp.f[tp.len]) tp.len--;

        return tp;

    }

    il void Output(){

        printf("%lld",f[len]);

        Bor(i,,len-) printf("%05lld",f[i]);

    }

}a[],tp[];

int main(){

    cin>>n,tp[].Push(),tp[].Push();

    a[].Push(),a[].Push();

    For(i,,n) a[i]=a[i-]*tp[]-a[i-]+tp[];

    a[n].Output();

    return ;

}

巴特西

P2144 [FJOI2007]轮状病毒

题目描述

输入输出格式

输入输出样例

最新文章

热门文章