[FJOI2007] 轮状病毒

题目链接：https://oj.hfuu.com.cn/problem/11002

结论题，递推式：Fn=3*F(n-1)-F(n-2)+2

至于怎么得出的结论又是一个神奇的递推过程。

（这个坑以后或许会填上，由 基尔霍夫矩阵 推出结论）

而且此题会爆_int128，需要高精输出。

但是这个的中间所有项又全是正数，不会出现小数减大数的情况，所以我用了一个阉割版的高精。。。

#include<iostream>
using namespace std;
int main()
{
    int n,x;
    cin>>n;
    int a[50]{},b[50]{},c[50]{};
    a[0]=1;
    b[0]=5;

    if(n==1)        //n==1时直接输出
    {
        cout<<"1"<<endl;
        return 0;
    }
    for(int i=0;i<n-2;i++)
    {
        c[0]=2;     //递推式后面的那个+2
        for(int k=0;k<50;k++)
        {
            c[k]+=3*b[k]-a[k];      //由递推式得出
            while(c[k]<0)
            {
                --c[k+1];
                c[k]+=10;
            }
            while(c[k]>=10)
            {
                ++c[k+1];
                c[k]-=10;
            }
        }
        for(int k=0;k<50;k++)
        {
            a[k]=b[k];
            b[k]=c[k];
            c[k]=0;
        }
    }
    int p=0;//用于判断从第一个不为零的数输出
    for(int j=49;j>=0;j--)      //直接倒着输出，省了变换
        {
            if(b[j]!=0)
            {
                p=1;
            }
            if(p)
            {
                cout<<b[j];
            }
        }
        cout<<endl;
    return 0;
}