CHRIST01 - Editorial

PROBLEM LINKS:

Practice
Contest Link

Author and Editorialist: Parmjeet singh

DIFFICULTY:

Easy

PREREQUISITES:

Combinatorics

QUICK EXPLANATION:

We can solve this problem simply by using inclusion exclusion principle. let A_{i} be the event denoting that character from i_{th} bag should remain together. So clearly S_{n} =| A_{1} \bigcup A_{2} \bigcup A_{3} ... \bigcup A_{n} | will be the required answer.

EXPLANATION:

using inclusion exclusion principle S_{n} can be written as:

S_{n} = \displaystyle\sum_{i=1}^{n} | A_{i} | - \displaystyle\sum_{1 \leq i < j \leq n} | A_{i} \bigcap A_{j} | + \displaystyle\sum_{1 \leq i < j < k \leq n} | A_{i} \bigcap A_{j} \bigcap A_{k} | -.....+ (-1)^{n-1} | A_{1} \bigcap A_{2} .... \bigcap A_{n} |

A_{i} is event denoting character from i_{th} bag remain together, so |A_{i}| can be calculated by tieng up characters of i_{th} together and now arrange them with other (n-1)*k characters left.
so ,
| A_{i} | will be equal to \displaystyle\frac{((n-1)*k+1)!}{K!^{n-1} } 1 \leq i \leq n.

similarly,

| A_{i} \bigcap A_{j} | will be equal to \displaystyle\frac{((n-2)*k+2)!}{K!^{n-2} } 1 \leq i < j \leq n.

| A_{i} \bigcap A_{j} \bigcap A_{k} | will be equal to \displaystyle\frac{((n-3)*k+3)!}{K!^{n-3} } 1 \leq i < j <k \leq n.
.
.
.
| A_{1} \bigcap A_{2} .... \bigcap A_{n} | will be equal to \displaystyle\frac{((n-n)*k+n)!}{K!^{n-n} }.

Putting these values in the expression of S_{n} ,

S_{n} = \displaystyle\sum_{i=1}^{n} \frac{((n-1)*k+1)!}{K!^{n-1} } - \displaystyle\sum_{1 \leq i < j \leq n} \frac{((n-2)*k+2)!}{K!^{n-2} } + \displaystyle\sum_{1 \leq i < j < k \leq n} \frac{((n-3)*k+3)!}{K!^{n-3} } -.....+ (-1)^{n-1} \frac{((n-n)*k+n)!}{K!^{n-n} }

reducing further

S_{n} = \displaystyle\binom{n}{1} \frac{((n-1)*k+1)!}{K!^{n-1} } - \displaystyle\binom{n}{2} \frac{((n-2)*k+2)!}{K!^{n-2} } + \displaystyle\binom{n}{3} \frac{((n-3)*k+3)!}{K!^{n-3} } -.....+ (-1)^{n-1}\displaystyle\binom{n}{n} \frac{((n-n)*k+n)!}{K!^{n-n} }

Precompute facatorial array and then S_{n} will be calculated easily in a singel loop of N in each iteration we have to use binary exponentiation to calculate power of K! so Time complexity will be O(N*log N) for each testcase. So total time complexity will be O(T*N*logN).

Don’t forget to take modulo with 1e9+7 while computing S_{n}.

SOLUTION:

Author Solution
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define sz(x) (int)x.size()
#define mex 500005

inline ll binex(ll a,ll b)
{
 ll ans=1,temp=a%mod;
 while(b!=0){
     if(b&1) ans=(ans*temp)%mod;
     temp=(temp*temp)%mod;
     b=b>>1;
 }
 return ans;
 }

 int main()
 {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL); cout.tie(NULL);
      ll fact[mex],inv[mex];
      fact[0]=1; inv[0]=1;
      for(int i=1;i<mex;i++){
        fact[i]=(i*fact[i-1])%mod;
       inv[i]=binex(fact[i],mod-2);
    }    
     int t; cin>>t;
     assert(t>=1 && t<=100000);
    while(t--){
         int n,k; cin>>n>>k;
    assert(n>=1 && n<=26);
    assert(k>=1 && k<=10000);
    ll ans=0;
    int temp=1;
    for(int i=1;i<=n;i++){
        ll x=(((fact[n]*inv[i])%mod)*inv[n-i])%mod;
        ll y=(fact[i+k*(n-i)]*binex(inv[k],n-i))%mod;
        x=(temp*x*y)%mod; 
        x=(x+mod)%mod;
        ans=(ans+x)%mod;
        temp*=-1;
    }
    cout<<ans<<endl;
}
} 

If you have any doubts regarding the problem, feel free to ask them in the comments :slightly_smiling_face:

2 Likes

Nice explaination!
Where can I practice similar problems?
I am quite weak in combinatorics.

problem link this is another good problem on combinatorics.
if u want to practice more you can practice here practice link they have some good stuff.

1 Like

In the Question It was written
" He has N bags with him, each of them containing K identical lower case English alphabets. No two bags contain same character. "
But in constraints we have K > N . Am I missing something or there is some problem

Yes K can be greater than N what is problem in that like if N=2 and K=4 then you can assume that 1st bag has 4 a's and second 4 b's as N is less than 26 so the situation that two bags have same character never occurs.

2 Likes