bzoj 1002: [FJOI2007]轮状病毒-白红宇

bzoj 1002: [FJOI2007]轮状病毒

阅读量：5052 次

发布时间：2019-06-12

本文共 1719 字，大约阅读时间需要 5 分钟。

想了好久没想出来。

查了下题解是有递推式。

f[i]=3*f[i-1]-f[i-2]+2（p.s.至今还不明觉厉）

然后就是高精了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std;10 #define For(i,n) for(int i=1;i<=n;i++)11 #define Rep(i,n) for(int i=0;i
              
               =0;i--)16 #define MAXN (100+10)17 #define F (10000)18 int n;19 struct Highn20 {21 int a[10000],len;22 Highn(){len=0;memset(a,0,sizeof(a));}23 Highn(int b)24 {25 len=0;memset(a,0,sizeof(a));26 while (b) a[++len]=b%F,b/=F;27 if (len==0) len=1;28 }29 friend Highn operator*(int b,Highn a)30 {31 For(i,a.len) a.a[i]*=b;32 For(i,a.len) a.a[i+1]+=a.a[i]/F,a.a[i]%=F;33 if (a.a[a.len+1]) a.len++;34 return a;35 }36 friend Highn operator+(Highn b,Highn a)37 {38 Highn c;39 c.len=max(a.len,b.len);40 For(i,c.len)41 {42 c.a[i]+=a.a[i]+b.a[i];43 c.a[i+1]+=c.a[i]/F;44 c.a[i]%=F;45 }46 c.len++;47 while (!c.a[c.len]) c.len--;48 return c;49 }50 friend Highn operator-(Highn a,Highn b)51 {52 Highn c;53 c.len=max(a.len,b.len);54 For(i,c.len)55 {56 c.a[i]+=a.a[i]-b.a[i];57 if (c.a[i]<0) c.a[i]+=F,c.a[i+1]--;58 // c.a[i+1]+=c.a[i]/F;59 // c.a[i]%=F;60 }61 while (!c.a[c.len]) c.len--;62 return c;63 }64 65 void print()66 {67 printf("%d",a[len]);68 ForD(i,len-1)69 {70 printf("%04d",a[i]);71 }72 puts("");73 }74 }f[MAXN];75 int main()76 {77 // freopen(".in","r",stdin);78 // freopen(".out","w",stdout);79 scanf("%d",&n);80 f[1]=1,f[2]=5;81 if (n<=2) f[n].print();82 else83 {84 Fork(i,3,n) f[i]=3*f[i-1]-f[i-2]+2;85 f[n].print();86 }87 88 89 return 0;90 }