如何计算具有 3 个有效值的 NxM 网格的不同组合
How to calculate the different combinations of an NxM grid with 3-valid values
我有 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。
这可以使用组合学的标准技术来解决。
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))
简答
这也可以用数学方法解决，所以公式是：
24n - (9 * 8n - 9 * 2n - 18 * 3n + 24)
def countPatterns(n):
result = 24**n - (9 * 8**n - 9*2**n - 18*3**n + 24)
mod = 10 ** 9 + 7
return result % mod
print (countPatterns(4))
296490
长答案
1。条件：没有行包含相同的值
对于给定的行，有 3 种方法可以在每个单元格中设置颜色。所以，有33=27种可能的组合。但是，在这些 27 组合中，3 是 GGG、BBB 和 RRR。因此，必须排除它们并且一行中的有效组合数为 27 - 3 = 24.
因此，n行的table的组合总数为24n
2。条件：没有列包含相同的值
为了解决这种情况，我们可以统计所有“无效组合”，然后从总数中减去它们的数量（如上一节所述，即 24n）。
2.1 无效组合
- 只有第一列具有相同的值。
- 只有第二列具有相同的值。
- 只有第三列具有相同的值。
- 只有 2 个第一列具有相同的值（第一列的值不一定等于另一列）。
- 只有最后 2 列具有相同的值。
- 只有第一列和最后一列的值相同。
- 每列中的值相等。
显然，1 的组合数等于 2 和 3。关于 4、5 和 6.
也可以注意到同样的情况
如果我们将 1 到 7 的组合加起来，那么我们将得到总数。
但是，很难单独计算 (1)-(7)，但更容易计算至少 k 列具有相同值的组合数。一旦找到这些，我们将应用 inclusion-exclusion principle 来查找问题中提出的组合数。
2.1.1 第一列具有相同的值
对于每一行，有 8 种组合，使得该行以 R:
开头
RRG
RRB
RGR
RGG
RGB
RBR
RBG
RBB
这意味着对于 table 和 n，有 8n 种组合，其中第一列由 8 组成。其中，第一列从R、G或B、
开始的组合有3*8n种
现在，重要的是要认识到这个数字代表 4 个无效案例 - 1、4、6 和 7（所有集合包含第一列的列）。
2.1.2 第二列具有相同的值
基本上我们可以用和上面一样的逻辑来实现也是3*8n.
这表示 2、4、5 和 7。
2.1.3 第三列具有相同的值
和之前一样 - 3*8n.
这包括 3、5、6 和 7。
如果我们将这些 3 步骤的组合相加，我们将得到 9*8n。但是，如这些步骤中所述，我们将计算 4、5 和 6 两次。 7将被计算三次。
2.1.4 2列具有相同的值
让我们数一数 2 第一列，因为每对列的数字仍然相同。
如果一行以 2 种相同的颜色开头，则每种颜色有 2 种组合。如果不是，则每对有 3 个组合（有 6 个可能的对）。因此，组合总数为3 * 2n + 6 * 3n.
所以，4和7的组合数是3 * 2n + 6 * 3n.
5和7的组合数为3 * 2n + 6 * 3n.
6和7的组合数为3 * 2n + 6 * 3n.
2.1.5 每列中的值相等
这意味着所有行必须相等。由于只有 24 种构造行的方法，因此有 24 种方法可以使列中的所有值都相等。所以，它是 24.
无效案例总数
如前所述，如果我们总结2.1.1，2.1.2和2.1.3，那么我们将计算4、5和6两次，7 - 3次（来自2.1).由于每对列的组合数相同，我们可以减去 3 * 2n + 6 * 2n 3次（从2.1.4开始），然后将三列情况的组合数加一次（因为减去后就没有了）
9 * 8n - 3 * (3 * 2n + 6 * 3n) + 24 = 9 * 8n - 9 * 2n - 18 * 3n + 24
3。最终答案
现在，只需从 24n 中减去无效案例数:
24n - (9 * 8n - 9 * 2n - 18 * 3n + 24)
不要忘记在最后应用 109 + 7 的模运算。
我有 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。
这可以使用组合学的标准技术来解决。
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))
简答
这也可以用数学方法解决，所以公式是：
24n - (9 * 8n - 9 * 2n - 18 * 3n + 24)
def countPatterns(n):
result = 24**n - (9 * 8**n - 9*2**n - 18*3**n + 24)
mod = 10 ** 9 + 7
return result % mod
print (countPatterns(4))
296490
长答案
1。条件：没有行包含相同的值
对于给定的行，有 3 种方法可以在每个单元格中设置颜色。所以，有33=27种可能的组合。但是，在这些 27 组合中，3 是 GGG、BBB 和 RRR。因此，必须排除它们并且一行中的有效组合数为 27 - 3 = 24.
因此，n行的table的组合总数为24n
2。条件：没有列包含相同的值
为了解决这种情况，我们可以统计所有“无效组合”，然后从总数中减去它们的数量（如上一节所述，即 24n）。
2.1 无效组合
- 只有第一列具有相同的值。
- 只有第二列具有相同的值。
- 只有第三列具有相同的值。
- 只有 2 个第一列具有相同的值（第一列的值不一定等于另一列）。
- 只有最后 2 列具有相同的值。
- 只有第一列和最后一列的值相同。
- 每列中的值相等。
显然，1 的组合数等于 2 和 3。关于 4、5 和 6.
如果我们将 1 到 7 的组合加起来，那么我们将得到总数。
但是，很难单独计算 (1)-(7)，但更容易计算至少 k 列具有相同值的组合数。一旦找到这些，我们将应用 inclusion-exclusion principle 来查找问题中提出的组合数。
2.1.1 第一列具有相同的值
对于每一行，有 8 种组合，使得该行以 R:
RRG
RRB
RGR
RGG
RGB
RBR
RBG
RBB
这意味着对于 table 和 n，有 8n 种组合，其中第一列由 8 组成。其中，第一列从R、G或B、
现在，重要的是要认识到这个数字代表 4 个无效案例 - 1、4、6 和 7（所有集合包含第一列的列）。
2.1.2 第二列具有相同的值
基本上我们可以用和上面一样的逻辑来实现也是3*8n.
这表示 2、4、5 和 7。
2.1.3 第三列具有相同的值
和之前一样 - 3*8n.
这包括 3、5、6 和 7。
如果我们将这些 3 步骤的组合相加，我们将得到 9*8n。但是，如这些步骤中所述，我们将计算 4、5 和 6 两次。 7将被计算三次。
2.1.4 2列具有相同的值
让我们数一数 2 第一列，因为每对列的数字仍然相同。
如果一行以 2 种相同的颜色开头，则每种颜色有 2 种组合。如果不是，则每对有 3 个组合（有 6 个可能的对）。因此，组合总数为3 * 2n + 6 * 3n.
所以，4和7的组合数是3 * 2n + 6 * 3n.
5和7的组合数为3 * 2n + 6 * 3n.
6和7的组合数为3 * 2n + 6 * 3n.
2.1.5 每列中的值相等
这意味着所有行必须相等。由于只有 24 种构造行的方法，因此有 24 种方法可以使列中的所有值都相等。所以，它是 24.
无效案例总数
如前所述，如果我们总结2.1.1，2.1.2和2.1.3，那么我们将计算4、5和6两次，7 - 3次（来自2.1).由于每对列的组合数相同，我们可以减去 3 * 2n + 6 * 2n 3次（从2.1.4开始），然后将三列情况的组合数加一次（因为减去后就没有了）
9 * 8n - 3 * (3 * 2n + 6 * 3n) + 24 = 9 * 8n - 9 * 2n - 18 * 3n + 24
3。最终答案
现在，只需从 24n 中减去无效案例数:
24n - (9 * 8n - 9 * 2n - 18 * 3n + 24)
不要忘记在最后应用 109 + 7 的模运算。