【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; } |