- 个人思路:
-
场景1:当高为1,宽为n时
-
计算:
- 固定(0,0)和(0,1)为边界
- 以(0,0),(0,1),(1,0)和(1,1)为顶点的区域内,符合要求的三角形有4个
- 以(0,0),(0,1),(2,0)和(2,1)为顶点的区域内,符合要求的三角形有4个
- ...
- 以(0,0),(0,1),(n,0)和(n,1)为顶点的区域内,符合要求的三角形有4个
- 上述符合要求的有4n个
- 固定(1,0)和(1,1)为边界
- 以(1,0),(1,1),(2,0)和(2,1)为顶点的区域内,符合要求的三角形有4个
- 以(1,0),(1,1),(3,0)和(3,1)为顶点的区域内,符合要求的三角形有4个
- ...
- 以(1,0),(1,1),(n,0)和(n,1)为顶点的区域内,符合要求的三角形有4个
- 上述符合条件的三角形有4(n-1) 个
- ...
- 固定以(n-1,0)和(n-1,1)为边界
- 以(n-1,0),(n-1,1),(n,0)和(n,1)为顶点的区域内,符合要求的三角形有4个
- 上述符合条件的三角形有4(1) 个
- 综上所述,当高为1,宽为n时,符合要求的三角形有4*(1+2+3+...n) = 4*(n*(n+1))/2
- 固定(0,0)和(0,1)为边界
-
场景2:当高为2,宽为n时
-
计算:
- 可以将该图形分割成两个高为1,宽为n的两个矩形,根据场景1中的结论可以得到2 * 4*(n*(n+1))/2个 符合要求的三角形
- 然后仅考虑高为2的情况,然后宽可以为1,2,3...n,这种情况与场景1类型,所以也可以得到4*(n*(n+1))/2 个符合要求的三角形
- 综上所述,当高为2,宽为n时,符合要求的三角形有4*(n*(n+1))/2 + 2*4*(n*(n+1))/2 = (1+2)*4*(n*(n+1))/2个符合要求的三角形
-
场景3:当高为3,宽为n时
-
计算:
- 可以将该图形分割成三个高为1,宽为n的矩形,根据场景1中的结论可以得到3 * 4*(n*(n+1))/2个 符合要求的三角形
- 然后将该图形分割成两个高为2,宽为n的矩形,根据场景1中的结论可以得到2 * 4*(n*(n+1))/2个 符合要求的三角形
- 接着仅考虑高为3的情况,然后宽可以为1,2,3...n,这种情况与场景1类型,所以也可以得到4*(n*(n+1))/2 个符合要求的三角形
- 综上所述,当高为3,宽为n时,符合要求的三角形有4*(n*(n+1))/2 + 2*4*(n*(n+1))/2 + 3*4*(n*(n+1))/2 = (1+2+3)*4*(n*(n+1))/2个符合要求的三角形
-
由此可以类推出:当高为m宽为n的矩形,符合要求的三角形 (1+2+3+...+m)*4*(n*(n+1))/2 = (m*(m+1))/2 * 4 * (n*(n+1))/2 = (m*(m+1))*(n*(n+1))
-
const long long mod = 1000000007;
int getNums(int n, int m) {
int answer = 0;
long long temp = 0;
n--;
m--;
temp = (long long)n * (long long)(n + 1) % mod;
temp = temp * (long long)m % mod;
temp = temp * (long long)(m + 1) % mod;
answer = temp;
return answer;
}