Actually for this problem, it is not difficult to prove that the brute force solution is sub - cuberoot(X), because Y starts increasing faster than that pretty quickly, and increases even further (this is sort of a hand-waving argument, a formal proof can be constructed from this). It is in fact exponential (someone also mentioned a bound of 100). But I didn’t see this relation with fibonacci.
Thank you so much, got AC!
I actually worked for linear case:
lets say you have freq array for n=4 : [{0,1},{1,3},{2,0},{3,0}] remainder and its freq so for k=2 we do is multiplying value to all previous considered value modulo n.it will give new freq array. for k=4,so what i am doing is replacing (((x1 % n * x2 ) %n * x3 )%n x4 )%n with (x1x2)%n * (x3*x4)%n which is binary exponentiation.
1 Like
If you have understood the answer, can you explain it ?
thank you for your reply it’s clear now
I think it’s better to read editorials first instead of asking loopfree 
Though it’s your wish. Idm.