NC15845. 子矩阵计数
描述
输入描述
输入包含多组测试数据
第一行一个正整数T,代表有T组测试数据
每组数据的第一行两个正整数n, m分别代表矩阵的行数和列数第二行一个正整数p, 代表数字为1的方格个数
接下来p行, 每行两个正整数x, y分别表示第x行y列的方格数字为1
注意: 这里的行号与列号均从1开始
输出描述
对于每组数据, 输出一个非负整数, 表示这个矩阵一共有多少个子矩阵含有为1的方格对(109+7)取模(余)后的结果
示例1
输入:
2 3 3 3 1 1 1 2 2 2 1 1 2 2
输出:
9 7
C++11(clang++ 3.9) 解法, 执行用时: 103ms, 内存消耗: 496K, 提交时间: 2020-03-14 12:23:28
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int MAXP=5e3;
struct Point
{
int x,y;
bool operator < (const Point &b) const
{
return x==b.x?y<b.y:x<b.x;
}
}P[MAXP];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll n,m;
int p;
scanf("%lld%lld",&n,&m);
scanf("%d",&p);
P[0]=Point{0,0};
for(int i=1;i<=p;i++)
{
scanf("%d%d",&P[i].x,&P[i].y);
}
sort(P,P+p+1);
ll ans=0;
for(int i=1;i<=p;i++)
{
ll high=m+1,low=0;
for(int j=i-1;j>-1;--j)
{
if(high==P[i].y||low==P[i].y)
{
break;
}
ll tmp=(high-P[i].y)*(P[i].y-low)%MOD;
tmp*=(n-P[i].x+1)*(P[j+1].x-P[j].x)%MOD;
ans=(ans+tmp)%MOD;
if(P[j].y>=P[i].y&&P[j].y<high) high=P[j].y;
if(P[j].y<=P[i].y&&P[j].y>low) low=P[j].y;
}
}
printf("%lld\n",ans);
}
return 0;
}