Project Euler 147

题目

Rectangles in cross-hatched grids

In a $3\times2$ 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 $3\times2$, vertical and horizontal dimensions being important, i.e. $1\times1$, $2\times1$, $3\times1$, $1\times2$ and $2\times2$. If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

$\begin{aligned}
1\times1&: 1 \
2\times1&: 4 \
3\times1&: 8 \
1\times2&: 4 \
2\times2&: 18
\end{aligned}$

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

How many different rectangles could be situated within $47\times43$ and smaller grids?

解决方案

假设该矩形大小为$n\times m(n\le m)$。

首先，和矩形边上平行的小矩形个数为$T(n,m)=\dfrac{n(n+1)m(m+1)}{4}$。

接下来考虑倾斜矩形的个数，使用了一些和多项式相关的小技巧。

合理猜测：这一类的矩形个数可以用多项式来表示，并且项的最高次数和上面一样，也是$4$。这种猜测个人认为比较合理，因为随着$n,m$的增长，两种方式矩形的增长速度感知上是相同的。

因此，假设这个公式为$p(n,m)=\sum{i=0}^4\sum{j=0}^{4-i}a{i,j} n^im^j$.其中，多项式$a{i,j}$是未知的，用待定系数求出来。

我首先写了一份比较暴力并且不美观的代码，用来计算小范围内的$p(n,m)$值：

# include <bits/stdc++.h>
using namespace std;
int solve(int n,int m){
    int o=max(n,m)*2;
    int ans=0;
    n<<=1;m<<=1;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++){
        if((i+j)&1) continue;
        for(int d=1;d<=o;d++){
            int x=i-d,y=j+d;
            if(x<0||y>m) break;
            for(int k=1;k<=o;k++){
                if(max(k+i,k+x)<=n&&max(k+j,k+y)<=m) ++ans;
                else break;
            }
        }
    }
    return ans;
}
int main(){
    int M=7;
    for(int n=1;n<=M;n++)
        for(int m=n;m<=M;m++)
            printf("%d %d %d\n",n,m,solve(n,m));
}

用统计出来的$n,m,p(n,m)$，全部代入到公式$p(n,m)$中。由此构造出一个方程组。

使用sympy库的linsolve函数最终解出方程组，回代到公式，整合，也就是：

$\dfrac{n((2m-n)(4n^2-1)-3)}{6}$

最终把上面的第一种情况加起来即可。

不失一般性，如果$n>m$，那么将上面的式子的$n,m$两个变量进行交换。

本题甚至可以进一步整理公式直接导出答案$\sum{i=1}^N\sum{j=1}^M{T(i,j)+p(i,j)}$的通式，此处不赘述。

代码

N, M = 47, 43


def solve(n, m):
    if n > m:
        n, m = m, n
    return n * (n + 1) * m * (m + 1) // 4 + n * ((2 * m - n) * (4 * n * n - 1) - 3) // 6


ans = 0
for i in range(1, N + 1):
    for j in range(1, M + 1):
        ans += solve(i, j)
print(ans)