Binomial coefficients modulo square of a prime

166 Views Asked by At

Calculate the binomial coefficient: \binom{852 467 439}{426} (nCk) modulo 289

I has used this document: https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf

int VpnCk(int n, int k, int p){
    int res = 0, t = p;
    while (n > t){
        res += (n/t - k/t - (n-k)/t);
        t *= p;
        if (res == 2) break;
    }
    return res;
}

So nCk is divided by 17, but 289
Use vector to get Representation of N, K, N-K in base 17.

vector<unsigned long long> getRepresentation(unsigned long long N, int mod) {
    vector<unsigned long long> res;
    while (N > 0) {
        res.push_back(N % mod);
        N /= mod;
    }
    return res;
}
...
int main(){
    ...
    n17.resize(n17.size()+1);
    k17.resize(n17.size()); r17.resize(n17.size());
}

N: 8 5 10 10 6 5 1 2 0
K: 1 8 1 0 0 0 0 0 0
N-K: 7 14 8 10 6 5 1 2 0

Define:
N = n_0 + 17 * n_1 + ... + 17^d * n_d (the value of n_i has listed)
N_i = n_i + 17 * n_{i+1} (i=0,d)

So, (N_i)!/(K_i)!(R_i)! modulo 289 are: 1 42 141 1 1 1 1 1 And

unsigned long long C289(unsigned long long N, unsigned long long K, unsigned long long R){
    if (K > N) {
        return 1;
    }
    return (((fact17[N] * binpow(fact17[R], 271, 289)) % 289) * binpow(fact17[K], 271, 289)) % 289;
}
int v17 = VpnCk(N, K, 17);
if (VpnCk(N, K, 17) == 2) res3 = 0;
else {
    for (unsigned long long i = 0; i <= k17.size()-2; ++i){
        res3 = (res3 * C289(n17[i+1]*17 + n17[i], k17[i+1]*17 + k17[i], r17[i+1]*17 + r17[i])) % 289;
    }
    if (v17 == 1) res3 = (res3*17) % 289;
}
cout << res3;

My answer is 102, but the correct answer is 238. What's wrong in my code

P/s: can I use Latex on stackoverflow?

0

There are 0 best solutions below