I think I have some of the logic behind this question but I'm not sure how to apply it?
A k-inversion in a bitstring b occurs when 1 appears k indexes before some 0. We're to come up with a way to count all the k-inversion for each k from 1 to n-1, given a bitstring b of length n. The algorithm should take less than O(n^2) time assuming arithmetic can be done in constant time.
I think this should be using cross correlation as a black box -- on n bits at a time. I'm thinking I can return a list of tuples or mappings between each bit-substring and the number of k conversions. Basically what I'm thinking so far:
- We have a bitstring b. We make a copy b', and invert b'
- For each k we perform a cross correlation with an offset of k, going up from bit 1 to k-1
- Each cross correlation takes $O(n log n)$ time.
- With this algorithm you would need to do k cross correlations, making $O(kn log n)$ time, but k is technically a measure of n, so this is not faster than $O(n^2)$ time
So basically...
I get how to do this naively. but how are you supposed to get the two vectors to be different lengths if you can just invert one? I'm also stuck on generalizing this as polynomial multiplication. The way that makes sense to me is to have k different cross-correlations but I saw earlier on this thread we should only need 1.