DISTANCECOLO - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Tester & Editorialist: iceknight1093

DIFFICULTY:

1513

PREREQUISITES:

Basic math

PROBLEM:

There are N stones and K colors. Each stone must be colored with one of the K colors.
However, any two stones with the same color should have a distance of at least K between them.

How many ways exist to color the stones?

EXPLANATION:

Let’s try to color the stones one at a time, from 1 to N.

  • Stone 1 can be colored in any of the K colors, there are no restrictions yet.
  • Stone 2 has K-1 options, since it can’t be the same color as 1.
  • Stone 3 has K-2 options, it can’t be the same color as the previous two.
    \vdots
  • Stone K-1 has 2 options.
  • Stone K has 1 option, since it can’t be any of the previous K-1 colors (which are all distinct).
  • Stone K+1 has only one option: it can’t take the color of any of stones 2, 3, \ldots, K; but it can take the color of stone 1.
  • Similarly, stone K+2 must have the same color as stone 2, and so on.

In general, if i \gt K then stone i will have exactly one option: have the same color as stone i-K.

Multiply the choices for each stone to obtain the final answer.
In particular, you might notice that:

  • If K \leq N, the answer is K! (we multiply each of 2, 3, \ldots, K exactly once; everything else is 1)
  • If K \gt N, the answer is K\times (K-1) \times \ldots \times (K-N+1) = \frac{K!}{(K-N)!}

TIME COMPLEXITY

\mathcal{O}(K) per test case.

CODE:

Editorialist's code (Python) 
mod = 10**9 + 7
for _ in range(int(input())):
    n, k = map(int, input().split())
    ans = 1
    while n > 0 and k > 0:
        ans *= k
        ans %= mod
        n -= 1
        k -= 1
    print(ans)
2

did not understand whats wrong in my code explain plsss

#include
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#include<bits/stdc++.h>
#include<math.h>
#include
#define ll 1000000007
using namespace std;
//long long GCD(long long x, long long y)
//{
// if (y == 0) return x;
// return GCD(y, x%y);
//}
//long long lcm (long long a, long long b) {
// return a / GCD(a, b) * b;
//}
long long int fact(long long int n)
{
if(n==0 || n==1)
{
return 1;
}
return n*fact(n-1);
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long t;
cin>>t;
while(t–>0)
{ long long int n,k,ans=1;
cin>>n>>k;
if(n==k)
{
cout<<fact(k)%ll<<endl;
}
else if(n>k)
{
cout<<(fact(k)%ll)<<endl;
}
else{
while(n–>0)
{
ans=ans*k;
k=k-1;
}
cout<<ans%ll<<endl;
}

}

}

5

The problem with this approach is that even after fact being a long long, it won’t be able to correctly store than 20!. Hence, at k =21, the output of fact(k) gives a negative value.

6

thank you broo for helping

7

#include <bits/stdc++.h>
using namespace std;
int nCrModp(int n, int r, int p)
{

if (r > n - r)
    r = n - r;


int C[r + 1];
memset(C, 0, sizeof(C));

C[0] = 1; 
for (int i = 1; i <= n; i++) {

    for (int j = min(i, r); j > 0; j--)

        C[j] = (C[j] + C[j - 1]) % p;
}
return C[r];

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t)
{
t–;
int N,K;
cin>>N>>K;

        vector<int>V(K);
    V[0]=1;
    for(int i=1;i<K;++i)
    {
        V[i]=((V[i-1])*(i+1))%1000000007;
    }
    
    if(N>=K)
    {
        
    cout<<V[K-1]<<endl;
    }
   
    else
    {
        long long int ans=(nCrModp(K,N,1000000007)* V[N-1])%1000000007;
        cout<<ans<<endl;
    }
    
    
    
}
// your code goes here
return 0;

}

Can some one find what’s wrong , test cases are failing for this