Cod sursa(job #2328871)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 26 ianuarie 2019 11:10:10
Problema Patrate2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

ifstream f("baza.in");
ofstream g("baza.out");

int nr[4000], n, lnr;
int re[4000], lre;
int fact[4000], lfact;
int au[4000], lau;
int total1[4000], ltotal1 = 0;

void inmultire(int a[], int la, int nr, int rez[], int &lb)
{
    for(int i = 0; i<max(la, lb); i++)
    {
        rez[i] += a[i]*nr;
        rez[i+1]+=rez[i]/10;
        rez[i] = rez[i]%10;
    }
    lb = max(la, lb);
    while(rez[lb] != 0)
    {
        rez[lb+1]+=rez[lb]/10;
        rez[lb] = rez[lb]%10;
        lb++;
    }
    if(nr == 0)
        lb = 0;
}

int aduna(int a[], int la, int b[], int lb)
{
    for(int i = 0; i<lb; i++)
    {
        a[i]+=b[i];
        a[i+1]+=a[i]/10;
        a[i] = a[i]%10;
    }
    la = max(la, lb);
    while(a[la] != 0)
    {
        a[la+1]+=a[la]/10;
        a[la] = a[la]%10;
        la++;
    }
    return la;
}

void inmult2Sir(int a[], int la, int b[], int lb, int total[], int &ltotal)
{
    int rez[4000], lrez;
    for(int i = 0; i<la; i++)
    {
        lrez = 0;
        memset(rez, 0, sizeof(rez));
        inmultire(b, lb, a[i], rez, lrez);
        ltotal = i+aduna(total+i, ltotal-i, rez, lrez);
    }
}

void copySir(int a[], int &la, int b[], int lb)
{
    la = lb;
    for(int i = 0; i<lb; i++)
    {
        a[i] = b[i];
    }
}

void putLog(int put, int a[], int la, int rez[], int &lrez)
{
    int aux[4000], laux;
    while(put)
    {
        if(put%2==0)
        {
            memset(aux, 0, sizeof(aux));
            laux = 0;
            inmult2Sir(a, la, a, la, aux, laux);
            copySir(a, la, aux, laux);
            put/=2;
        }
        else
        {
            memset(aux, 0, sizeof(aux));
            laux = 0;
            inmult2Sir(rez, lrez, a, la, aux, laux);
            copySir(rez, lrez, aux, laux);
            put--;
        }
    }
}

void r()
{
    scanf("%d", &n);
    nr[0] = 2;
    lnr = 1;
    lre = 1;
    re[0] = 1;
    putLog(n*n, nr, lnr, re, lre);

    fact[0] = 1;
    lfact = 1;
    for(int i = 1; i<=n; i++)
    {
        memset(au, 0, sizeof(au));
        lau = 0;
        inmultire(fact, lfact, i, au, lau);
        copySir(fact, lfact, au, lau);
    }

    ///*********************
    ///fact * re

    inmult2Sir(fact, lfact, re, lre, total1, ltotal1);

    for(int i = ltotal1-1; i>=0; i--)
    {
        printf("%d", total1[i]);
    }
}

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