Define two length n sequences : a_i is 1 if there is initially a robot at the position i, and 0 otherwise. b_i is 1 if the position i is special, 0 otherwise.

You then want to know for all k ≤ n if , where m is the number of robots. You can compute all these sums fast enough using FFT.

See this link : http://www.geeksforgeeks.org/wildcard-character-matching/ Consider the ordering of all robots as 1's with the spaces in between denoted with the wildcard '?' and consider the arrangement of batons as 1's and 0's. Then it is easy.

Can this problem be solved like this ?? What i did was that i made a polynomial A which whose x^(n-i-1) coefficient is 1 if ith baton is special baton other wise zero .my polynomial A is of degree 2*n-1 and i made another polynomial b with x^i and x^(n+i) is 1 if at ith position the robot is present and then i simply multiplied both the polynomials using FFT and checked the coefficients of {x^n ... x^(2*n -1)} for the answer if they are equal to m i.e number of robots.the count of such coefficients is the answer.

Problem essentially reduces to finding the inner product of two vectors for every rotation of one of the vectors.

Refer to: All kinds of Scalar Products