Число двоичных матриц n x m по модулю c, не более k последовательных чисел 1 в каждом столбце

Question

Я пытаюсь вычислить количество двоичных матриц nxm с не более k последовательных значений 1 в каждом столбце. После нескольких исследований я понял, что этого будет достаточно, чтобы найти векторы с 1 столбцом и n строками. Например, если у нас есть p векторов, требуемое количество матриц будет m^p. Поскольку n и m очень большие (< 2.000.000), я не могу найти подходящее решение. Я пытаюсь найти формулу повторения, чтобы построить матрицу, чтобы помочь мне вычислить ответ. Не могли бы вы предложить мне какое-нибудь решение?

Answer 1

Существует (k + 1)-состоящая динамическая программа (состояние = количество предыдущих 1 с, от 0 до k). Короче говоря, вы можете быстро вычислить большие термины, взяв n-ую степень k + 1 на k + 1 целочисленную матрицу, как (например, для k = 4)

1 1 0 0 0
1 0 1 0 0
1 0 0 1 0
1 0 0 0 1
1 0 0 0 0

по модулю с и суммирования первого ряда.