题解 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[][];

int len[];

int mul[];

void pluse(int x)

{

    int m=x-;

    int n=x-;

    int cnt=;int l=len[n];

    for(int i=;i<=l;i++)

    {

        mul[i]=(ans[n][i]*+cnt)%;

        cnt=(ans[n][i]*+cnt)/;

    }

    if(cnt!=) mul[++l]=cnt;

    cnt=;

    for(int i=;i<=l;i++)

    {

        ans[x][i]=(mul[i]-ans[m][i]+cnt+)%;

        if(mul[i]-ans[m][i]+cnt<) cnt=-;

        else cnt=(mul[i]-ans[m][i]+cnt)/;

    }

    if(cnt!=) ans[x][l+]=cnt,len[x]=l+;

    else len[x]=l;

    return ;

}

int n;

int main()

{

    scanf("%d",&n);

    ans[][]=;len[]=;

    ans[][]=;len[]=;

    for(int i=;i<=n;i++) pluse(i);

    for(int i=len[n];i>=;i--) printf("%d",ans[n][i]);

    return ;

}

巴特西

题解 BZOJ 1002 【[FJOI2007]轮状病毒】

最新文章

热门文章