Have you tried to replace your multiply_hack with the multiple function mentioned in the editorial?
1 Like
It looks like “void add(int s)” has a bug. You should have one more mod after the +. Try to find such tiny bugs around, and thus your debug skills will be improved fast.
The multiplication operator in your code, although mod c, may exceed unsigned long long. Please read the editorial to find the tricky way to get the product withou any exceeding. Thanks.
1 Like
In this java code, i tried so many test cases, even with 10^18 but it gives Wa… please tell where m getting wrong.
oh, you need to mod all L[i] by c. Try System.out.print((list[i] % c)+ " ");.
the mod c should be applied even if the all operations are “reverse”
dFm38p - Online IDE & Debugging Tool - Ideone.com This code gives WA (if i use xor for reversing), and TLE if i do it using loop(done in comments).
However, i saw various solutions in which xor was used, but then they are not taking mod after reversing, is it such??
@aq1_ If you’ll see addmod function, you have done x-m+y, but if even this “x-m+y” is greater than c, we again need to take the mod. You function should have the recursive call which returns(x+y+m) when x+y-m<0.
oh, in your reverse, “int to=num” should be “int to=num - 1” I think. You can mod them before output.
“multiplicativeConstant = (multiplicativeConstant * bModC) % C;” may exceed the unsigned long long when multiplication, please look into the editorial to find the solution to avoid exceeding.
Thanks, although got the TLE. I have to use the continuous multiplication like mentioned in editorial.
i was wondering why O(n^2) was giving TLE because N<=1000 and time limit was 2sec. Wasn’t it enough ??
thanks for pointing out the problem in my code.
Yes, from the theoretical complexity, it should work. But, you should also consider the implementations. If your implementation uses the mod operations too many times, or some other reasons lead to a big constant in time complexity, it may get TLE.
Please calm down and look your codes line by line, sentence by sentence carefully. I think you can figure out the bugs. 
And I have tested your code locally. It even failed by the sample cases! After I fixed the problem, I found your code TLE. There are too many unnecessary mod operations. And also, you can read the editorial to find a faster solution. Only O(N log C) for each case.
in the first approach what are the initial values of K[0] and D[0] ?