首页 > 代码库 > BZOJ 1002 轮状病毒

BZOJ 1002 轮状病毒

Description

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

技术分享

Input

第一行有1个正整数n。

Output

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

Sample Input

3

Sample Output

16
 
两种做法:
1.基尔霍夫矩阵+高斯消元暴搓
2.根据基尔霍夫矩阵推出推出递推公式推出f[i]=(f[i-2]*3-f[i-1]+2)。(解释见:http://vfleaking.blog.163.com/blog/static/17480763420119685112649/)
代码如下:
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;int n;struct node{    int a[1100],l;    node()    {        memset(a,0,sizeof(a));        l = 1;    }    friend inline node operator *(int x,node &y)    {        node ret; ret.l = y.l+1;        for (int i = 1;i <= y.l;++i)        {            ret.a[i] += y.a[i]*x;            ret.a[i+1] += ret.a[i]/10;            ret.a[i] %= 10;        }        if (ret.a[ret.l] == 0) ret.l--;        return ret;    }    friend inline node operator -(node x,node y)    {        node z; z.l = max(x.l,y.l);        for (int i = 1;i <= z.l;++i)        {            z.a[i] = x.a[i]-y.a[i];            while (z.a[i] < 0)                z.a[i] += 10,x.a[i+1]--;        }        while (z.l > 1&&z.a[z.l] == 0)z.l--;        return z;    }    friend inline node operator +(node &x,int y)    {        node ret = x;        ret.a[1] += y;        for (int i = 1;i <= ret.l;++i)        {            if (ret.a[i] >= 10)                ret.a[i]-=10,ret.a[i+1]++;            else break;        }        if (ret.a[ret.l+1]) ret.l++;        return ret;    }    inline void print()    {        for (int i = l;i >= 1;--i)            printf("%d",this->a[i]);    }}f[110];int main(){    freopen("1002.in","r",stdin);    freopen("1002.out","w",stdout);    scanf("%d ",&n);    f[1] = f[1]+1; f[2] = f[2] + 5;    for (int i = 3;i <= n;++i)    {        f[i] = 3*f[i-1];        f[i] = f[i]-f[i-2];        f[i] = f[i]+2;    }    f[n].print();    fclose(stdin); fclose(stdout);    return 0;}

 

BZOJ 1002 轮状病毒