首页 > 代码库 > 数学(容斥计数):LNOI 2016 方

数学(容斥计数):LNOI 2016 方

Description

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

Input

第一行三个整数 N, M, K, 代表棋盘的行数、 列数和不能选取的顶点个数。 保证 N, M >= 1, K <=(N + 1) ×
(M + 1)。约定每行的格点从上到下依次用整数 0 到 N 编号,每列的格点依次用 0到 M 编号。接下来 K 行,每
行两个整数 x,y 代表第 x 行第 y 列的格点被删掉了。保证 0 <=x <=N<=10^6, 0 <=y<=M<=10^6,K<=2*1000且不
会出现重复的格点。

Output

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

Sample Input

2 2 4
1 0
1 2
0 1
2 1

Sample Output

1
  这道题因为k很小可以用容斥, 所有正方形数-Σ每个点(在正方形上)的正方形数+Σ每个无序点对(在正方形上)的正方形数-Σ每个无序三个元组(在正方形上)的正方形数+Σ每个四元组(在正方形上)的正方形数
  然后我打的复杂化了,不过很好懂,几乎是望文生义……
  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 using namespace std;
  6 const int N=2010;
  7 const int Mod=100000007;
  8 typedef long long LL;
  9 LL Abs(LL x){return x<0?-x:x;}
 10 LL n,m,k,tot,x[N],y[N];
 11 LL Ask(LL a,LL b,LL c){
 12     LL ret,L;
 13     if(!a||!b||!c)return 0;
 14     if(a>c-1)a=c-1;
 15     if(b>c-1)b=c-1;
 16     ret=(2*c-a-1)*a/2;
 17     if(c-1>=b+1){
 18         L=min(a,c-b-1);
 19         ret+=b*L;
 20         ret-=(2*c-L-1)*L/2;
 21     }
 22     return (ret%Mod+Mod)%Mod;
 23 }
 24 LL Solve1(){
 25     LL ret=0,L,R,U,D;
 26     for(int i=1;i<=k;i++){
 27         L=min(x[i]-1,y[i]-1);ret+=L;
 28         L=min(n+1-x[i],y[i]-1);ret+=L;
 29         L=min(x[i]-1,m+1-y[i]);ret+=L;
 30         L=min(n+1-x[i],m+1-y[i]);ret+=L;
 31     }
 32     for(int i=1;i<=k;i++){
 33         U=x[i]-1;D=n+1-x[i];
 34         L=y[i]-1;R=m+1-y[i];
 35         ret+=Ask(L,R,U);
 36         ret+=Ask(L,R,D);
 37         ret+=Ask(U,D,L);
 38         ret+=Ask(U,D,R);
 39     }
 40     return ret%Mod;
 41 }
 42 
 43 
 44 LL Solve2(){
 45     LL ret=0,L;
 46     LL px,py,dx,dy;
 47     for(int i=1;i<=k;i++)
 48         for(int j=i+1;j<=k;j++){
 49             dx=x[j]-x[i];
 50             dy=y[j]-y[i];
 51             
 52             px=x[j]+dy;py=y[j]-dx;
 53             if(px>=1&&px<=n+1&&py>=1&&py<=m+1){
 54                 px=px-dx;py=py-dy;
 55                 if(px>=1&&px<=n+1&&py>=1&&py<=m+1)ret+=1;    
 56             }
 57             
 58             px=x[j]-dy;py=y[j]+dx;
 59             if(px>=1&&px<=n+1&&py>=1&&py<=m+1){
 60                 px=px-dx;py=py-dy;
 61                 if(px>=1&&px<=n+1&&py>=1&&py<=m+1)ret+=1;    
 62             }
 63             
 64             if((x[i]+x[j])%2==(y[i]+y[j])%2){
 65                 dx=2*x[i]-(x[i]+x[j]);
 66                 dy=2*y[i]-(y[i]+y[j]);
 67                 px=(x[i]+x[j]+dy)/2;
 68                 py=(y[i]+y[j]-dx)/2;
 69                 if(px>=1&&px<=n+1&&py>=1&&py<=m+1){
 70                     dx=-dx;dy=-dy;
 71                     px=(x[i]+x[j]+dy)/2;
 72                     py=(y[i]+y[j]-dx)/2;
 73                     if(px>=1&&px<=n+1&&py>=1&&py<=m+1)ret+=1;
 74                 }
 75             }
 76         }
 77     return ret%Mod;        
 78 }
 79 
 80 LL hshx[N],hshy[N];
 81 int cntx,cnty,vis[N][N];
 82 
 83 void Prepare(){
 84     for(int i=1;i<=k;i++){
 85         hshx[++cntx]=x[i];
 86         hshy[++cnty]=y[i];
 87     }
 88     sort(hshx+1,hshx+cntx+1);
 89     cntx=unique(hshx+1,hshx+cntx+1)-hshx-1;
 90     sort(hshy+1,hshy+cnty+1);
 91     cnty=unique(hshy+1,hshy+cnty+1)-hshy-1;
 92     for(int i=1;i<=k;i++){
 93         LL x_=lower_bound(hshx+1,hshx+cntx+1,x[i])-hshx;
 94         LL y_=lower_bound(hshy+1,hshy+cnty+1,y[i])-hshy;
 95         vis[x_][y_]=i;
 96     }
 97 }
 98 
 99 int Q(LL x,LL y){
100     LL x_=lower_bound(hshx+1,hshx+cntx+1,x)-hshx;
101     LL y_=lower_bound(hshy+1,hshy+cnty+1,y)-hshy;
102     return (hshx[x_]==x&&hshy[y_]==y)*vis[x_][y_];
103 }
104 
105 LL Solve3(){
106     LL ret=0;
107     LL px1,py1,px2,py2,dx,dy;
108     for(int i=1;i<=k;i++)
109         for(int j=i+1;j<=k;j++){
110             dx=x[j]-x[i];
111             dy=y[j]-y[i];
112             
113             px1=x[j]+dy;py1=y[j]-dx;
114             if(px1>=1&&px1<=n+1&&py1>=1&&py1<=m+1){
115                 px2=px1-dx;py2=py1-dy;
116                 if(px2>=1&&px2<=n+1&&py2>=1&&py2<=m+1){
117                     if(Q(px1,py1)>j)ret+=1;
118                     if(Q(px2,py2)>j)ret+=1;
119                 }
120             }
121             
122             px1=x[j]-dy;py1=y[j]+dx;
123             if(px1>=1&&px1<=n+1&&py1>=1&&py1<=m+1){
124                 px2=px1-dx;py2=py1-dy;
125                 if(px2>=1&&px2<=n+1&&py2>=1&&py2<=m+1){
126                     if(Q(px1,py1)>j)ret+=1;
127                     if(Q(px2,py2)>j)ret+=1;
128                 }
129             }
130             
131             if((x[i]+x[j])%2==(y[i]+y[j])%2){
132                 dx=2*x[i]-(x[i]+x[j]);
133                 dy=2*y[i]-(y[i]+y[j]);
134                 px1=(x[i]+x[j]+dy)/2;
135                 py1=(y[i]+y[j]-dx)/2;
136                 if(px1>=1&&px1<=n+1&&py1>=1&&py1<=m+1){
137                     dx=-dx;dy=-dy;
138                     px2=(x[i]+x[j]+dy)/2;
139                     py2=(y[i]+y[j]-dx)/2;
140                     if(px2>=1&&px2<=n+1&&py2>=1&&py2<=m+1){
141                         if(Q(px1,py1)>j)ret+=1;
142                         if(Q(px2,py2)>j)ret+=1;
143                     }
144                 }
145             }
146         }
147     return ret%Mod;
148 }
149 
150 LL Solve4(){
151     LL ret=0;
152     LL px1,py1,px2,py2,dx,dy;
153     for(int i=1;i<=k;i++)
154         for(int j=i+1;j<=k;j++){
155             dx=x[j]-x[i];
156             dy=y[j]-y[i];
157             
158             px1=x[j]+dy;py1=y[j]-dx;
159             if(px1>=1&&px1<=n+1&&py1>=1&&py1<=m+1){
160                 px2=px1-dx;py2=py1-dy;
161                 if(px2>=1&&px2<=n+1&&py2>=1&&py2<=m+1)
162                     if(Q(px1,py1)>j&&Q(px2,py2)>j)ret+=1;
163             }
164             
165             px1=x[j]-dy;py1=y[j]+dx;
166             if(px1>=1&&px1<=n+1&&py1>=1&&py1<=m+1){
167                 px2=px1-dx;py2=py1-dy;
168                 if(px2>=1&&px2<=n+1&&py2>=1&&py2<=m+1)
169                     if(Q(px1,py1)>j&&Q(px2,py2)>j)ret+=1;
170             }
171             
172             if((x[i]+x[j])%2==(y[i]+y[j])%2){
173                 dx=2*x[i]-(x[i]+x[j]);
174                 dy=2*y[i]-(y[i]+y[j]);
175                 px1=(x[i]+x[j]+dy)/2;
176                 py1=(y[i]+y[j]-dx)/2;
177                 if(px1>=1&&px1<=n+1&&py1>=1&&py1<=m+1){
178                     dx=-dx;dy=-dy;
179                     px2=(x[i]+x[j]+dy)/2;
180                     py2=(y[i]+y[j]-dx)/2;
181                     if(px2>=1&&px2<=n+1&&py2>=1&&py2<=m+1)
182                         if(Q(px1,py1)>j&&Q(px2,py2)>j)ret+=1;
183                 }
184             }
185         }
186     return ret%Mod;
187 }
188 
189 int main(){
190     freopen("square.in","r",stdin);
191     freopen("square.out","w",stdout);
192     scanf("%lld%lld%lld",&n,&m,&k);
193     for(LL L=min(m,n);L>=1;L--){
194         tot+=(n-L+1)*(m-L+1)%Mod*L%Mod;
195         if(tot>=Mod)tot-=Mod;
196     }
197     for(int i=1;i<=k;i++){
198         scanf("%lld%lld",&x[i],&y[i]);
199         x[i]+=1;y[i]+=1;
200     }
201     Prepare();
202     tot-=Solve1();tot%=Mod;
203     tot+=Solve2();tot%=Mod;
204     tot-=Solve3();tot%=Mod;
205     tot+=Solve4();tot%=Mod;    
206     tot=(tot+Mod)%Mod;
207     printf("%lld\n",tot);
208     return 0;
209 }

  运算有些多,常数比较大,不开O2只有50分,优化的话,可以把LL改成int,Mod的时候有些地方可以改成减。

数学(容斥计数):LNOI 2016 方