Estou tentando um problema em que recebemos uma string binária de comprimento N (<10 ^ 5), e nos é permitido exatamente X (<10 ^ 5) inverter, perguntam-nos quantas cordas diferentes são possíveis? Eu não estou tendo uma idéia sobre isso, acho que ele pode ser resolvido usando dp, mas não é capaz de vir com uma recursão. Plz Help?

Exemplo: considere a sequência binária de N = 3, 1 1 1 e X = 2 As novas seqüências binárias que podem ser formadas após a aplicação de 2 inverter são 1 1 1 (inverte o primeiro / segundo / terceiro bit duas vezes) 0 0 1 (inverter primeiro e segundo bits) 1 0 0 (segundo e terceiro bits invertidos) 0 1 0 (primeiro e terceiro bits invertidos)