如何计算矩形网格中的矩形数？

Question

我想计算矩形中的矩形数.可以使用公式来完成

(X ^ 2 + X)(Y ^ 2 + Y)/ 4

但它也包括完美的正方形,如1*1,2*2,3*3等.我不想在我的计算中包含它.我怎么能这样做？

Answer 1

好吧,你必须点之间的整数矩形数坐标(0, 0),(x, 0),(x, y)和(0, y),x和y为整数太大.你现在需要从这个总和中删除完美的正方形.

为了计算它,我们来评估平方数1*1:显然x*y有它们.对于正方形2*2,我们可以x-1选择x坐标和y-1这个正方形左下角的y坐标,因为这个正方形的宽度:这会产生(x-1)*(y-1)正方形.同上,我们将有(x-2)*(y-2)正方形3*3等

因此,对于一个给定的i,我们有(x - i + 1) * (y - i + 1)正方形i*i,并i从去1到最小的x和y(如果当然x是4和y是7,我们不能有一个边大于4平方).

所以,如果m = min(x, y),我们有:

Sum_Squares = Sum(i = 1, i = m, (x - i + 1) * (y - i + 1))
            = Sum(j = 0, j = m - 1, (x - i) * (y - i))
            = Sum(j = 0, j = m - 1, x*y - (x+y)*j + j^2)
            = m*x*y - (x+y)*Sum(j = 0, j = m - 1, j) + Sum(j = 0, j = m - 1, j^2)
            = m*x*y - (x+y)*Sum(j = 1, j = m - 1, j) + Sum(j = 1, j = m - 1, j^2)
            = m*x*y - (x+y)*m*(m-1)/2 + (m-1)*m*(2*m-1)/6

我通过索引change(j = i - 1)并通过众所周知的公式得到它:

Sum(i = 1, i = n, j) = n*(n + 1)/2
Sum(i = 1, i = n, j^2) = n*(n + 1)*(2*n + 1)/6

你只需要删除该Sum_Squares从(x^2+x)(y^2+y)/4你就大功告成了!