Cod sursa(job #2788030)

Utilizator Gabriel_DascalescuGabriel Dascalescu Gabriel_Dascalescu Data 24 octombrie 2021 18:37:29
Problema Patrate2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.45 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("patrate2.in");
ofstream out("patrate2.out");

const int MAXDIGITS = 10000; //1024
const int Base = 10;

//clasa huge numbers
class HUGE_NUM
{
private:
    int x[MAXDIGITS];
public:
    //constructorii
    HUGE_NUM()
    {
        memset(x,0,sizeof(x));
        x[0]=1;
    }
    HUGE_NUM(int n)
    {
        memset(x,0,sizeof(x));
        x[0]=0;
        do
        {
            ++x[0];
            x[x[0]] = n%10;
            n/= 10;
        }
        while(n>0);
    }
    HUGE_NUM(const HUGE_NUM &other)//copierea unui numar mare
    {
        memcpy(x, other.x, sizeof(x));
    }
    int cmp(const HUGE_NUM &other)//comparare a doua huge-uri
    {
        if(x[0]>other.x[0])
            return 1;
        else if(x[0]<other.x[0])
            return -1;
        else
        {
            for(int i=x[0]; i>0; i--)
            {
                if(x[i]>other.x[i])
                    return 1;
                else if(x[i]<other.x[i])
                    return -1;
            }
            return 0;
        }
    }
    void print()
    {
        for(int i=x[0]; i>0; i--)
        {
            out<<x[i];
        }
    }
    //supraincarcarea operatorilor aritmetici
    HUGE_NUM operator+(const HUGE_NUM &other);
    HUGE_NUM operator+=(const HUGE_NUM &other);//+=
    HUGE_NUM operator-(const HUGE_NUM &other);//scadere
    HUGE_NUM operator-=(const HUGE_NUM &other);//-=
    HUGE_NUM operator*(int k);//inmultire cu scalar
    HUGE_NUM operator*=(int k);//*= cu scalar
    HUGE_NUM operator*(const HUGE_NUM &other);//inmultire cu huge
    HUGE_NUM operator*=(const HUGE_NUM &other);//*= cu huge
    HUGE_NUM operator/(int k);//impartire cu int
    HUGE_NUM operator/(const HUGE_NUM &other);
    long long operator%(int k);
    //supraincarcarea operatorilor relationali
    bool operator==(const HUGE_NUM &other);
    bool operator<(const HUGE_NUM &other);
    bool operator<=(const HUGE_NUM &other);
    bool operator>(const HUGE_NUM &other);
    bool operator>=(const HUGE_NUM &other);
    bool operator!=(const HUGE_NUM &other);
};

HUGE_NUM HUGE_NUM::operator+=(const HUGE_NUM &other)
{
    int i, tr, aux;
    x[0] = max(x[0], other.x[0]);
    for(i=1, tr=0; i<=x[0]; i++)
    {
        aux = x[i]+other.x[i] +tr;
        x[i] = aux%Base;
        tr = aux/Base;
    }
    if(tr)
    {
        x[0]++;
        x[x[0]]=tr;
    }
}

long long HUGE_NUM::operator%(int k)
{
    long long c=0;
    for(int i=x[0]; i>=1; i--)
    {
        c = (10*c +x[i])%k;
        c%=k;
    }
    return c;
}

HUGE_NUM HUGE_NUM::operator*=(int k)
{
    int i, car =0, aux;
    for(int i=1; i<=x[0]; i++)
    {
        aux = x[i]*k+car;
        x[i] =  aux%Base;
        car = aux/ Base;
    }
    while(car >0)
    {
        x[0]++;
        x[x[0]] = car%Base;
        car /= Base;
    }
}

HUGE_NUM HUGE_NUM::operator*(const HUGE_NUM &other)
{
    HUGE_NUM c;
    int i, j, transport=0;
    c.x[0] = x[0] + other.x[0] -1;
    for(i=1; i<=x[0]; i++)
    {
        for(j=1; j<=other.x[0]; j++)
        {
            c.x[i+j-1]+=x[i]*other.x[j];
        }
    }
    for(i=1; i<=c.x[0]; i++)
    {
        transport += c.x[i];
        c.x[i] = transport %Base;
        transport/=Base;
    }
    while(transport>0)
    {
        c.x[0]++;
        c.x[c.x[0]] = transport%Base;
        transport/=Base;
    }
    return c;
}

bool HUGE_NUM::operator==(const HUGE_NUM &other)
{
    return(*this).cmp(other)==0;
}

bool HUGE_NUM::operator<(const HUGE_NUM &other)
{
    return(*this).cmp(other)==-1;
}

bool HUGE_NUM::operator>(const HUGE_NUM &other)
{
    return(*this).cmp(other)==1;
}

bool HUGE_NUM::operator>=(const HUGE_NUM &other)
{
    return(*this).cmp(other)>=0;
}

bool HUGE_NUM::operator<=(const HUGE_NUM &other)
{
    return(*this).cmp(other)<=0;
}

bool HUGE_NUM::operator!=(const HUGE_NUM &other)
{
    return(*this).cmp(other)!=0;
}

HUGE_NUM fast_exp_huge(HUGE_NUM basa, int n)
{
    HUGE_NUM p(1), bb(basa);
    for(; n; n=n>>1)
    {
        if(n&1)
        {
            p=p*bb;
        }
        bb=bb*bb;
    }
    return p;
}

int n;

int main()
{
    in>>n;
    HUGE_NUM a(1);
    for(int i=1; i<=n; i++)
    {
        a*=i;
    }
    HUGE_NUM basa(2);
    HUGE_NUM rasp(0);
    rasp = fast_exp_huge(basa, n*n);
    rasp = rasp* a;
    rasp.print();
    return 0;
}