Saloni has two sets A and B, both of having N distinct elements. Sets A and B have exactly N - K same elements (K <= N). Therefore, exactly K elements differ in sets A and B. Now you insert both the sets into two lists C and D.
Now Saloni loves the scenario when C[i] != D[i] for any value of i from 1 to N.
You are allowed to permute both the arrays C and D. Find the number of ways in which Saloni loves the permutation of the two arrays. (The total number of ways to permute both arrays = N! * N! )
As the answer can be huge, find it modulo 109 + 7.
Input
The first line of input contains an integer Q, denoting the number of queries.
The next Q lines contain two integers N and K.
Constraints
1 <= Q <= 100000
1 <= N <= 10000
0 <= K <= N
Sample Input
3
3 0
3 1
3 3
Sample Output
12
18
36
Explanation:
Query 1: C = [a, b, c] and D = [a, b, c]. One valid combination is [b, a, c] and [a, c, b].
Query 2: C = [a, b, c] and D = [a, b, d]. One valid combinations are [a, b, c] and [b, a, d].
Query 3: C = [a, b, c] and D = [d, e, f]. All permutations of both the arrays are valid. So, 3! * 3! = 36.
if anyone can please provide a code or solution, preferably in C++ or Java
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int fact[10005],ifact[10005];
int ncr(int n, int k) {
return (((fact[n]*ifact[k])%mod)*ifact[n-k])%mod;
}
void solve() {
fact[0]=1;
fr(i,1,10000)
fact[i]=(fact[i-1]*i)%mod;
ifact[10000]=powm(fact[10000],mod-2);
for(int i=9999; i>=0; i--)
ifact[i]=(ifact[i+1]*(i+1))%mod;
int q;
cin>>q;
while(q--) {
int n,k;
cin>>n>>k;
k=n-k;
int ans=0;
fr(i,0,k) {
if(i&1)
ans=(ans-ncr(k,i)*fact[n-i])%mod;
else
ans=(ans+ncr(k,i)*fact[n-i])%mod;
}
if(ans<0)
ans+=mod;
ans=(ans*fact[n])%mod;
cout<<ans<<endl;
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
int t=1;
// cin>>t;
while(t--)
solve();
return 0;
}
1 Like
thanks a lot, really clean and understandable code 
even u are free to suggest 