algorithm - c を法とするバイナリ nxm 行列の数。各列の最大 k 個の連続する 1 が含まれます。

Question

各列で最大 k 個の連続する値が 1 の nxm バイナリ行列の数を計算しようとしています。いくつかの調査の後、1列とn行のベクトルを見つけるだけで十分であることがわかりました。たとえば、p 個のベクトルがある場合、必要な行列の数は m^p になります。n と m が非常に大きい (< 2.000.000) ため、適切な解決策が見つかりません。答えを計算するのに役立つマトリックスを作成するために、再帰式を見つけようとしています。それで、何か解決策を提案してもらえますか？

Answer 1

(k + 1) 状態の動的プログラム (状態 = 0 から k までの前の 1 の数) があります。簡単に言うと、次のように k + 1 x k + 1 整数行列の n 乗を取ることで、その大きな項をすばやく計算できます (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

c を法とし、最初の行を合計します。