[BZOJ4558]:[JLoi2016]方（容斥+模拟）

题目传送门

题目描述

上帝说，不要圆，要方，于是便有了这道题。
由于我们应该方，而且最好能够尽量方，所以上帝派我们来找正方形上帝把我们派到了一个有N行M列的方格图上，图上一共有$(N+1)\times (M+1)$个格点，我们需要做的就是找出这些格点形成了多少个正方形（换句话说，正方形的四个顶点都是格点）。
但是这个问题对于我们来说太难了，因为点数太多了，所以上帝删掉了这$(N+1)\times (M+1)$中的$K$个点。
既然点变少了，问题也就变简单了，那么这个时候这些格点组成了多少个正方形呢？

输入格式

第一行三个整数N,M,K，代表棋盘的行数、列数和不能选取的顶点个数。
约定每行的格点从上到下依次用整数0到N编号，每列的格点依次用0到M编号。
接下来K行，每行两个整数x,y代表第x行第y列的格点被删掉了。

输出格式

仅一行一个正整数，代表正方形个数对$100000007({10}^8+7)$取模之后的值。

样例

样例输入：

2 2 4
1 0
1 2
0 1
2 1

样例输出：

数据范围与提示

$0\leqslant x\leqslant N\leqslant {10}^6$

$K\leqslant 2\times 1000$且不会出现重复的节点

题解

看到题面以为很简单，其实呢？

要知道，不仅正方形可以是正着放着的也可以是斜着放着的。

我的天！！！

显然我们不好直接求出答案，所以我们来考虑容斥。

虽说一共有2000个格点被删掉了，但是想想，一个正方形只有四个顶点，那么问题就简单多了。

答案就变成了：随便选的方案数-所有选一个被删掉的点为顶点的正方形个数+所有选二个被删掉的点为顶点的正方形个数-所有选三个被删掉的点为顶点的正方形个数+所有选四个被删掉的点为顶点的正方形个数。

在分类讨论之前，我们先来明确这么一个知识：

　　一个正着放置的边长为$x$正方形内有$x-1$个斜着放置的内接正方形，那么一个$x\times x$的格点中一共就有$x$个正方形。

那么我们现在来分类讨论每一种情况：

　　1.随便选：

　　枚举正方形的边长，方案数为：$\sum \limits_{i=1}^{\min(n,m)}i\times (n-i+1)\times (m-i+1)$。

　　2.选一个：

　　个人感觉这是这道题中最难处理的一种情况，因为这种情况还分为四种子情况：

　　为了方便，先来定义一些值：一个被删除的点有上下左右四个方向，以这四个方向为正方向都有$l,r,h$分别为向左延伸的方向，向右延伸的方向，向上延伸的方向。

　　　　$\alpha.1\leqslant h\leqslant \min (l,r)$：

　　　　　　方案数为$\frac{(h+3)\times h}{2}$。

　　　　$\beta.\min(l,r)+1\leqslant h\leqslant \max(l,r)$：

　　　　　　方案数为$\frac{(\min(l,r)+3)\times \min(l,r)}{2}+(h-\min(l,r))\times (\min(l,r)+1)$。

　　　　$\chi.\max(l,r)+1\leqslant \min(l,r)+\max(l,r)$：

　　　　　　方案数为

　　　　　　$\frac{(\min(l,r)+3)\times \min(l,r)}{2}+(\max(l,r)-\min(l,r))\times (min(l,r)+1)+\frac{(2\times \min(l,r)+1-h+\max(l,r))\times (h-\max(l,r))}{2}$

　　　　$\delta.\min(l,r)+\max(l,r)\leqslant h\leqslant +\infty$：

　　　　　　方案数为

　　　　　　$\frac{(\min(l,r)+3)\times \min(l,r)}{2}+(\max(l,r)-\min(l,r))\times (\min(l,r)+1)+\frac{(\min(l,r)+1)\times \min(l,r)}{2}$。

　　推导过程不再赘述，有兴趣可以自己画画图。

　　3.选二个：

　　依次枚举两个点$(a,b)(c,d)$，看能不能当作正方形的两个顶点，分二种情况：

　　　　$\alpha.$两点作为正方形一条边，正方形可以在上面，也可以在下面，另两个点分别为$(a+d-b,a+b-c)(c+d-b,a+d-c)$和$(a+b-d,b+c-a)(b+c-d,c+d-a)$。

　　　　$\beta.$两点作为正方形的对角线，则另外两个定点是$(\frac{a+b+c-d}{2},\frac{b+c+d-a}{2})(\frac{a+c+d-b}{2},\frac{a+b+d-c}{2})$。

　　直接判断这些点在不在范围内就好了。

　　4.选三个：

