bzoj 4558 方

Posted on | Views:

容斥原理.

  • 记 $s_i$ 表示顶点恰好有 $i$ 个点是不合法点的正方形数,答案显然是 $s_0-s_1+s_2-s_3+s_4$ .
  • $s_0$ 可以直接算, $s_1$ 可以枚举每个不合法点来算.
  • 算 $s_2,s_3,s_4$ 都只需要枚举每对不合法点,并判断其他两个顶点是否合法,将贡献加入对应的 $s$ .

注意考虑斜着放的正方形.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e8+7;
const int inv2=(P+1)>>1;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=2e3+10;
typedef pair<int,int> pii;
#define mp make_pair
set<pii> S;
int n,m,k,s[5];
int Calc(int l,int r,int h)
{
	int z=min(l+r,h);
	if(!z)
		return 0;
	int res=mul(mul(z,z+3),inv2);
	if(z>l)
		res=add(res,P-mul(inv2,mul(z-l,z-l+1)));
	if(z>r)
		res=add(res,P-mul(inv2,mul(z-r,z-r+1)));
	return res;
}
int calc1(int x,int y)
{
	int t=x,b=n-x,l=y,r=m-y;
	int res=0;
	res=add(res,Calc(t,b,l));
	res=add(res,Calc(t,b,r));
	res=add(res,Calc(l,r,t));
	res=add(res,Calc(l,r,b));
	res=add(res,P-min(l,t));
	res=add(res,P-min(r,t));
	res=add(res,P-min(l,b));
	res=add(res,P-min(r,b));
	return res;
}
bool check(int x,int y)
{
	return x>=0 && x<=n && y>=0 && y<=m;
}
void count(int ax,int ay,int bx,int by)
{
	if(check(ax,ay) && check(bx,by))
	{
		int t=S.count(mp(ax,ay))+S.count(mp(bx,by));
		++s[2];
		if(t>0)
			s[3]=add(s[3],1);
		if(t>1)
			s[3]=add(s[3],1),s[4]=add(s[4],1);
	}
}
int x[MAXN],y[MAXN];
void solve()
{
	for(int i=1;i<=n && i<=m;++i)
		s[0]=add(s[0],mul(i,mul(n-i+1,m-i+1)));
	for(int i=1;i<=k;++i)
		s[1]=add(s[1],calc1(x[i],y[i]));
	for(int i=1;i<k;++i)
		for(int j=i+1;j<=k;++j)
		{
			int dx=x[i]-x[j];
			int dy=y[i]-y[j];
			count(x[i]+dy,y[i]-dx,x[j]+dy,y[j]-dx);
			count(x[i]-dy,y[i]+dx,x[j]-dy,y[j]+dx);
			if(abs(dx)+abs(dy) & 1)
				continue;
			int X=(dx-dy)>>1,Y=(dx+dy)>>1;
			count(x[i]-X,y[i]-Y,x[j]+X,y[j]+Y);
		}
	s[3]/=3;
	s[4]/=6;
}
int main()
{
	n=read(),m=read();
	k=read();
	for(int i=1;i<=k;++i)
	{
		x[i]=read();
		y[i]=read();
		S.insert(mp(x[i],y[i]));
	}
	solve();
	int ans=0;
	for(int i=0;i<=4;++i)
		if(i&1)
			ans=add(ans,P-s[i]);
		else
			ans=add(ans,s[i]);
	cout<<ans<<endl;
	return 0;
}