Cod sursa(job #896320)

Utilizator sebii_cSebastian Claici sebii_c Data 27 februarie 2013 15:06:58
Problema Patrate2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <cstdio>

#include <iterator>
#include <vector>

using namespace std;

class bigint : vector<int> {
private:
    static const int base = 10000;

public:
    bigint() : vector<int>() {}
    bigint(int n) {
        while (n) {
            push_back(n % base);
            n /= base;
        }
    }

    bigint operator+(bigint);
    bigint operator*(bigint);
    bigint pow(int);
    void print();
};

bigint bigint::operator+(bigint b)
{
    bigint res;
    if (size() < b.size())
        resize(b.size());
    if (b.size() < size())
        b.resize(size());

    int carry = 0;
    for (int i = 0; i < size(); ++i) {
        int d = (*this)[i] + b[i] + carry;
        res.push_back(d % base);
        carry = d / base;
    }
    if (carry != 0)
        res.push_back(carry);

    return res;
}

bigint bigint::operator*(bigint b)
{
    bigint res;

    for (int i = 0; i < size(); ++i) {
        bigint aux;
        for (int k = 0; k < i; ++k)
            aux.push_back(0);

        int digit = (*this)[i];
        int carry = 0;
        for (int j = 0; j < b.size(); ++j) {
            int d = b[j] * digit + carry;
            aux.push_back(d % base);
            carry = d / base;
        }
        if (carry != 0)
            aux.push_back(carry);

        res = res + aux;
    }

    return res;
}

bigint bigint::pow(int n)
{
    bigint res = bigint(1);
    bigint base = *this;

    while (n) {
        if (n % 2 == 1)
            res = res * base;
        base = base * base;
        n /= 2;
    }

    return res;
}

void bigint::print()
{
    bool first = true;
    vector<int>::reverse_iterator rit;
    for (rit = rbegin(); rit != rend(); ++rit) {
        if (first) {
            printf("%d", *rit);
            first = false;
        } else {
            printf("%04d", *rit);
        }
    }
    printf("\n");
}

const int MAXN = 101;

bigint fact[MAXN];

void factorial(int n)
{
    fact[0] = bigint(1);
    for (int i = 1; i <= n; ++i)
        fact[i] = fact[i - 1] * bigint(i);
}

int main()
{
    freopen("patrate2.in", "r", stdin);
    freopen("patrate2.out", "w", stdout);

    int n;
    scanf("%d", &n);

    factorial(n);
    bigint res = fact[n] * bigint(2).pow(n * n);
    res.print();

    return 0;
}