algorithm - 以 c 为模的二进制 nxm 矩阵的数量，每列最多 k 个连续的 1

Question

我正在尝试计算每列中最多 k 个连续值为 1 的 nxm 二进制矩阵的数量。经过一些研究，我发现找到具有 1 列和 n 行的向量就足够了。例如，如果我们有 p 个向量，则所需的矩阵数量为 m^p。因为 n 和 m 非常大（< 2.000.000），我找不到合适的解决方案。我试图找到一个递归公式，以建立一个矩阵来帮助我计算答案。那么你能建议我任何解决方案吗？

Answer 1

有一个 (k + 1) 状态动态程序（状态 = 先前 1 的数量，从 0 到 k）。长话短说，您可以通过将 k + 1 的 n 次方乘以 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

模 c 并对第一行求和。