SkyWT / 博客 / BZOJ1002 轮状病毒 题解

BZOJ1002 轮状病毒 题解

2018 年 3 月 14 日 12:28


BZOJ原题链接)这题是可以推出公式的:F[i]=F[i-1]*3-F[i-2]+2。套个高精度就好了。(由于需要用到的知识太复杂,推不来……)(其实可以写个暴力推出来)

代码如下:

#include
#include
#include
#include
using namespace std;
const int maxn=105,maxlen=105,tt=10000;
int n;
struct Bigint{
    int len,a[maxlen];
    Bigint(){len=0;memset(a,0,sizeof(a));}
    Bigint operator =(int b){
        while (b) a[++len]=b%tt,b/=tt;
    }
    Bigint operator +(Bigint b){
        Bigint c;memset(c.a,0,sizeof(c.a));
        c.len=max(len,b.len);
        for (int i=1;i<=c.len;i++){
            c.a[i]+=a[i]+b.a[i];
            c.a[i+1]+=c.a[i]/tt;
            c.a[i]%=tt;
        }
        if (c.a[c.len+1]) c.len++;
        return c;
    }
    Bigint operator -(Bigint b){
        Bigint c;memset(c.a,0,sizeof(c.a));
        c.len=len;
        for (int i=1;i<=c.len;i++){
            c.a[i]+=a[i]-b.a[i]+tt;
            c.a[i+1]+=c.a[i]/tt-1;
            c.a[i]%=tt;
        }
        if (!c.a[c.len]) c.len--;
        return c;
    }
    Bigint operator *(int b){
        Bigint c;memset(c.a,0,sizeof(c.a));
        c.len=len;
        for (int i=1;i<=c.len;i++){
            c.a[i]+=a[i]*b;
            c.a[i+1]+=c.a[i]/tt;
            c.a[i]%=tt;
        }
        while (c.a[c.len+1]) c.len++;
        return c;
    }
    void write(){
        printf("%d",a[len]);
        for (int i=len-1;i>=1;i--) printf("%04d",a[i]);
    }
}f[4];
int main(){
    scanf("%d",&n);
    Bigint two;two=2;
    f[1]=1;f[2]=5;
    for (int i=3;i<=n;i++) f[i%4]=f[(i-1+4)%4]*3-f[(i-2+4)%4]+two;
    f[n%4].write();printf("\n");
    return 0;
}

暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)