Wannafly 挑战赛12 D

链接：https://www.nowcoder.com/acm/contest/79/D
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给一个n x m的01矩阵，其中C个格子是1，其余全是0。求有多少全0的子矩阵。
答案对10⁹ + 7取模。

输入描述:

第一行三个数，分别表示n,m,C。
接下来C行，每行两个数x,y（1 <= x <= n, 1 <= y <= m)，表示为1的格子，保证互不相同。

输出描述:

仅一行一个数，表示答案。

示例1

输入

3 3 1
2 3

输出

备注:

1 ≤ n,m ≤ 10

⁹


0 ≤ C ≤ 5000
思路：按坐标排序，统计每个1第一次出现的子矩阵个数即可。

 1 #include <iostream>
 2 #include <fstream>
 3 #include <sstream>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <string>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <queue>
11 #include <stack>
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <list>
16 #include <iomanip>
17 #include <cctype>
18 #include <cassert>
19 #include <bitset>
20 #include <ctime>
21 
22 using namespace std;
23 
24 #define pau system("pause")
25 #define ll long long
26 #define pii pair<int, int>
27 #define pb push_back
28 #define mp make_pair
29 #define clr(a, x) memset(a, x, sizeof(a))
30 
31 const double pi = acos(-1.0);
32 const int INF = 0x3f3f3f3f;
33 const int MOD = 1e9 + 7;
34 const double EPS = 1e-9;
35 
36 /*
37 #include <ext/pb_ds/assoc_container.hpp>
38 #include <ext/pb_ds/tree_policy.hpp>
39 
40 using namespace __gnu_pbds;
41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T;
42 */
43 
44 
45 struct gg {
46     int x, y;
47     gg () {}
48     gg (int x, int y) : x(x), y(y) {}
49     bool operator < (const gg &g) const {
50         return x == g.x ? y < g.y : x < g.x;}
51 } g[5015];
52 int n, m, c;
53 ll ans;
54 int main() {
55     scanf("%d%d%d", &n, &m, &c);
56     for (int i = 1; i <= c; ++i) {
57         scanf("%d%d", &g[i].x, &g[i].y);
58     }
59     sort(g + 1, g + c + 1);
60     g[0] = gg(0, 0);
61     for (int i = 1; i <= c; ++i) {
62         ll k = (n - g[i].x + 1);
63         for (int j = i - 1, l = 1, r = m; ~j; --j) {
64             ans += k * (g[i].y - l + 1) % MOD * (r - g[i].y + 1) % MOD * (g[j + 1].x - g[j].x) % MOD;
65             if (g[j].y <= g[i].y) l = max(l, g[j].y + 1);
66             if (g[i].y <= g[j].y) r = min(r, g[j].y - 1);
67         }
68     }
69     ans = (ll)n * (n + 1) / 2 % MOD * ((ll)m * (m + 1) / 2 % MOD) - ans;
70     printf("%d
", (ans % MOD + MOD) % MOD);
71     return 0;
72 }

View Code