在$3\times 2$的交叉对角线方格中，一共有37种不同的长方形，如下图所示：

长宽都不超过$3\times 2$的交叉对角线方格共有五个，即$1\times 1$、$1\times 2$、$2\times 1$、$2\times 2$、$3\times 1$，在这些交叉对角线方格中分别可以有1、4、4、18、8种不同的长方形。

把这些数和37相加，可得在形状不超过$3\times 2$的交叉对角线方格中一共有72种长方形。

在形状不超过$47\times 43$的交叉对角线方格中一共有多少种长方形？

本题难度:

解答

为方便叙述，称两边水平或垂直的长方形为第一类长方形，称斜放的长方形（即两边平行于对角线）为第二类长方形。

根据第85题中的分析，在$m\times n$的方格中共有$mn(m+1)(n+1)/4$个第一类长方形。

要统计第二类长方形的数量，我们可以统计其左端点可能的位置。给定点A，以之为作端点，分别向右上方和右下方以$\sqrt2/2$步长前进，设在两个方向上各自前进了若干步分别到达点B和点C，并令$D=A+(\overrightarrow{AB}+\overrightarrow{AC})$，那么只要这四点的坐标都在方格内，ABCD就组成一个方格内的第二类长方形。

若A的坐标是$(a,b)$，则向右上方最多可以前进$2\min(a,n-b)$步，向右下方做多可以前进$2\min(m-a,n-b)$步，枚举所有可能的点A即得结果$846910284$。

d={}
s=0
for m in range(1,44):
    for n in range(1,48):
        if (m,n) not in d:
            r=m*n*(m+1)*(n+1)/4
            for a in range(1,m):
                for b in range(n):
                    for i in range(1,2*min(a,n-b)+1):
                        for j in range(1,2*min(m-a,n-b)+1):
                            r+=(a+(j-i)*0.5<=m and b+(j+i)*0.5<=n)
            for a in range(m):
                for b in range(n-1):
                    for i in range(1,int(2*min(a+0.5,n-b-0.5))+1):
                        for j in range(1,int(2*min(m-a-0.5,n-b-0.5))+1):
                            r+=(a+0.5+(j-i)*0.5<=m and b+0.5+(j+i)*0.5<=n)
            d[(m,n)]=d[(n,m)]=r
        s+=d[(m,n)]
        print m,n,r,s

print s