Cod sursa(job #3209191)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 2 martie 2024 10:30:18
Problema Patrate2 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;
#define int unsigned long long int

int ocupat, n, ans[30000], ans2[30000], aux[30000];

void inm(int a[], int x) {
    int t = 0;
    for (int i = 1; i <= a[0]; i++) {
        a[i] = a[i] * x;
        t = a[i] / 10;
        a[i] %= 10;
    }
    while (t) {
        a[++a[0]] = t % 10;
        t /= 10;
    }
}

void inmultire_nrmare(int a[], int b[], int c[]) {
    c[0] = a[0] + b[0] - 1;
    for(int i = 1; i <= a[0] + b[0]; i++)
        c[i] = 0;

    for(int i = 1; i <= a[0]; i++) {
        for(int j = 1; j <= b[0]; j++) {
            c[i + j - 1] += a[i] * b[j];
        }
    }

    int t = 0;
    for(int i = 1; i <= c[0]; i++) {
        c[i] = c[i] + t;
        t = c[i] / 10;
        c[i] = c[i] % 10;
    }

    if(t != 0) {
        c[0]++;
        c[c[0]] = t;
    }
}

void atrib(int a[], int b[]) {
    /// a primeste b
    for (int i = 0; i <= b[0]; i++)
        a[i] = b[i];
    memset(b, 0, sizeof(b));
}

signed main()
{
    freopen("patrate2.in", "r", stdin);
    freopen("patrate2.out", "w", stdout);
    cin >> n;
    if (n == 1)
    {
        cout << 2;
        return 0;
    }
    int cn = n;
    ans[0] = ans[1] = 1;
    while (cn) {
        inm(ans, 2);
        cn--;
    }
    for (int i = 1; i <= n; i++)
    {
        /// ans *= (n - i + 1) * lgpow(2LL, n - 1);
        inm(ans, (n - i + 1));
        cn = n - 1;
        memset(aux, 0, sizeof(aux));
        aux[0] = aux[1] = 1;
        while (cn) {
            inm(aux, 2);
            cn--;
        }
        inmultire_nrmare(ans, aux, ans2);
        atrib(ans, ans2); /// ans2 <- ans
    }
    for (int i=ans[0]; i >= 1; i--)
        cout << ans[i];
    return 0;
}