　　在枚举选二个的同时可以顺便求得，但是需要注意的是因为选二个是每次固定两个点，所以这时每个选三个的方案会被重复统计三次，需要除掉。

　　5.选四个：

　　同理，但是会被重复统计六次。

计算答案时注意奇加偶减就好了，代码实现细节很多，需要注意。

代码时刻

#include<bits/stdc++.h>

using namespace std;

#define mod 100000007

struct rec{int x,y;}e[2010],res1,res2;

int n,m,k;

long long ans;

int sum2,sum3,sum4;//统计选二、三、四个的方案数

bool cmp(rec a,rec b){return a.x==b.x?a.y<b.y:a.x<b.x;}

int judge(int l,int r,int h)//计算选一个的方案数

{

    int fh;

    long long num=0;

    int minn=min(l,r);

    int maxn=max(l,r);

    if(h>minn)fh=minn;

    else fh=h;

    num+=(1LL*(fh+3)*fh/2)%mod;

    if(h<=minn)return num%mod;

    if(h>maxn)fh=maxn;

    else fh=h;

    num+=(1LL*(fh-minn)*(minn+1))%mod;

    if(h<=maxn)return num%mod;

    if(h>minn+maxn)fh=minn+maxn;

    else fh=h;

    num+=(1LL*(minn*2+1-fh+maxn)*(fh-maxn)/2)%mod;

    return num%mod;

}

int calc1(int x,int y,int l,int r){return (judge(x,y,l)+judge(x,y,r)+judge(l,r,x)+judge(l,r,y)-min(x,l)-min(x,r)-min(y,l)-min(y,r)+mod)%mod;}

void calc2()

{

	sum2++;

	int flag1=lower_bound(e+1,e+k+1,res1,cmp)-e;

	int flag2=lower_bound(e+1,e+k+1,res2,cmp)-e;

	if(1<=flag1&&flag1<=k&&e[flag1].x==res1.x&&e[flag1].y==res1.y)sum3++;

	if(1<=flag2&&flag2<=k&&e[flag2].x==res2.x&&e[flag2].y==res2.y)sum3++;

	if(1<=flag1&&flag1<=k&&e[flag1].x==res1.x&&e[flag1].y==res1.y&&1<=flag2&&flag2<=k&&e[flag2].x==res2.x&&e[flag2].y==res2.y)sum4++;

}

bool jd(double x){return fabs(x-(int)(x+1e-8))<=1e-8;}

void get0()//随便选

{

	for(int i=1;i<=min(n,m);i++)

		ans=(ans+1LL*i*(n-i+1)%mod*(m-i+1))%mod;

}

void get2()//选二个+选三个+选四个

{

    for(int i=1;i<k;i++)

        for(int j=i+1;j<=k;j++)

        {

            int a=e[i].x,b=e[i].y,c=e[j].x,d=e[j].y;

            res1=(rec){a+d-b,b+a-c};

            res2=(rec){c+d-b,d+a-c};

            if(0<=a+d-b&&a+d-b<=n&&0<=b+a-c&&b+a-c<=m&&0<=c+d-b&&c+d-b<=n&&0<=d+a-c&&d+a-c<=m)calc2();

            res1=(rec){a+b-d,b+c-a};

            res2=(rec){c+b-d,c+d-a};

            if(0<=a+b-d&&a+b-d<=n&&0<=b+c-a&&b+c-a<=m&&0<=c+b-d&&c+b-d<=n&&0<=d+c-a&&d+c-a<=m)calc2();

            if(jd(1.0*(a+b+c-d)/2)&&jd(1.0*(a+c+d-b)/2))

            {

                res1=(rec){(a+b+c-d)/2,(b+c+d-a)/2};

                res2=(rec){(a+c+d-b)/2,(a+b+d-c)/2};

                if(0<=(a+b+c-d)/2&&(a+b+c-d)/2<=n&&0<=(b+c+d-a)/2&&(b+c+d-a)/2<=m&&0<=(a+c+d-b)/2&&(a+c+d-b)/2<=n&&0<=(a+b+d-c)/2&&(a+b+d-c)/2<=m)

                calc2();

            }

        }

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1;i<=k;i++)

	{

		scanf("%d%d",&e[i].x,&e[i].y);

		ans=(ans-calc1(e[i].x,n-e[i].x,e[i].y,m-e[i].y)+mod)%mod;

	}

	sort(e+1,e+k+1,cmp);

	get0();

	get2();

	ans=(ans+sum2)%mod;

	ans=(ans-sum3/3+mod)%mod;//统计答案时记着除掉

	ans=(ans+sum4/6)%mod;

	printf("%lld",(ans+mod)%mod);

	return 0;

}

rp++

巴特西