Количество различных двоичных строк с k сальто

Я пытаюсь решить проблему, когда нам задают двоичную строку длиной N (<10 ^ 5), и нам разрешено ровно X (<10 ^ 5) переворачивать ее, нас спрашивают, сколько разных строк возможно? Я не понимаю об этом, хотя я думаю, что это может быть решено с помощью dp, но не в состоянии прийти с рекурсией. Плз помогите?

Пример: рассмотрим двоичную строку с N = 3, 1 1 1 и X = 2. Новые двоичные строки, которые могут быть сформированы после применения двух переворотов, равны 1 1 1 (дважды перевернули первый / второй / третий бит) 0 0 1 (перевернуто первый и второй бит) 1 0 0 (перевернутый 2-й и 3-й бит) 0 1 0 (перевернутый 1-й и 3-й бит)

 Srivatsa Sinha10 июн. 2016 г., 20:09
Конечно !! .. Я добавил пример
 Srivatsa Sinha07 июн. 2016 г., 16:44
да одним щелчком, персонаж изменится с 0 на 1 или наоборот
 eol07 июн. 2016 г., 16:01
X переворачивает, вы имеете в виду, что вы можете перевернуть каждый символ строки?

Ответы на вопрос(1)

Нахождение перевернутых строк

Рассмотрим, например, случай, когда N = 10, X = 4 и исходная строка:

initial: 0011010111  

тогда это будет пример перевернутой строки:

flipped: 0000111111  

потому что 4 бита разные. Если вы XOR две строки, вы получите:

initial: 0011010111  
flipped: 0000111111  
XOR-ed:  0011101000  

где 4 заданных бита (единицы) в строке XOR-ed указывают местоположение 4 битов, которые были перевернуты.

Теперь подумайте об этом задом наперед. Если у вас есть исходная строка и строка с 4 установленными битами, то вы можете сгенерировать X-отраженную строку, выполнив XOR-код их:

initial: 0011010111  
4 bits : 0011101000  
XOR-ed:  0000111111  

Таким образом, если вы генерируете каждую двоичную строку длины N с установленными битами X, а вы XOR с помощью исходной строки, вы получаете все строки, перевернутые X.

initial     4 bits      XOR-ed  
0011010111  0000001111  0011011000
            0000010111  0011000000
            0000100111  0011110000
            ...
            1110010000  1101000111
            1110100000  1101110111
            1111000000  1100010111

Генерация всех строк длиной N с битами, установленными в X, может быть выполнена, например, сВзломать Госпера, В приведенном ниже примере кода я использую функцию обратного лексикографического порядка, которую я изначально написал дляэтот ответ.

Дважды листать

Если биты могут быть перевернуты дважды, возможно, что строка с перевернутым X не имеет битов X, отличных от исходной строки, но только X-2, потому что один бит перевернут, а затем перевернут в исходное состояние. Или X-4, если бит был перевернут 4 раза, или два разных бита были перевернуты дважды. Фактически, число различных битов может быть X, X-2, X-4, X-6 ... вплоть до 1 или 0 (в зависимости от того, является ли X нечетным или четным).

Таким образом, чтобы сгенерировать все строки с перевёрнутым X, вы генерируете все строки с перевернутыми битами X, затем все строки с перевернутыми битами X-2, затем X-4, X-6 ... до 1 или 0.

Если X> N

Если X больше, чем N, то, очевидно, некоторые биты будут переворачиваться более одного раза. Метод их генерации тот же: вы начинаете с X, отсчитываете до X-2, X-4, X-6 ... но генерируете только строки для значений ≤ N. Таким образом, практически вы начинаете с N или N- 1, в зависимости от того, является ли XN четным или нечетным.

Общее количество строк

Количество строк N-длины с перевернутыми битами X равно числу строк N-длины с битами, заданными X, что являетсяБиномиальный коэффициент N choose X, Конечно, вы должны принять во внимание строки с перевернутыми битами X-2, X-4, X-6 ... так что в итоге получается:

(N выбрать X) + (N выбрать X-2) + (N выбрать X-4) + (N выбрать X-6) + ... + (N выбрать (1 или 0))

В случае, когда X больше, чем N, вы начинаете сN choose N или жеN choose N-1в зависимости от того, является ли X-N четным или нечетным.

Для вашего примера с N = 3 и X = 2 общее число:

(3 choose 2) + (3 choose 0) = 3 + 1 = 4  

Для приведенного выше примера с N = 10 и X = 4 общее число равно:

(10 choose 4) + (10 choose 2) + (10 choose 0) = 210 + 45 + 1 = 256  

Для примера в другом ответе с N = 6 и X = 4 правильное число:

(6 choose 4) + (6 choose 2) + (6 choose 0) = 15 + 15 + 1 = 31  

Пример кода

Этот фрагмент кода JavaScript генерирует последовательности двоичных строк в обратном лексикографическом порядке (так что установленные биты перемещаются слева направо), а затем распечатывает результирующие перевернутые строки и общее количество для примеров, описанных выше:

function flipBits(init, x) {
    var n = init.length, bits = [], count = 0;
    if (x > n) x = n - (x - n) % 2;   // reduce x if it is greater than n
    for (; x >= 0; x -= 2) {          // x, x-2, x-4, ... down to 1 or 0
        for (var i = 0; i < n; i++) bits[i] = i < x ? 1 : 0;    // x ones, then zeros
        do {++count;
            var flip = XOR(init, bits);
            document.write(init + " &oplus; " + bits + " &rarr; " + flip + "<br>");
        } while (revLexi(bits));
    }
    return count;
    function XOR(a, b) {              // XOR's two binary arrays (because JavaScript)
        var c = [];
        for (var i = 0; i < a.length; i++) c[i] = a[i] ^ b[i];
        return c;
    }
    function revLexi(seq) {           // next string in reverse lexicographical order
        var max = true, pos = seq.length, set = 1;
        while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
        if (pos < 0) return false;
        seq[pos] = 0;
        while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
        return true;
    }
}
document.write(flipBits([1,1,1], 2) + "<br>");
document.write(flipBits([0,0,1,1,0,1,0,1,1,1], 4) + "<br>");
document.write(flipBits([1,1,1,1,1,1], 4) + "<br>");

Ваш ответ на вопрос