polygons solution

polygons.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;

long long degree(long long a, long long k, long long p) {
  long long res = 1;
  long long cur = a;

  while (k) {
    if (k%2) {
      res = (res * cur)%p;
    }
    k /= 2;
    cur = (cur * cur) % p;
  }
  return res;
}


int get_degree(long long n, long long p) { // returns the degree with which p is in n!
  int degree_num = 0;
  long long u = p;
  long long temp = n;
  while (u <= temp) {
    degree_num += temp/u;
    u *= p;
  }
  return degree_num;
}

std::map<std::pair<long long, long long>, long long> memo;
long long combinations(int n, int k, long long p) {
  if (n < k) return 0;
  if (n == 0 && k == 0) return 1;
    
    map<std::pair<long long, long long>, long long>::iterator it;

   if((it = memo.find(std::make_pair(n, k))) != memo.end()) {
        return it->second;
   }
   else
   {
  int num_degree = get_degree(n,p) - get_degree(n- k,p);
  int den_degree = get_degree(k,p);
  
  long long res = 1;
  for (long long i = n; i > n- k; --i) {
    long long ti = i;
    while(ti % p == 0) {
      ti /= p;
    }
    res = (res *ti)%p;
  }
  long long denom = 1;
  for (long long i = 1; i <= k; ++i) {
    long long ti = i;
    while(ti % p == 0) {
      ti /= p;
    }
    denom = (denom * ti)%p;
  }
  res = (res * degree(denom, p-2, p)) % p;
  return res;
}
}

int mul_inverse(int a, int b) {
	long long int b0 = b,
		t,
		q;
	long long int x0 = 0,
		x1 = 1;
		if (b <= 1) return 1;
		while (a > 1 && b != 0) {
			q = a / b;
			t = b;
			b = a % b;
			a = t;
			t = x0;
			x0 = x1 - q * x0;
			x1 = t;
		}
		if (x1 < 0) x1 += b0;
		return x1;
}


  // std::ifstream fin ("input03.txt");
  // std::ifstream fin ("test.in");
int main() {
  ifstream fin ("input03.txt");
  ofstream fout ("myoutput.txt");
  int kMod = 1000003;
  int T;
  fin >> T;
  //std::cin >> T;

  int n, k;
  long long a, b, c;

  long N[T], K[T];
  int result[T];

  int i;
  for(i = 0; i < T; i++) {
    fin >> N[i] >> K[i];
    //std::cin >> N[i] >> K[i];
  }

  int index = 0;
  for(i = 0; i < T; i++) {
    n = N[i];
    k = K[i];

    a = combinations(n - 3, k, kMod);
    b = combinations(n + k, n - 1, kMod);
    c = mul_inverse(n + k, kMod);

    // (1 / (n + k) * nCk(n - 3, k) * nCk(n + k, n - 1)) % 1000003
    int r = (a * b) % kMod;
        r = (r * c) % kMod;

    cout << "r: " << r << endl;
    result[index] = r;
    index++;
  }

  for(i = 0; i < T; i++) {
    std::cout << result[i] << "\n";
    fout << result[i] << endl;
  }

  return 0;
}