题解 | #格点三角形#

• 个人思路：

  • 场景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

  • 场景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;
}