牛客寒假6-F十字阵列

链接：https://ac.nowcoder.com/acm/problem/201986
来源：牛客网

题目描述

小 Q 新学会了一种魔法，可以对一个 N行M列的网格上的敌人造成伤害

第 i 次使用魔法可以对网格上的一个十字形区域（即第 xi 行和第 yi 列的并）中的每个格子上的敌人造成 zi 点伤害

现在小 Q 一共使用了 H 次魔法，你需要在所有的施法完成之后统计造成伤害的情况，详见输出描述

提醒：本题输入规模较大，请使用高效的输入方式

1≤H≤500,000 1≤xi,yi,zi,N,M≤2000 1 ≤xi≤N,1≤yi≤M

输入描述:

第一行 3 个数字 N,M,H

接下来 H 行，每行 3 个正整数 xi，yi，zi

输出描述:

为了避免大量的输出，假设第 i 行第 j 列受到的总伤害是 w _ij

你只需要输出Σw _ij(i+j)对 10^9+7 取模的结果即可

示例1

输入

复制

输出

复制

说明

造成伤害的情况是：

1 3 4 5 6

3 2 5 6 7

4 5 3 7 8

5 6 7 4 9

6 7 8 9 5

补充的说明：

890 = 1*(1+1)+3*(1+2)+4*(1+3)+...+5*(5+5）,一共25项累加得到890

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 #define pi acos(-1.0)
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 template<class T>inline void read(T &res)
10 {
11     char c;T flag=1;
12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
14 }
15 
16 namespace _buff {
17     const size_t BUFF = 1 << 19;
18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
19     char getc() {
20         if (ib == ie) {
21             ib = ibuf;
22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
23         }
24         return ib == ie ? -1 : *ib++;
25     }
26 }
27 
28 int qread() {
29     using namespace _buff;
30     int ret = 0;
31     bool pos = true;
32     char c = getc();
33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
34         assert(~c);
35     }
36     if (c == '-') {
37         pos = false;
38         c = getc();
39     }
40     for (; c >= '0' && c <= '9'; c = getc()) {
41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
42     }
43     return pos ? ret : -ret;
44 }
45 
46 const int maxn = 2007;
47 const int M = 1000000007;
48 
49 int n,m,h;
50 
51 int a[maxn], b[maxn];
52 int ab[maxn][maxn];
53 
54 int main()
55 {
56     scanf("%d %d %d",&n, &m, &h);
57 
58     int ans = 0;
59     int x, y, z;
60     while(h--) {
61         scanf("%d %d %d",&x,&y,&z);
62         a[x] += z;
63         b[y] += z;
64         ab[x][y] += z;
65     }
66     for(int i = 1; i <= n; ++i) {
67         for(int j = 1; j <= m; ++j) {
68             //printf("val[%d][%d]:%lld\n",i,j,a[i] + a[j] - ab[i][j]);
69             ans = (ans + (LL)(a[i] + b[j] - ab[i][j]) * (i+j) % M) % M;
70         }
71     }
72     printf("%d\n",(ans+M)%M);
73     return 0;
74 }