2407 조합

#include <cstdio>
#include <cstdlib>
#include <iostream>
 
 
using namespace std;
const long long int maximum = 1e17; // 17자리씩 담아야지~
 
typedef struct big{ // 17자리씩 담아야지~
  long long int high = 0;  
  long long int low = 0;
}big;
 
big operator+(big a, big b) {
  big c;
  c.high = a.high + b.high;
 
  if (a.low + b.low > maximum) {
    c.low = a.low + b.low - maximum;
    c.high++;
  }
  else {
    c.low = a.low + b.low;
  }
  return c;
}
 
big memo[101][101];
 
big rec(int n, int k) { // nCk
  if (memo[n][k].low != 0 || memo[n][k].high != 0) {
  return memo[n][k];
  }
  else if (n <= 0) {
  return memo[n][k];
  }
  else if (k == 0 || n == k) {
    memo[n][k].low = 1;
    return memo[n][k];
  }
  else return memo[n][k] = rec(n - 1, k - 1) + rec(n - 1, k);
}
 
int main() {
  int n, m;
  big temp;
  scanf("%d %d", &n, &m);
  if (n - m < m) m = n - m;
  temp = rec(n, m);
  if (temp.high != 0) printf("%lld", temp.high);
  printf("%lld", temp.low);
  return 0;
}

조합이라고 해서 이항계수를 이용하면 쉽게 해결될 줄 알았는데 복병은 따로 있었다.

채점하는 케이스의 범위가 너무 커서 일반적인 자료형으로는 도저히 감당할 수 없었다.

그래서 아예 새로운 자료형을 만들었다.

앞 17자리, 뒤 17자리 총 34자리의 수를 표현할 수 있는 초대형 자료형이다.

이와 동시에 이항계수를 구하기 위해 이 자료형을 위한 +연산자도 오버로딩해서 정의했다.