sum=10
Remove 2 10s
New sequence is
2 2 4 4 6 6 8 8
Pairs are
(2,8)
(2,8)
(4,6)
(4,6)
Or
(2,8)*2
(4,6)*2
Ans=(4!/2!*2!) (No. Of ways to arrange the pairs) * 2^4(no. of orientations). I’m not sure how you got your formula. There is no addition involved.
1 Like
thanks a lot for that , this is what I was trying to figure out… but I was trying to add each combination like , (2,4,6,8)+ (2,2,6,6) + (2,8,6,6) etc … i.e no of ways to arrange each of these combinations . need to improve on counting principle 
thanks again …
thanks man!!
1 Like
i have done the same thing as given in editorial but still i am not able to figure out the problem in my code. please help me
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll fact[100001];
ll mod=1000000007;
int main()
{
fact[0]=1;
fact[1]=1;
for(int i=2;i<100001;i++)
fact[i]=(ifact[i-1])%mod;
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int arr[2n+2];
ll sum=0;
map<int,int>m;
for(int i=0;i<2n;i++)
{
cin>>arr[i];
sum+=arr[i];
m[arr[i]]++;
}
if(sum%(n+1)!=0)
{
cout<<“0\n”;
continue;
}
sum=sum/(n+1);
if(m[sum]<2)
{
cout<<“0\n”;
continue;
}
arr[2n]=0;
arr[2n+1]=0;
m[0]=2;
sort(arr,arr+2(n+1));
map<int,int>:: iterator it;
bool flag=false;
int j=2*n+1;
for(int i=0;i<j;i++)
{
if(arr[i]+arr[j]!=sum)
{
flag=true;
break;
}
j–;
}
if(flag)
{
cout<<“0\n”;
continue;
}
for(it=m.begin();it!=m.end();it++)
{
if(it->second!=m[sum-(it->first)])
{
flag=true;
break;
}
if(it->first==sum/2 && (it->second)%2!=0)
flag=true;
}
if(flag)
{
cout<<"0\n";
continue;
}
map<pair<int,int>,int>mp;
j=2*n-1;
for(int i=2;i<j;i++)
{
mp[make_pair(arr[i],arr[j])]++;
j--;
}
ll res=1;
res=fact[n-1];
res=(res*(ll)pow(2,n-1-mp[{sum/2,sum/2}]))%mod;
map<pair<int,int>,int> :: iterator ite;
for(ite=mp.begin();ite!=mp.end();ite++)
{
res=(res/(fact[ite->second])%mod)%mod;
}
cout<<res<<endl;
}
}
The division is wrong in the last line.
Res may not divide the factorial because it is mod p.
To overcome that, instead multiply by (fact)^(p-2).
Since fact^(p-1)=1 mod p, res/fact mod p = res *fact^(p-2) mod p
it is still giving the same test case cleared!!!
While multiplying 2^n you need to use power, not pow as it will overflow. Also im not sure how maps work, but the maps are being incremented but i dont see them being initialized, are they initially zero?
yes they are initially zero, i have used power this is the corrected code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll fact[100001];
ll mod=1000000007;
ll power(ll x , ll p)
{
ll res = 1;
while§
{
if(p & 1) res = (res * x)%mod;
p /= 2;
x = (x * x)%mod;
}
return res;
}
int main()
{
fact[0]=1;
fact[1]=1;
for(int i=2;i<100001;i++)
fact[i]=(ifact[i-1])%mod;
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int arr[2n+2];
ll sum=0;
map<int,int>m;
for(int i=0;i<2n;i++)
{
cin>>arr[i];
sum+=arr[i];
m[arr[i]]++;
}
if(sum%(n+1)!=0)
{
cout<<“0\n”;
continue;
}
sum=sum/(n+1);
if(m[sum]<2)
{
cout<<“0\n”;
continue;
}
arr[2n]=0;
arr[2n+1]=0;
m[0]=2;
sort(arr,arr+2(n+1));
map<int,int>:: iterator it;
bool flag=false;
int j=2*n+1;
for(int i=0;i<j;i++)
{
if(arr[i]+arr[j]!=sum)
{
flag=true;
break;
}
j–;
}
if(flag)
{
cout<<“0\n”;
continue;
}
for(it=m.begin();it!=m.end();it++)
{
if(it->second!=m[sum-(it->first)])
{
flag=true;
break;
}
if(it->first==sum/2 && (it->second)%2!=0)
flag=true;
}
if(flag)
{
cout<<"0\n";
continue;
}
map<pair<int,int>,int>mp;
j=2*n-1;
for(int i=2;i<j;i++)
{
mp[make_pair(arr[i],arr[j])]++;
j--;
}
ll res=1;
res=fact[n-1];
res=(res*(ll)pow(2,n-1-mp[{sum/2,sum/2}]))%mod;
map<pair<int,int>,int> :: iterator ite;
for(ite=mp.begin();ite!=mp.end();ite++)
{
res=(res*power(fact[ite->second],mod-2))%mod;
}
cout<<res<<endl;
}
}
One more problem, did you check whether sum divides 2?
When we will get the setters solution… Tbh the tester solution doesn’t look user friendly anyway
Really what a beautiful Editorial! Thank u:grinning: 
1 Like
How did the tester calculated inverse factorial? I am unable to undertand that…pls elaborate that part only else soln is fine.
Hi,
The fact that the Prefix[i]+Suffix[n-1-i]=S relation holds it quite obvious (at least to me). But would it be possible to explain in a bit more detail why after the sorting of X the following relation X_i + X_{2n-i} = S still holds? I mean, this means that all the prefixes will be to the left of the sorted array and all the suffixes will be to the right of the sorted array. What’s more, their order will be such that the i-th element of the sorted array (a prefix sum) will match the (2n-i)-th element of the sorted array (a suffix sum). Is that really so easy to see and prove? Normally, I’d expect that after sorting we are going to have a bigger mess than before sorting (prefix sums and suffix sums would take arbiraty positions in the sorted array).
Best wishes
tadek
if p is any prime number and a is an integer not divisible by p,
a ^ {-1} \equiv a ^ {p - 2} \mod(p)
In this case, MOD = 1000000007 is the prime number.
In the tester’s solution,
Inv(llong x) : @line 26,
x^{-1} \mod(MOD)
is being calculated via the call to the function FastPow
return FastPow(x, MOD-2);
Considering that you understood how the factorials are being calculated @line 46, the inverse factorials are being calculated @line 47 by assigning invFacts[i] with the value of fact[i] ^{-1} which is returned by Inv with parameter fact[i].
Hope it is clear to you now. 
Thanks man I got it now!
1 Like
Hi, can someone explain how after adding 2 zeros and sorting the X holds the condition Xi+X2n-i = S with an example. Thanks in advance 
i get why we are dividing with yi but the fact that we are multiplying with 2n-1-ym means we are considering different configurations of a particular pair.
like take the example 3 3 3 3 10 7 7 7 7 10
so it can be written as (3/7) (3/7) (3/7) (3/7) and 10,10 is anyways fixed.
i cant understand the fact why we are dividing everything with yi
cause for the configuration 3 3 3 7 10 we should divide with 3!
for 3 3 7 7 10 we should divide with 2!2!
can someone please explain this .
Let’s sort the array X and only consider the first half, i.e. the first n elements, viz X1, X2, …, Xn. Some of the Xi will be Prefix and some of it will be Suffix, we don’t and can’t know which one is which but what we do know for sure that X1 <= X2 <= …<= Xn and this because we just sorted the array. Let’s for simplicity denote every Xi in [X1, Xn] by Li(the left part of the array). Now we will start generating the second part of the array, i.e. Xn+1, Xn+2, …, X2n. Let’s for simplicity, call each Xi in [Xn+1 X2n] by Ri(the right part of the array). So, for each Li we will generate it’s corresponding Ri. We will use the rule Prefix (i) + Suffix(n-i) = Sum of Array = S. Hence Li + Ri = S or Ri = S - Li.
Now, If we can prove that after generating the Right part, i.e. R1…Rn the array is completely sorted then we can prove that on sorting X the condition stated in editorial i.e. Xi and X2n-i forms a pair is satisfied. This is because we just generated the second half of the array - R, using the same condition.
Now, all we have to prove is that Ln <= R1 <= R2 <= R2 <= … <= Rn. If we can prove this than we are done.
Since Ri = S - Li, so greater the Li smaller the Ri and vice versa. So, more we move to the right of L, the element will be more to the left of R. Hence the condition that R is sorted is satisfied. This also makes the entire X sorted as L is already sorted.
1 Like
It is later proved later that there is only one way of pairing every element in array such that sum of each pair is same.
1 Like
I used same approach to solve the problem using maps,but i don’t know where it is going wrong.can you please help me.