算法-数方块-Google kickstart2017 Round A - Problem A

题目描述

给定一个r行c列的二维数组构成的矩形网格,该形状内存在多少个正方形。由于结果可能太大,将结果对$10^9 + 7 (1000000007)$取模输出。

比如对于如下输入样例:

4
2 4
3 4
4 4
1000 500

对应输出如下:

Case #1: 3
Case #2: 10
Case #3: 20
Case #4: 624937395

可能解法

首先观察下列$4 \times 4$的网格图,对应边长为$3 \times 3$:


网格示意图

我们可以发现:

  • 边长为1的正方形有$(r - 1)(c - 1)$个;
  • 边长为2的正方形有$(r - 2)(c - 2)$个,此外每个边长为2的正方形内部有一个斜的边长为$\sqrt{2}$正方形,因此总数为$2(r - 2)(c - 2)$;
  • 边长为3的正方形有$(r - 3)(c - 3)$个,此外每个边长为3的正方形内部有一个斜的边长为$\sqrt{5}$正方形,因此总数为$3(r - 3)(c - 3)$;
  • 边长为n的正方形及其内部的正方形共有$n(r - n)(c - n)$个。

同时,最大的边长n满足:$n = \min \lbrace r - 1, c - 1 \rbrace$。据此已经可以通过循环求和得到结果,但是针对大样本时间会来不及。因此我们考虑自行化简如下:
$$
\begin{align}\\
&\sum\limits_{i=1}^{n}{i(r - i)(c - i)}\\
&= rc \cdot \sum\limits_{i=1}^{n}{i} - (r + c) \cdot \sum\limits_{i=1}^{n}{i^2} + \sum\limits_{i=1}^{n}{i^3}\\
&= \frac{n(n+1)}{2} \cdot rc - \frac{n(n+1)(2n+1)}{6} \cdot (r+c) + \frac{n^2(n+1)^2}{4}\\
\end{align}
$$
从而可以很方便的通过一次计算得到结果。最后,为了避免大数运算,需要在计算的过程中进行取模。要注意的是,由于中间有减法存在,需要检查最后的结果是否合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<string>
#include<cmath>
#include<fstream>
using namespace std;
int main() {
int module = 1000000007;
int T;
cin >> T;
for (int Case = 1; Case <= T; Case++) {
int r, c;
cin >> r >> c;
long m = min(r - 1, c - 1);
long sum = 0;
long temp1 = r * c;
long temp2 = r + c;
sum += ((m + 1)*m/2 * temp1)%module;
sum += -((int)(m + 1)*m*(2*m + 1)/6 *temp2)%module;
sum += ((m + 1)*(m + 1)*m*m/4)%module;
sum = sum%module;
if(sum < 0){
sum += module;
}
cout << "Case #" << Case << ": " << sum << endl;
}
return 0;
}
}

复杂度分析

算法单次时间复杂度为$\mathcal{O}(1)$,空间复杂度也为$\mathcal{O}(1)$。

文章目录
  1. 1. 题目描述
  2. 2. 可能解法
  3. 3. 复杂度分析
|