题目描述
Mirko在汽车后座找到了一个N行M列的矩形，矩形第一行由数字1，2,3，…，M，第二行由M+1，M+2,…,2M组成，一直到第N行数字，由(N-1)*M+1, (N-1)M+2,…, NM组成。
举个例子，对于N=3，M=4的矩形，有：
1 2 3 4
5 6 7 8
9 10 11 12
由于这样的矩形不够有趣，于是他进行K次选择，每次选择一行或者一列，将这一行或一列上的所有值乘以一个非负整数。
K次操作完成后，Mirko想知道这个矩形中所有值的总和是多少。由于这个数字可能会非常大，答案将对1e9+7取模。
输入格式
第一行输入三个正整数N（1≤N≤1000000）,M(1≤M≤1000000)和K(1≤K≤1000)，表示矩形的大小和操作的次数。
接下来K行，每行包含三个字符。如果将第X行的所有值乘以Y，那么输入“R X Y”，如果将第X列的所有值乘以Y，那么输入“S X Y”。
输出格式
输出矩形中所有值的和对1e9+7取模的值。
样例
样例输入1
3 4 4
R 2 4
S 4 1
R 3 2
R 2 0
样例输出1
94
样例输入2
3 1 1
S 1 4
样例输出2
24
样例输入3
2 4 4
S 2 0
S 2 3
R 1 5
S 1 3
样例输出3
80
数据范围与提示
对于第一组样例，完成四次操作后，矩阵情况如下：
1 2 3 4
0 0 0 0
18 20 22 24
这时，矩阵内所有的元素和为：1+2+3+4+0+0+0+0+18+20+22+24=94
解题思路
n,m很大，操作很少，我们考虑从操作入手。
我们先就直接操作行列。
我们会发现，行列的交点，我们的处理是有问题的，比如说第一行2，第一列3，我们仅仅加了5，这少的部分就是x * y - x - y。就按这样处理即可。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdlib>
#include<map>//50000004
#define mod 1000000007
using namespace std;
struct node{
long long x,y;
bool operator < (const node &z)const {
return x < z.x;
}
}a[1005],a1[1005],d[1005],d1[1005];
int k,len,len1,cnt,cnt1;
char s;
long long ans,n,m;
int main(){
//freopen("automobil.in","r",stdin);
//freopen("automobil.out","w",stdout);
scanf("%lld%lld%d",&n,&m,&k);
ans = (n * m % mod + 1) % mod * n % mod * m % mod * 500000004 % mod;
for (int i = 1;i <= k;i ++){
scanf ("
");
scanf ("%c",&s);
int x,y;
scanf ("%d%d",&x,&y);
if (s == 'R'){
a[++ len].x = x;
a[len].y = y;
}
else {
a1[++len1].x = x;
a1[len1].y = y;
}
}
sort(a + 1,a + 1 + len);
sort(a1 + 1,a1 + 1 + len1);
for (int i = 1;i <= len;i ++){
if (a[i].x != a[i - 1].x || i == 1)
d[++ cnt] = a[i];
else
d[cnt].y = d[cnt].y * a[i].y % mod;
}
for (int i = 1;i <= len1;i ++){
if (a1[i].x != a1[i - 1].x || i == 1)
d1[++ cnt1] = a1[i];
else
d1[cnt1].y = d1[cnt1].y * a1[i].y % mod;
}
for (int i = 1;i <= cnt;i ++)
ans = (ans + ((d[i].x - 1) * m + 1 + d[i].x * m) % mod * m % mod *(d[i].y - 1) % mod * 500000004 % mod) % mod;
for (int i = 1;i <= cnt1;i ++)
ans = (ans +(d1[i].x + (n - 1) * m + d1[i].x) % mod * n % mod * (d1[i].y - 1) % mod * 500000004 % mod) % mod;
for (int i = 1;i <= cnt;i ++){
for (int j = 1;j <= cnt1;j ++){
long long t = (d[i].y * d1[j].y % mod - d[i].y - d1[j].y + mod + 1) % mod;
ans = (ans + ((d[i].x - 1) * m + d1[j].x) % mod * t % mod + mod)% mod;
}
}
printf("%lld",ans);
}