This problem is very interesting ,I was learning bitmasking and DP things to solve it but never thought of this approach because i didn’t even know about FFT 
,But will definitly upsolve it
2 Likes
Did anyone try to solve it in another way. This is what I did:
For A and B being same sized (=1):
A XOR B = (A+B) - 2*(A AND B)
A XOR B XOR C = (A+B+C) - 2*(A AND B + B AND C + C AND B) + 4*(A AND B AND C)
Truth table:-
A B XOR Sum AND (Sum-2*(A AND B))
0 0 0 0 0 0
0 1 1 1 0 1
1 0 1 1 0 1
1 1 0 2 1 0
The above logic comes from adder circuit of Half Adder in Digital Logic - GeeksforGeeks
Being an electronics engineer, this is the first thing which came to my mind.
Sum of all possible values from 0 to m terms can be decomposed in a similar polynomial multiplication.
And that solution works just as well. Just that making permutations for AND instead of XOR was easier.
1 Like
Try reducing modular operations or write a better implementation of NTT. You can use the one I have provided in the link.
1 Like
Hi,
It tried to use combinatorial arguments only to do it, but then after a few hours of thinking, I realized the convolution might be a way to do it. Then searching from webpage to webpage, I saw that FFT can calculate these convolutions in n log(n) (for each bit). I tried to use numpy.fft, but when n becomes slightly bigger than 50, it does not work anymore. I am not sure if this has to do with precision, but then I saw NTT, and since we are working modulo a prime of the required form, then I extracted the code from Sympy for NTT and pasted it inside my code. Unfortunately, it is way too slow. I (unfortunately) code only in Python for now. Does anybody know how to use either of these (FTT or NTT) in Python fast enough to pass the time limit?
Coming back about how to solve the problem using only combinatorial arguments, I tried to root the subsets but I couldn’t do it. The only solution that got full marks for this problem in Python actually solves it very elegantly using nice combinatorial tricks. The solution from @sid05182000 can be found here:
https://www.codechef.com/viewsolution/42486582
Thanks for your help!
as far as I can understand, I guess u are taking nCr every time while counting ones but we are supposed to be taking cases only when the count of ones is odd, as only those cases where count of ones is odd would contribute to the result,
I am counting for odd count only, in line 119 I am incrementing i+=2 ,
i guess this is what u mean, Or may be i have understood it in wrong way
Can anyone who have just solved subtask 1 share their code link? Thanks in advance
First things first what is a convolution ??
And how did you reach to the conclusion that it requires convolution ?
Read the FFT/NTT link I have mentioned.
Can you share some resources to learn the underlying concepts?
In your code ,you are looping from i=1 to i<=j and calculating ncr for xCi but eventually i will exceed x for some cases in which your value should be 0 (eg:-3C5 should be 0)but your code is not doing that.
https://www.codechef.com/viewsolution/42849133
This is your code with only if(R>N) return 0; this line added in your Binomial function. Subtask 1 AC and rest tle.
1 Like
thanks , should have seen that while contest 
Convolution is basically a mathematical operation on 2 functions which leads to a resultant function. Generally, if we represent a function a set a values[array], the value of the resultant function at each index is series summation of product of elements from both input functions in a particular way as shown below. Here in the context of this problem as well, for finding the solution for a particular value of M, we see a summation series which is identical to polynomial multiplication.
Exploring polynomial multiplication, could recollect that it is a convolution as I studied it during college days. FFT/NTT used to solve convolution with same approach in different fields in nlogn time complexity.
FFT-less solution cuz im a noob: CodeChef: Practical coding for everyone
For size i, I xor’d each element to the subsequences of size i-1. This would give me subsequences of size i-2 and i, which i subtracted and divided respectively to get the actual answer for size i.
2 Likes
Hi all,
I have tried to solve the problem in python. I kept getting TLE. I have applied recommendations like optimizations by use functions, avoided nested for loops and have also used inbuilt libraries which are efficient in working
Solution link https://www.codechef.com/viewsolution/42725945
Any replies which can help me to further understand why I got TLE will certainly help a lot.
There is no doubt you will get TLE for even much smaller values of N beyond 20-25.
If you are going to enlist all subsets of a set of size N, you will get complexity 2^N.
In this problem, even N^2 struggles to pass all test cases and NlogN is required.
1 Like
yeah, Sorry , I missed that iteration was i+=2,