轮状病毒

【题目描述】

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

【输入描述】

第一行有1个正整数n。

【输出描述】

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

【样例输入】

3

【样例输出】

16

源代码：

#include<cstdio>
int n,num[101],f[101][1001]={0};
void x1(int t)
{
    int k(0);
    for (int a=1;a<=num[t];a++)
    {
        k+=f[t][a]*3;
        f[t+1][a]=k%10;
        k/=10;
    }
    num[t+1]=num[t];
    while (k)
    {
        f[t+1][++num[t+1]]=k%10;
        k/=10;
    }
}
void x2(int t)
{
    int k=2;
    for (int a=1;a<=num[t];a++)
    {
        k+=f[t][a];
        f[t][a]=k%10;
        k/=10;
    }
    while (k)
    {
        f[t][++num[t]]=k%10;
        k/=10;
    }
}
void x3(int t) //高精度减法。
{
    for (int a=1;a<=num[t+2];a++)
    {
        f[t+2][a]-=f[t][a];
        if (f[t+2][a]<0)
        {
            f[t+2][a+1]--;
            f[t+2][a]+=10;
        }
    }
    bool k(0);
    for (int a=num[t+2];!k;a--)
      if (f[t+2][a])
          k=true;
      else
        num[t+2]--;
}
int main()
{
    scanf("%d",&n);
    f[1][1]=1;
    f[2][1]=5;
    num[1]=num[2]=1;
    for (int a=3;a<=n;a++)
    {
        x1(a-1);
        x2(a);
        x3(a-2);
    }
    for (int a=num[n];a>0;a--)
      printf("%d",f[n][a]);
    return 0;
}

/*
    运用“基尔霍夫矩阵”推出动态转移方程：f[i]=3*f[i-1]-f[i-2]+2。
    虽然我不会，但不得不感叹真是神奇的数学。
    暴力解法：
        1.画图求1-5的解：1 5 16 45 121 ...
        2.观察数列找规律：1*1 3*3-4 4*4 7*7-4 11*11 ...（向完全平方数上面推）
        3.与Fabonacci数列同理，偶数项须减4。
    光辉始于猜测。
*/