Cod sursa(job #2905303)

Utilizator divadddDavid Curca divaddd Data 20 mai 2022 18:57:08
Problema Patrate2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#define MAX 10002
using namespace std;
typedef int NrMare[MAX];
int n;

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

void inmultire(NrMare X, int n){
    long long t = 0;
    for(int i = 1; i <= X[0]; i++){
        X[i] = X[i]*n+t;
        t = X[i]/10;
        X[i] %= 10;
    }
    while(t){
        X[++X[0]] = t%10;
        t /= 10;
    }
}

/**
. . . 5 .
5 . . . .
. . 5 . .
. 5 . . .
. . . . 5
codificare: 4 1 3 2 5 => aranjamente de n luate cate n ( a[n][n] = p[n] = n! )
pentru fiecare rand pentru a alege unde punem 1 si -1 avem 2^n moduri
deci avem
n! * ( 2^n * 2^n * 2^n * ... * 2^n ) <=> n! * 2^(n*n)
      -----------------------------
                  n ori
**/

int main()
{
    fin >> n;
    NrMare fact;
    fact[0] = fact[1] = 1;
    for(int i = 2; i <= n; i++){
        inmultire(fact, i);
    }
    for(int i = 1; i <= (n*n); i++){
        inmultire(fact, 2);
    }
    for(int i = fact[0]; i >= 1; i--){
        fout << fact[i];
    }
    return 0;
}