Need Help in Newton School Coding August Challenge Question(contest is over)

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

@rahuldugar please help

#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 :slightly_smiling_face:

even u are free to suggest :sweat_smile: