More polygons

polygons2

#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;
}

long long combinations(int n, int k, long long p, int &t) {
  if (n < k) return 0;
  if (n == 0 && k == 0) return 1;

  int num_degree = get_degree(n,p) - get_degree(n- k,p);
  int den_degree = get_degree(k,p);
  t = num_degree - den_degree;
  if (t > 0) return 1;
  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;
  if (res == 0) return 1;
  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) {
			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;
}

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 < 4; i++) {
    n = N[i];
    k = K[i];
    
    int r, t;
    long long res = 1;
    int cnt = 0;
    a = combinations(n-3, k, kMod, t);
    res = (res*a) % kMod; cnt+=t;
    b = combinations(n + k, n - 1, kMod, t);
    res = (res*b) % kMod; cnt+=t;
    r = n+k;
    while (r % kMod == 0) {
        r /= kMod;
        cnt--;
    }
    c = mul_inverse(r, kMod);
    res = (res * c) %kMod;
    
    if (cnt > 0) res = 0;

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

  return 0;
}