I’m adding this to my to-do list. I’ll definitely solve it after learning FFT. Very cool problem!
3 Likes
wow! now I understand the importance of knowing the algo rather than just using it as a black box. tried the same thing as @takh8
2 Likes
This problem is the most interesting problem, and for 10 points this problem was a very confidence booster for me, a new concept FFT/NTT also came to know, I will definitely upsolve it
This was one of the problems I spent most time on… Finally could solve it… I came up with the strategy of series sum of binomials for each bit soon and got the first set correct, but getting TLE for 5 cases. Explored a bit and understood that it is a convolution, explored different ways of solving. Worked with FFT first, then struggled with modulo, broken down the polynomials, then again TLE 
. Stumbled up on NTT more suitable with modulo. Spent some time on understanding the concept. Implemented NTT though I used some existing code of NTT. Again TLE. Tweaked the series to compute convolution and then prefix sums. Earlier I was directly calculating the answer for M which lead to more padding of zeroes to the series (as NTT/FFT gives circular convolution). Again TLE. Then I realised the I/O is slow and then used Fast IO which gave some room and also tweaked the NTT code to remove some modulo operations… Finally got AC(100) just below the time limit. Finally it was quite satisfactory and I learnt something new as well, though it cost me a lot of time… 
4 Likes
Exactly same for me
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