Why does this submission fail and this one doesn’t? Both differ only in the choice of modulo but that shouldn’t ideally affect the output in this question.
How to construct such cases? Any possible motivation?
We can’t obviously use random modulos and number of modulos are only few which are suitable for NTT and are less than 10^18. So does that mean this question can’t be solved by NTT if the testcases are built thoughtfully?
I don’t understand what you’re pointing out in the code.
How can the mod be arbitrary, it should have a primitive root, let alone a kth root of unity…
Also I saw another submission which doesn’t use only the transform (unlike mine), but it uses binary exponentiation of the polynomial with convolution using the same ‘well-known’ mod, and that submission passes. Do you mean something like this?
The coeffs of the final polynomial are number of ways, right?
So either way (transform or binary exp) we’ll get the same final polynomial. And the initial submission failed because the no. of ways for a particular term summed up to a multiple of the modulo, thereby making the coeff zero.
Link
This is my last question. What am I missing here?
Got it, thanks a lot …