After looking at your solution, I’m surprised that it didn’t TLE. I think the problem might be in your logic, most probably. A duplicate need not be the sum of the sequence.
The sum of the sequence will be fixed as “The sum of Prefixes and Suffixes, divided by n+1”. This is because for every Prefix Sum up to some index, there is a Suffix Sum for the index after that, their sum together gives the sum of the original sequence.
Second of all, there are probably a lot of things that you can learn here.
You can use
sort(a,a+n); to sort the array in C. You don’t need to write the merge sort for it every time.
There is a built in function for calculating GCD.
ll gcd = __gcd(x,y);
You’ll need to write your own power function based of fast exponents O(logEXP) as the values might overflow and calculating by repeated multiplication might give TLE.
ll yourPowerFunction(ll base,ll exp)
if(exp==0) return 1;
To take the modulo inverse, you can just raise that number to the power MOD-2;
ll InvMod = yourPowerFunction(number,MOD-2);
It is recommended to create the array of Factorials and Inverse Factorials beforehand.
Use good variable names instead of a,b,c,d,e, etc. It makes the code easy to understand.