A brief note on de arrangements



proof from inclusion exclusion principle and other associated proofs will help to enhance the knowledge.

http://math.stackexchange.com/questions/83380/i-have-a-problem-understanding-the-proof-of-rencontres-numbers-derangements/83472#83472

 link 1

http://math.stackexchange.com/questions/507019/derangement-of-n-elements



Read this articles thouroughly

Question

Professor just has checked all the N students tests. Everything was fine but then he realised that none of the students had signed their papers, so he doesn't know which test belongs to which student.

But it's definitely not professors's job to catch every student and asked him to find his paper! So he will hand out these papers in a random way.

Now he is interested in the following question: what is the probability that X students will receive someone other's test, not their where L <= X <= R.

Input:

The first line contains 3 space-separated integers: N, L, R.

Output:

Let's suppose the answer is a fraction P / Q where P and Q are coprime. Output P * Q^-1 modulo 10⁹ + 7.

Constraints:

1 ≤ N ≤ 100
0 ≤ L ≤ R ≤ N

Notice the number of dearangements of k objects can be recursively shown as 

      D(n)= (n-1)  [  D(n-1) + D(n-2)]  using this recurrence we first build the table and then its a simple 

combinatorics question.

Solution

#include<iostream>

#include<bits/stdc++.h>

#define mod 1000000007

#define ll long long int 

ll fact[110];

ll factinv[110];

ll C[120][120];

ll dearange[110];

void ncr(int n)

{

int i,j;

for(i=0;i<=n;i++)

    {

        for(j=0;j<=i;j++)

        {

            if(i == j || j == 0)

                C[i][j] = 1;

            else

                C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;

        }

    }

}

void calcdearange(int n)

{

dearange[0] = 1;

    dearange[1] = 0;

    for(int i=2;i<=n;i++)

    {

        dearange[i] = ((i-1)*(dearange[i-1]+dearange[i-2]))%mod;

    }

}

ll bigpow(ll a,ll m)

{

 if(m==0)

 return 1;

 ll temp=bigpow(a,m/2);

 if(m&1)

 return (((temp*temp)%mod)*a)%mod;

 return (temp*temp)%mod;

}

ll invmod(ll num,ll m)

{

ll val=bigpow(num,m-2);

return val;

}

void prefact()

{

 fact[0]=1;

 for(int i=1;i<=101;i++)

 fact[i]=(i*fact[i-1])%mod;

}

using namespace std;

int main()

{

ncr(110);

calcdearange(102);

prefact();

//cout<<invmod(6,mod)<<endl;;

int n;

cin>>n;

int l,r;

cin>>l>>r;

ll ways=0;

for(int i=l;i<=r;i++)

{

ll temp=(C[n][i]*dearange[i])%mod;

ways=(ways+temp)%mod;

}

//cout<<ways<<endl;

//cout<<fact[n]<<endl;

ll den=invmod(fact[n],mod);

// cout<<den<<endl;

ll ans=(den*ways)%mod;

cout<<ans<<endl;

return 0;

}