What is INVFACT?

general
1

Going through some of the codes for certain problems I have noticed something like invfact. I don’t know what it means but it is used in cases where we need to calculate nPr or nCr, that too real quick. Can somebody please explain me what is the use of invfact?

Here is a piece of code for example:

void init(){
    For(i,MaxN-1){
        For(j,MaxN-1){
            gcd[i+1][j+1]=__gcd(i+1,j+1);
            ncr[i][j]=0;
        }
    }
    For(i,MaxN-1) {ncr[i+1][0]=1; ncr[i+1][i+1]=1;}
    fact[0]=1;
    fact[1]=1;
    
    for (int i=2;i<MaxN;i++){
        fact[i]=(fact[i-1]*i)%mod;
    }
    invfact[MaxN-1]=fastexpo(fact[MaxN-1],mod-2);
    invfact[0]=1;
    for (int i=MaxN-2;i>0;i--){
        invfact[i]=(invfact[i+1]*(i+1))%mod;
    }
    
}

Credits:CodeChef: Practical coding for everyone

Another thing, in general how can we or what is the best way to precompute values of nPr and nCr?

2

invfact is simply a precomputed array of modular multiplicative inverses for each value of i!. See here if you don’t know what that is (shameless self-promotion). Because \dbinom{n}{k} = \dfrac{n!}{(n - k)! \cdot k!}, we need to quickly “divide” by (n - k)! and k!, these precomputed inverses let us do that.

In brief, this comment shows how I would write nCk. nPk can be calculated by removing ifact[k] from the function. All of this preprocessing can be done in O(n).

3 Likes
3

Thanks a lot @galencolin. :smile: