def _construct_vector(m, i):
    """Construct the vector for x_i of length 2^m, which has form:
    A string of 2^{m-i-1} 1s followed by 2^{m-i-1} 0s, repeated
    2^m / (2*2^{m-i-1}) = 2^{m-1}/2^{m-i-1} = 2^i times.
    NOTE: we must have 0 <= i < m."""
    return ([1] * 2 ** (m - i - 1) + [0] * 2 ** (m - i - 1)) * 2 ** i
