題解 BZOJ 1002 【[FJOI2007]輪狀病毒】

題目連結

emm……

正解：矩陣樹定理，但是本寶寶不會求基爾霍夫矩陣。

開始考場方法：

手動模拟$n=1--5$時的答案（數不大，~~畫畫就出來了~~要畫上半個小時）。

畫出來，答案是這樣的：$1$ $5$ $16$ $45$ $121$

然後簡單根據題目出處和難度蒙了一下感覺第$n$項的答案和$n-1$,$n-2$的答案有關。

再看看增長率$(\frac{ans[n-1]}{ans[n-2]})$大概是$2--3$之間，并且比較靠近三。

于是，就想 $ans[n]$ $=$ $ans[n-1]*3$ $±$ $……$

又因為差的不是一個常數，是以

$ans[n]$ $=$ $3*ans[n-1]-ans[n-2]$ $±$ $……$

之後，驚喜的發現每個$ans[n]$ 與 $3*ans[n-1]-ans[n-2]$ 都差$2$。

最終，蒙了一個表達式：$ans[n]=$ $3*ans[n-1]-ans[n-2]+2$

看資料範圍，需要高精。

之後一臉懵逼的$AC$了。

代碼附上：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
//F(n)=3*F(n-1)-F(n-2)+2,F(1)=1,F(2)=5.;
int ans[103][10010];
int len[103];
int mul[10010];
void pluse(int x)
{
    int m=x-2;
    int n=x-1;
    int cnt=0;int l=len[n];
    for(int i=1;i<=l;i++)
    {
        mul[i]=(ans[n][i]*3+cnt)%10;
        cnt=(ans[n][i]*3+cnt)/10;
    }
    if(cnt!=0) mul[++l]=cnt;
    
    cnt=2;
    for(int i=1;i<=l;i++)
    {
        ans[x][i]=(mul[i]-ans[m][i]+cnt+100)%10;
        if(mul[i]-ans[m][i]+cnt<0) cnt=-1;
        else cnt=(mul[i]-ans[m][i]+cnt)/10;
    }
    if(cnt!=0) ans[x][l+1]=cnt,len[x]=l+1;
    else len[x]=l;
    return ;
}
int n;
int main()
{
    scanf("%d",&n);
    ans[1][1]=1;len[1]=1;
    ans[2][1]=5;len[2]=1;
    for(int i=3;i<=n;i++) pluse(i);
    for(int i=len[n];i>=1;i--) printf("%d",ans[n][i]);
    return 0;
}