Cod sursa(job #921885)

Utilizator assa98Andrei Stanciu assa98 Data 21 martie 2013 20:16:14
Problema Patrate2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

class huge
{
private:
    int v[4000];
public:
    huge()
    {
        memset(v,0,sizeof(v));
    }
    huge(int a)
    {
        memset(v,0,sizeof(v));
        while(a)
        {
            v[++v[0]]=a%10;
            a/=10;
        }
    }
    huge(const char s[210])
    {
        (*this)=huge();
        v[0]=strlen(s);
        for(int i=v[0],j=0; i>=1; i--,j++)
            v[i]=s[j]-'0';
    }
    inline huge operator +(const huge a)
    {
        huge res=huge();
        res.v[0]=max(v[0],a.v[0]);
        int t=0;
        for(int i=1; i<=res.v[0]; i++)
        {
            res.v[i]=v[i]+a.v[i]+t;
            t=res.v[i]/10;
            res.v[i]=res.v[i]%10;
        }
        if(t)
            res.v[++res.v[0]]=t;
        return res;
    }


    inline huge operator *(const huge a)
    {
        huge res=huge();
        int t=0;
        res.v[0]=a.v[0]+v[0];
        for (int i=1; i<=v[0]; i++)
            for (int j=1; j<=a.v[0]; j++)
                res.v[i+j-1]+=v[i]*a.v[j];
        for (int i=1; i<=res.v[0]; i++)
        {
            res.v[i]+=t;
            t=res.v[i]/10;
            res.v[i]%=10;
        }
        if (t) res.v[++res.v[0]]=t;
        while(res.v[res.v[0]]==0&&res.v[0]>1)
            res.v[0]--;
        return res;
    }
    inline huge operator *(const int a)
    {
        huge res=(*this);
        for(int i=1;i<=res.v[0];i++)
            res.v[i]*=a;
        int t=0;
        for(int i=1;i<=res.v[0];i++)
        {
            res.v[i]+=t;
            t=res.v[i]/10;
            res.v[i]=res.v[i]%10;
        }
        while(t)
        {
            res.v[++res.v[0]]=t%10;
            t/=10;
        }
        return res;
    }

    friend void print(huge a);
};

void print(huge a)
{
    for(int i=a.v[0]; i>=1; i--)
        printf("%d",a.v[i]);
    printf("\n");
}

huge pow(const huge n,int m) //n^m O(log2(m))
{
    if(m==0)
    {
        huge a=huge(1);
        return a;
    }
    if(m==1)
        return n;
    if(m%2==1)
        return pow(n,m-1)*n;
    huge a=pow(n,m/2);
    return a*a;
}

int main()
{
    freopen("patrate2.in","r",stdin);
    freopen("patrate2.out","w",stdout);
    int n;
    scanf("%d",&n);
    huge P=huge(1);
    for(int i=2;i<=n;i++)
        P=P*i;
    huge doi=huge(2);
    huge dp=pow(doi,n*n);
    print(P*dp);
    return 0;
}