Cod sursa(job #651298)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 20 decembrie 2011 02:44:53
Problema Patrate2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdint.h>

#include <string>

class BigInt {
public:
  explicit BigInt(uint64_t x = 0) {
    m_len = 10;
    memset(m_cif, 0, sizeof(m_cif));
    for (uint32_t i = 0; x; ++i) {
      m_cif[i] = x % sm_base;
      x /= sm_base;
    }
    fix();
  }

  BigInt& operator*=(uint32_t scalar) {
    for (int i = m_len - 1; i >= 0; --i) {      
      uint64_t temp = ((uint64_t)m_cif[i]) * ((uint64_t)scalar);
      m_cif[i + 2] += (temp / sm_base) / sm_base;
      m_cif[i + 1] += (temp / sm_base) % sm_base;
      m_cif[i] = temp % sm_base;
    }
    m_len += 2;
    fix();
    return *this;
  }

  BigInt& operator+=(BigInt& other) {
    for (uint32_t i = 0; i < other.m_len; ++i)
      m_cif[i] += other.m_cif[i];
    m_len = std::max(m_len, other.m_len);
    fix();
    return *this;
  }

  void print(std::string& output) {
    fix();
    if (!m_len) { output = "0"; return; }
    
    output.clear();
    add_digit(m_cif[m_len - 1], false, output);
    for (int i = m_len - 2; i >= 0; --i)
      add_digit(m_cif[i], true, output);
  }

  void raw_print() {
    fix();
    
    printf("%lu :", (unsigned long)m_len);
    for (int i = m_len - 1; i >= 0; --i)
      printf(" %lu", (unsigned long)m_cif[i]);
    printf("\n");
  }
  
private:
  void fix() {
    for (int i = 0; i < (signed)m_len; ++i) {
      if (m_cif[i] >= sm_base) {
	m_cif[i + 1] += m_cif[i] / sm_base;
	m_cif[i] %= sm_base;
	if (i + 1 == (signed)m_len) ++m_len;
      }
    }
    while (m_len && m_cif[m_len - 1] == 0) --m_len;
  }

  void add_digit(uint32_t digit, bool force_len, std::string& str) {
    char buffer[128];
    sprintf(buffer, force_len ? "%4.4lu" : "%lu", (unsigned long)digit);
    str += buffer;
  }

  static const uint32_t sm_base = 10000;
  uint32_t m_cif[8192], m_len;
};


#define FISIN   "patrate2.in"
#define FISOUT  "patrate2.out"

int n;

int main() {
  FILE *fin = fopen(FISIN, "rt");
  FILE *fout = fopen(FISOUT, "wt");

  fscanf(fin, "%d", &n);
  BigInt rez(1);

  for (int i = 1; i <= n; ++i)
    rez *= i;

  for (int pow = n * n; pow;) {
    int now = std::min(pow, 31);
    rez *= (1 << now);
    pow -= now;
  }

  std::string result; rez.print(result);

  fprintf(fout, "%s\n", result.c_str());

  fclose(fout);
  fclose(fin);
  return 0;
}