# CHRIST01 - Editorial

Author and Editorialist: Parmjeet singh

Easy

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

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

Can somebody tell that what is the strongest hint in this problem that suggests that its an inclusion exclusion problem ?