Количество смежных битов

Question

вот проблема из spoj, которая гласит

Для строки из n битов x1, x2, x3, ..., Xn количество соседних битов строки (AdjBC (x)) задается как

X1 * X2 + X2 * X3 + X3 * X4 + ... + Xn-1 * Xn

, который считает количество раз 1 бит соседствует с другим 1 битом. За пример:

AdjBC (011101101) = 3
AdjBC (111101101) = 4
AdjBC (010101010) = 0

и вопрос: напишите программу, которая принимает в качестве входных целых чисел n и k и возвращает количество битовых строк x из n битов (из 2ⁿ), которые удовлетворяют AdjBC (x) = k.

Понятия не имею, как решить эту проблему. Можете ли вы помочь мне решить это?

Спасибо

Answer 1

Часто в комбинаторных задачах это помогает взглянуть на набор значений, которые он производит. Используя грубую силу, я рассчитал следующую таблицу:

  k   0   1   2   3   4   5   6
n +----------------------------
1 |   2   0   0   0   0   0   0
2 |   3   1   0   0   0   0   0
3 |   5   2   1   0   0   0   0
4 |   8   5   2   1   0   0   0
5 |  13  10   6   2   1   0   0
6 |  21  20  13   7   2   1   0
7 |  34  38  29  16   8   2   1

Первый столбец - это знакомая последовательность Фибоначчи, которая удовлетворяет рекуррентному соотношению f(n, 0) = f(n-1, 0) + f(n-2, 0)

Другие столбцы удовлетворяют рекуррентному соотношению f(n, k) = f(n - 1, k) + f(n - 1, k - 1) + f(n - 2, k) - f(n - 2, k - 1)

С этим вы можете выполнять динамическое программирование:

INPUT: n, k
row1 <- [2,0,0,0,...] (k+1 elements)
row2 <- [3,1,0,0,...] (k+1 elements)
repeat (n-2) times
  for j = k downto 1 do
    row1[j] <- row2[j] + row2[j-1] + row1[j] - row1[j-1]
  row1[0] <- row1[0] + row2[0]
  swap row1 and row2
return row2[k]

Answer 2

В качестве подсказки вы можете разбить его на два случая: числа, заканчивающиеся на 0, и числа, заканчивающиеся на 1.

def f(n, k):
    return f_ending_in_0(n, k) + f_ending_in_1(n, k)

def f_ending_in_0(n, k):
    if n == 1: return k == 0
    return f(n - 1, k)

def f_ending_in_1(n, k):
    if n == 1: return k == 0
    return f_ending_in_0(n - 1, k) + f_ending_in_1(n - 1, k - 1)

Это дает правильный вывод, но выполнение занимает много времени.Вы можете применить стандартные методы динамического программирования или запоминания, чтобы заставить это работать достаточно быстро.

Answer 3

Я опаздываю на вечеринку, но у меня есть линейное решение временной сложности.

Для меня это больше математическая проблема.Вы можете прочитать подробное решение в этом блоге , написанном мной.Далее следует краткое описание.Я хотел бы поставить немного LaTeX, но SO не позволяет этого.

Предположим, что для данных n и k наш ответ дается функцией f(n,k).Используя метод Беггара, мы можем получить следующую формулу

f(n,k) = SUM C(k+a-1,a-1)*C(n-k+1-a,a), где a проходит от 1 до (n-k+1)/2

Здесь C(p,q) обозначает биномиальные коэффициенты.

Итак, чтобы получить наш ответ, мы должны рассчитать оба биномиальных коэффициента для каждого значения a.Мы можем вычислить биномиальную таблицу заранее.Этот подход затем даст наш ответ в O(n^2), так как мы должны вычислить таблицу.

Мы можем улучшить сложность времени, используя формулу рекурсии C(p,q) = (p * C(p-1,q-1))/q для вычисления текущего значения биномиальных коэффициентов из их значенийв предыдущем цикле.

Наш финальный код выглядит следующим образом:

long long x=n-k, y=1, p=n-k+1, ans=0;
ans += x*y;

for(int a=2; a<=p/2; a++)
{
    x = (x*(p-2*a+1)*(p-2*a+2))/(a*(p-a+1));
    y = (y*(k+a-1))/(a-1);
    ans += x*y;
}

Вы можете найти полностью принятое решение в моем GitHub репозитории .