Aug 2012
1 / 11
Aug 2012
Aug 2012
naman_gemini
Aug '12

Hey, I was doing a problem recently, and after quite a mathematical struggle I reached the answer of the problem to be in form of (nCr % MOD) where nCr = n! / (n-r)! and MOD is in int range

Now the thing is my n can be as big as 2*10^6. I have seen ppl do this in O(1) time by precomputing all values of n!
But how is it possible to avoid overflow, and is there a general technique to find this (apart from multiplying numbers from 1 through n, 1 through r)
Can someone elaborate please, or give some link of a nice reference.

I can provide the problem link as well, but I think that's irrelevant, I just want a general approach towards such problem. Sorry for another post, I couldn't really find something specific like this in previous posts. unamused

  • created

    Aug '12

  • last reply

    Aug '12
  • 10

    replies

  • 1.8k

    views

  • 3

    users

  • 1

    like

  • 4

    links

naman_gemini
Aug '12

I found out this way.
Basically dividing numerator and denominator by their common factor, following code gives the implementation for that:

#include<cstdio>
#define MOD 1000000009
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b)
{
    ll t;
    while(b)
    {
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}
void div_by_gcd(ll &a, ll &b)
{
    ll g=gcd(a,b);
    a/=g;
    b/=g;
}
ll C(int n,int k)
{
    ll num=1,den=1,toMul,toDiv;
    if(k>n/2) k=n-k;
    for(int i=k;i>0;i--)
    {
        toMul=n-k+i;
        toDiv=i;
        div_by_gcd(toMul,toDiv);
        div_by_gcd(num,toDiv);
        div_by_gcd(toMul,den);
        num*=toMul;
        den*=toDiv;
    }
    return num/den;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%lld\n",(n*C(2*n,n))/2);
    }
}

But I don't know how to tackle overflow with this, plus
color=#FF0000%m = (a%m)*(b%m)[/color]
Is there any formula forcolor=#0040FF%m[/color] as well?? I think (a%m)*(b^-1) would have precision issues

leppyr64
Aug '12

You are right to be worried about this portion of the calculation. It is not accurate.

There are many methods for calculating (nCr)%m. These methods are then limited by the question of whether or not m is prime.

Post a link to the problem please, someone may find it useful.

leppyr64
Aug '12

Oh this problem!

Since mod is prime, this is useful:
en.wikipedia.org/wiki/Modular_mu ... ve_inverse10

PS: you don't want to calculate nCx n times. You need to think a little harder than that.

The methods of calculating nCr is not really beneficial here. Storing n! so that you can access it in O(1) is beneficial.

mehmetinal
Aug '12

There is another problem on this subject, spoj.pl/problems/GAMECG/3.

I can calculate C(n, r) % 1300031 but I couldn't find a good way to determine if the result exceeds 1300030. Any ideas on this one?

mehmetinal
Aug '12

First I I calculate factorials modulus MOD in an array called fct. Then I use:

[bbone=text,457]
x = fct[n]*(mod_inv(fct[r]) * mod_inv(fct[n - r]));
x%=p;
[/bbone]

mod_inv is the modular inverse.

I get right answers for nCr but I have TLE, without determining if it exceeds or not.

leppyr64
Aug '12

I notice that you aren't consistent with your datatypes. This will involve a lot of typecasting.

Why are you calling mod_inv twice?

mehmetinal
Aug '12

I corrected data types and called mod_inv once only. Now I'm getting WA instead of TLE, without checking if the number exceeds 1300031. If I check it using the simple method for calculating combination (breaking it once the value is exceeded), it gives TLE again. Is there some good method to check if the result exceeds the given value?

Suggested Topics

Topic Category Replies Views Activity
Hosting a competition on SPOJ Off-topic 1 129 Apr 9

Want to read more? Browse other topics in Off-topic or view latest topics.