【BZOJ1002】轮状病毒
推了半天发现是打表找规律...基尔霍夫的证明方法看得不是很懂
递推式：f[n]=3*f[n-1]-f[n-2]+2，初始条件f[1]=1,f[2]=5
然后高精一下。（终于找到了一些个人比较喜欢的高精结构体打法）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=110;struct BigNum{ int a[maxn]; int l; BigNum (int _a=0) {memset(a,0,sizeof(a));a[1]=_a;l=1;} int &operator [] (int x) {return a[x];} friend BigNum operator + (const BigNum &a,const BigNum &b); friend BigNum operator - (const BigNum &a,const BigNum &b); friend BigNum operator * (const BigNum &a,const BigNum &b);}f[maxn],a2,a3,_v;BigNum operator + (const BigNum &a,const BigNum &b){ memset(_v.a,0,sizeof(_v.a)); _v.l=max(a.l,b.l); for (int i=1;i<=_v.l;i++) _v[i]+=a.a[i]+b.a[i],_v[i+1]+=_v[i]/10,_v[i]%=10; if (_v[_v.l+1]) _v.l++; return _v;}BigNum operator - (const BigNum &a,const BigNum &b){ memset(_v.a,0,sizeof(_v.a)); _v.l=a.l; for (int i=1;i<=_v.l;i++) { _v[i]+=a.a[i]-b.a[i]; if (_v[i]>=0) continue; _v[i+1]--; _v[i]+=10; } while (_v.l>1 && !_v[_v.l]) _v.l--; return _v;}BigNum operator * (const BigNum &a,const BigNum &b){ memset(_v.a,0,sizeof(_v.a)); _v.l=a.l+b.l-1; for (int i=1;i<=a.l;i++) for (int j=1;j<=b.l;j++) _v[i+j-1]+=a.a[i]*b.a[j]; for (int i=1;i<=_v.l;i++) _v[i+1]+=_v[i]/10,_v[i]%=10; if (_v[_v.l+1]) _v.l++; while (_v.l>1 && !_v[_v.l]) _v.l--; return _v;}int main(){ int n; scanf("%d",&n); f[1]=BigNum(1); f[2]=BigNum(5); a2=BigNum(2); a3=BigNum(3); for (int i=3;i<=n;i++) f[i]=f[i-1]*a3-f[i-2]+a2; for (int i=f[n].l;i;i--) printf("%d",f[n][i]); return 0;} |
评论 (0)
