题目147：交叉格子中的长方形

欧拉计划

Rectangles in cross-hatched grids

In a 3x2 cross-hatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.

There are 5 grids smaller than 3x2, vertical and horizontal dimensions being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18

Adding those to the 37 of the 3x2 grid, a total of 72 different rectangles could be situated within 3x2 and smaller grids.

How many different rectangles could be situated within 47x43 and smaller grids?

题目：

在一个 3×2 的交叉格子中，一共可以找出 37 个矩形，如下图所示。

在区分横纵的情况下，小于 3×2 的格子一共有 5 个，1x1, 2x1, 3x1, 1x2 以及 2x2。如果将它们都用交叉线画成交叉格子，在它们内部分别可以找出如下数目的矩形：

1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18

将上面的数字与 3×2 中的 37 相加，可得在 3×2 以及更小的交叉格子中一共可以得到 72 个不同的矩形。

问，在 47×43 以及更小的交叉格子里，一共可以得到多少个不同的矩形？

加餐

正矩形数是85题对应的算法；斜矩形可以递推，但很麻烦，可以通过分析计算或找规律直接将m×n的网格里包含多少i×j的斜矩形个数的代数表达式写出来

瓦屋青衣

import time
import math

timeStart = time.time()

m, n = 47, 43

def rect(m:int, n:int) -> int:
    ans = m*(m+1)*n*(n+1)//4
    for x in range(2, 2*min(m, n)+1):
        row0 = (m-(x-1)//2)
        col0 = (n-(x-1)//2)
        row1 = (m-x//2)
        col1 = (n-x//2)
        y = (row0*col0 + row1*col1) * ((x-1)//2) + (row1*col0 + row0*col1) * (x//2)
        ans += y
    return ans

ans = 0
for i in range(1, m+1):
    for j in range(1, n+1):
        ans += rect(i, j)
print(ans)

print(f'time used: {time.time() - timeStart: .3f} s')