PROBLEM LINK:
Author: Pranjul Pal
Tester: Navin Chandra
Editorialist: Pranjul Pal
DIFFICULTY:
Easy
PREREQUISITES:
Math
PROBLEM:
Out of total N rooms in a row, you have to calculate no. of ways of selecting k rooms such that no two adjacent rooms have been selected.
QUICK EXPLANATION:
Total number of ways can be calculated using the formula \binom{N-k+1}{k} \bmod 1000000007.
EXPLANATION:
We can solve the problem using Stars and Bars Concept.
There are N rooms in a row and we have to select k rooms such that between any two rooms there is atleast one room.
This can be taken as putting k bars in N stars such that the distance between any two bars is alteast 1.
Let’s denote distance between bars by {x_i}.
x_1 = distance from 1^{st} bar to the left end.
x_{k+1} = distance from k^{th} bar to the right end.
x_2, x_3, \dots, x_k = distance between the bars
So we can say that:
x_1+ x_2+ \dots+ x_{k+1}=N-k
where, x_1>=0 and x_{k+1}>=0, and x_2, x_3, \dots, x_k>=1
->x_1+ x_2+ \dots+ x_{k+1}=N-2*k+1
where x_1, x_2, \dots, x_{k+1}>=0
Hence, the answer would be \binom{N-k+1}{k} \bmod 1000000007.
Since, N,k are large, we can use Fermat’s little theorem to compute the answer.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ln "\n"
#define pb push_back
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define vll vector<ll>
#define vpll vector<pll>
#define vvll vector<vector<ll>>
#define sll stack<ll>
#define qll queue<ll>
#define mp make_pair
#define f first
#define s second
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define Test ll t;cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define init(x,n,v) for(ll i=0;i<=n;i++) x[i]=v;
#define all(x) x.begin(),x.end()
#define pi 3.14159265358979323846
ll MOD = 1e9+7 , MAX = 1e18;
ll power(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans = (ans * a)%MOD;
b/=2;
a = (a * a)%MOD;
}
return ans;
}
ll nck(ll n,ll r)
{
ll ans=1;
if(n-r<r) r=n-r;
for(ll i=0;i<r;i++)
{
ans = (ans*(n-i))%MOD;
ans = (ans*power(i+1,MOD-2))%MOD;
}
return ans;
}
int main()
{
fast_io;
Test
{
ll n,k,ans=0;
cin>>n>>k;
n=n-2*k+1;
k++;
if(n>=0) ans=nck(n+k-1,k-1);
cout<<ans<<ln;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 100000000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
void mahakal(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif
}
ll power(ll x , ll y){
if(y==0)return 1 ;
ll ps = power(x , y/2)%mod;
ll ss= (ps*ps)%mod;
if(y&1)ss=(ss*x)%mod;
return ss ;
}
ll modInverse(ll x){
return power(x,mod-2);
}
ll nck(ll n, ll k)
{
if(k==0)return 1 ;
ll fac[n+1];
fac[0] = 1;
for (ll i=1 ; i<=n; i++)
fac[i] = fac[i-1]*i%mod;
return (fac[n]* modInverse(fac[k]) % mod *
modInverse(fac[n-k]) % mod) % mod;
}
void solve(){
ll n , k ;
cin>> n >> k ;
ll N=n-2*k+1;
ll K=k+1;
if(N<0)cout<<0<<endl;
else{
ll ans = nck(N+K-1,K-1);
cout<<ans<<endl;
}
}
int main(){
mahakal(),fast;
ll t ;
cin>> t ;
while(t--)solve();
return 0;
}