python - 如何计算具有 3 个有效值的 NxM 网格的不同组合

Question

我有 3 个有效值:a、b、c我可以将它们插入 Nx3 网格中，使得没有行或列包含相同值的单元格。如何计算使用 N 行可以创建的有效模式的数量？

例如，如果N = 4，则有效模式总数为296490。

这是我的尝试:

def countPatterns(n):

    dp1, dp2 = 6,6
    mod = 10 ** 9 + 7
    
    for i in range(2, n+1):
        dp1, dp2 = (dp1 * 3 + dp2 * 2) % mod, (dp1 * 2 + dp2 * 2) % mod
    return (dp1 + dp2) % mod

当 N = 4 时，输出应该是 174，但我得到的是 54。

Answer 1

这可以使用组合数学的标准技术来解决。

import math


# Counts the number of grids where the first i rows and first j columns are
# monochrome. All of the monochrome rows and columns must have the same color if
# and only if both i and j are nonzero. Otherwise, the color choices are
# independent.
def count_monochrome(n, i, m, j):
    return 3 ** (1 if i and j else i + j) * 3 ** ((n - i) * (m - j))


# Uses inclusion-exclusion to count the number of grids with no monochrome row
# or column.
def count(n, m=3):
    # There are math.comb(n, i) * math.comb(m, j) intersections with i
    # monochrome rows and j monochrome columns.
    return sum(
        math.comb(n, i)
        * math.comb(m, j)
        * (-1) ** (i + j)
        * count_monochrome(n, i, m, j)
        for i in range(n + 1)
        for j in range(m + 1)
    ) % (10 ** 9 + 7)


print(count(4))