Estoy intentando un problema en el que se nos da una cadena binaria de longitud N (<10 ^ 5), y se nos permite exactamente X (<10 ^ 5), se nos pregunta cuántas cadenas diferentes es posible. No tengo idea sobre esto, aunque pensé que podría resolverse usando dp, pero no podría venir con una recurrencia. Por favor ayuda?

Ejemplo: considere la cadena binaria de N = 3, 1 1 1 y X = 2 Las nuevas cadenas binarias que se pueden formar después de aplicar 2 volteos son 1 1 1 (volteó el primer / segundo / tercer bit dos veces) 0 0 1 (volteado primer y segundo bit) 1 0 0 (volteado segundo y tercer bit) 0 1 0 (volteado primer y tercer bit)