# TRAXORB - Editorial (Kodeathon 15.2)

Practice

Contest

Author: Satyam Gupta

Tester: Pulkit Sharma

Editorialists: Satyam Gupta,Pulkit Sharma

MEDIUM

### PREREQUISITES:

Maths, Combinatorics, Inclusion-Exclusion Principle

### PROBLEM:

There are R types of orbs. There are equal number of orbs of all types.
Each orb is unique in itself. Count the no. of ways to choose k orbs that includes at least one orb from all R types.

### EXPLANATION:

Count the no. of ways of choosing k orbs, such that there exists at least one type for which no orb is selected and subtract from the total no. of ways of choosing k orbs. To calculate this, use Inclusion-Exclusion Principle.

i) Add no. of ways to select k orbs.

ii) Subtract no. of ways of selecting k orbs, where exactly one type exists for which no orb is selected.

iii) Add no. of ways of selecting k orbs, where exactly two types exist for which no orb is selected.

iv) Subtract no. of ways of selecting k orbs, where exactly three types exist for which no orb is selected.
… and so on.

So,

ans = \sum_{i=0}^{R} (-1)^i *\dbinom{R}{i} * \dbinom{n-(i*n/r)}{k}

Here is the pseudocode implementing the above said procedure

	y=n/r
ans = 0

for i=0 to r:

if(i%2=1)
ans = ans - ncr(r,i)*ncr(n-i*y,k)
else
ans = ans + ncr(r,i)*ncr(n-i*y,k)

//ncr(a,b) calculates a choose b (Binomial Coefficient)

return ans


Complexity of this solution:

Preprocessing for calculating factorials and modular inverse of factorials (used for computing ^nC_r ): O(100000)

Final complexity = O(R + 100000)

### AUTHOR’S AND TESTER’S SOLUTIONS:

#include<iostream>
#include<cstdio>

using namespace std;

#define MOD 1000000007
#define ll long long int

ll fact,ifact;

ll modpow(ll base, ll exponent, int modulus=MOD)
{
ll result = 1;
while (exponent > 0)
{
if (exponent % 2 == 1)
result = (result * base) % modulus;
exponent = exponent >> 1;
base = (base * base) % modulus;
}
return result;
}

ll modinv(ll x)
{
return modpow(x,MOD-2);
}

void calc()
{
fact=fact=ifact=ifact=1;

for(int i=2;i<=1000;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
ifact[i]=(ifact[i-1]*modinv(i))%MOD;
}
}

ll ncr(ll n,ll r)
{
if(n<r) return 1;

return (((fact[n]*ifact[n-r])%MOD)*ifact[r])%MOD;
}

int main()
{
ll t,n,r,k,i,y,ans;

calc();

cin>>t;

while(t--)
{
cin>>n>>r>>k;

y=n/r;

ans = 0;

for(i=0;i<r;i++)
{
if(i&1)
ans = ((ans - (ncr(r,i)*ncr(n - i*y,k))%MOD)+MOD)%MOD;
else
ans = (ans + (ncr(r,i)*ncr(n - i*y,k))%MOD)%MOD;

printf("(%ld,%ld)\n",ncr(r,i),ncr(n - i*y,k));
}
cout<<ans<<endl;
}

return 0;
}

1 Like