PROBLEM LINKS:
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 