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;
}