# CHRIST01 - Editorial

**URL:** <https://discuss.codechef.com/t/christ01-editorial/58615>\
**Category:** editorial\
**Tags:** easy, editorial, ghc32020\
**Created:** [March 26, 2020, 7:55am UTC](https://discuss.codechef.com/t/christ01-editorial/58615 "2020-03-26T07:55:01Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![eunoia\_1729](https://discuss.codechef.com/user_avatar/discuss.codechef.com/eunoia_1729/32/24644_2.png) [@eunoia\_1729](https://discuss.codechef.com/u/eunoia_1729)\
**Post date:** [March 26, 2020, 7:55am UTC](https://discuss.codechef.com/t/christ01-editorial/58615/1 "2020-03-26T07:55:01Z")

</div>

# PROBLEM LINKS:

[Practice](https://www.codechef.com/problems/CHRIST01)  
[Contest Link](https://www.codechef.com/GHC32020/problems/CHRIST01)

_ **Author and Editorialist:** _ [Parmjeet singh](https://www.codechef.com/users/parmjeet5)

# DIFFICULTY:

Easy

# PREREQUISITES:

Combinatorics

# QUICK EXPLANATION:

We can solve this problem simply by using [inclusion exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_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](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_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 🙂

---

<div class="post-metadata">

**Author:** ![pop123456](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pop123456/32/12227_2.png) [@pop123456](https://discuss.codechef.com/u/pop123456)\
**Post date:** [March 26, 2020, 10:45am UTC](https://discuss.codechef.com/t/christ01-editorial/58615/2 "2020-03-26T10:45:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![parmjeet\_singh](https://discuss.codechef.com/user_avatar/discuss.codechef.com/parmjeet_singh/32/3653_2.png) [@parmjeet\_singh](https://discuss.codechef.com/u/parmjeet_singh)\
**Post date:** [March 26, 2020, 2:23pm UTC](https://discuss.codechef.com/t/christ01-editorial/58615/3 "2020-03-26T14:23:17Z")

</div>

[problem link](https://www.codechef.com/problems/PRTTME) this is another good problem on combinatorics.  
if u want to practice more you can practice here [practice link](https://www.hackerearth.com/practice/math/combinatorics/basics-of-combinatorics/practice-problems/) they have some good stuff.

---

<div class="post-metadata">

**Author:** ![stunn\_areeb09](https://discuss.codechef.com/user_avatar/discuss.codechef.com/stunn_areeb09/32/32509_2.png) [@stunn\_areeb09](https://discuss.codechef.com/u/stunn_areeb09)\
**Post date:** [March 26, 2020, 2:32pm UTC](https://discuss.codechef.com/t/christ01-editorial/58615/4 "2020-03-26T14:32:11Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![parmjeet\_singh](https://discuss.codechef.com/user_avatar/discuss.codechef.com/parmjeet_singh/32/3653_2.png) [@parmjeet\_singh](https://discuss.codechef.com/u/parmjeet_singh)\
**Post date:** [March 27, 2020, 7:41am UTC](https://discuss.codechef.com/t/christ01-editorial/58615/5 "2020-03-27T07:41:05Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![cubefreak777](https://discuss.codechef.com/user_avatar/discuss.codechef.com/cubefreak777/32/215911_2.png) [@cubefreak777](https://discuss.codechef.com/u/cubefreak777)\
**Post date:** [April 9, 2020, 1:01pm UTC](https://discuss.codechef.com/t/christ01-editorial/58615/6 "2020-04-09T13:01:13Z")

</div>

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