Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cctype>
- #include <cmath>
- #include <complex>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <deque>
- #include <fstream>
- #include <iostream>
- #include <list>
- #include <map>
- #include <memory>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <string>
- #include <utility>
- #include <vector>
- #include <iomanip>
- using namespace std;
- #define REP(i,n) for(__typeof(n) i=0; i<(n); i++)
- #define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
- #define RFOR(i,a,b) for(__typeof(b) i=(a); i>(b); i--)
- #define RESET(t,value) memset((t), value, sizeof(t))
- typedef long long int64;
- typedef long double d64;
- #define READ(f) freopen(f, "r", stdin)
- #define WRITE(f) freopen(f, "w", stdout)
- #define PI acos(-1.0)
- #define INF (1<<30)
- #define eps 1e-8
- #define pb push_back
- #define ppb pop_back
- #define pii pair<double,double>
- #define G struct node
- template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
- template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
- template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
- template< class T > void setmin(T &a, T b) { if(b < a) a = b; }
- vector < int > pset;
- void initSet(int _size){ pset.resize(_size); FOR(i,0,_size-1) pset[i]=i;}
- int findSet(int i){return (pset[i]== i)?i: (pset[i] = findSet(pset[i]));}
- void unionSet(int i,int j){ pset[findSet(i)]=findSet(j);}
- bool isSameSet(int i,int j){ return findSet(i)==findSet(j);}
- #define MAX 5000
- struct Bigint {
- // representations and structures
- string a; // to store the digits
- int sign; // sign = -1 for negative numbers, sign = 1 otherwise
- // constructors
- Bigint() {} // default constructor
- Bigint( string b ) { (*this) = b; } // constructor for string
- // some helpful methods
- int size() { // returns number of digits
- return a.size();
- }
- Bigint inverseSign() { // changes the sign
- sign *= -1;
- return (*this);
- }
- Bigint normalize( int newSign ) { // removes leading 0, fixes sign
- for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- )
- a.erase(a.begin() + i);
- sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign;
- return (*this);
- }
- // assignment operator
- void operator = ( string b ) { // assigns a string to Bigint
- a = b[0] == '-' ? b.substr(1) : b;
- reverse( a.begin(), a.end() );
- this->normalize( b[0] == '-' ? -1 : 1 );
- }
- // conditional operators
- bool operator < ( const Bigint &b ) const { // less than operator
- if( sign != b.sign ) return sign < b.sign;
- if( a.size() != b.a.size() )
- return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
- for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] )
- return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
- return false;
- }
- bool operator == ( const Bigint &b ) const { // operator for equality
- return a == b.a && sign == b.sign;
- }
- // mathematical operators
- Bigint operator + ( Bigint b ) { // addition operator overloading
- if( sign != b.sign ) return (*this) - b.inverseSign();
- Bigint c;
- for(int i = 0, carry = 0; i<a.size() || i<b.size() || carry; i++ ) {
- carry+=(i<a.size() ? a[i]-48 : 0)+(i<b.a.size() ? b.a[i]-48 : 0);
- c.a += (carry % 10 + 48);
- carry /= 10;
- }
- return c.normalize(sign);
- }
- Bigint operator - ( Bigint b ) { // subtraction operator overloading
- if( sign != b.sign ) return (*this) + b.inverseSign();
- int s = sign; sign = b.sign = 1;
- if( (*this) < b ) return ((b - (*this)).inverseSign()).normalize(-s);
- Bigint c;
- for( int i = 0, borrow = 0; i < a.size(); i++ ) {
- borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
- c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
- borrow = borrow >= 0 ? 0 : 1;
- }
- return c.normalize(s);
- }
- Bigint operator * ( Bigint b ) { // multiplication operator overloading
- Bigint c("0");
- for( int i = 0, k = a[i] - 48; i < a.size(); i++, k = a[i] - 48 ) {
- while(k--) c = c + b; // ith digit is k, so, we add k times
- b.a.insert(b.a.begin(), '0'); // multiplied by 10
- }
- return c.normalize(sign * b.sign);
- }
- Bigint operator / ( Bigint b ) { // division operator overloading
- if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
- Bigint c("0"), d;
- for( int j = 0; j < a.size(); j++ ) d.a += "0";
- int dSign = sign * b.sign; b.sign = 1;
- for( int i = a.size() - 1; i >= 0; i-- ) {
- c.a.insert( c.a.begin(), '0');
- c = c + a.substr( i, 1 );
- while( !( c < b ) ) c = c - b, d.a[i]++;
- }
- return d.normalize(dSign);
- }
- Bigint operator % ( Bigint b ) { // modulo operator overloading
- if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
- Bigint c("0");
- b.sign = 1;
- for( int i = a.size() - 1; i >= 0; i-- ) {
- c.a.insert( c.a.begin(), '0');
- c = c + a.substr( i, 1 );
- while( !( c < b ) ) c = c - b;
- }
- return c.normalize(sign);
- }
- // output method
- void print() {
- if( sign == -1 ) putchar('-');
- for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
- }
- };
- Bigint dp[MAX+1];
- Bigint fib(int n) {
- if(n == 0) {
- dp[n] = "0";
- return dp[n];
- }
- if(n == 1) {
- dp[n] = "1";
- return dp[n];
- }
- if(dp[n] < Bigint("0")) {
- dp[n] = fib(n-1) + fib(n-2);
- return dp[n];
- } else {
- return dp[n];
- }
- }
- int main()
- {
- //READ("input.txt");
- Bigint minusOne = Bigint("-1");
- REP(i, MAX) dp[i] = minusOne;
- fib(MAX);
- int n;
- while(cin>>n) {
- cout<<"The Fibonacci number for "<<n<<" is ";
- dp[n].print();
- cout<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement