AT2674 [AGC018E] Sightseeing Plan解题报告

解题报告

AT2674 [AGC018E] Sightseeing Plan解题报告：

更好的阅读体验

题意

• 给定$6$个点$(x_1,y_1)\cdots(x_6,y_6)$。
• 从矩形$(x_1,y_1)-(x_2,y_2)$中某个点出发，在矩形$(x_3,y_3)-(x_4,y_4)$中某个点休息，然后在矩形$(x_5,y_5)-(x_6,y_6)$中某个点结束，每一步行走都只能向上或向右。
• 求一共有多少不同的方案（只要经过的点集不同就算作不同方案），对$10^9+7$取模。
• 数据范围：$1\leqslant x_1\cdots x_6,y_1\cdots y_6\leqslant 10^6$。

分析

神仙题，下面分步进行说明：

点到点

点到点很简单，考虑两个点之间的横纵坐标之差$\Delta x,\Delta y$，发现一共有$\Delta x+\Delta y$步，可以选择$\Delta x$步向右，因此方案数为$\frac{(\Delta x+\Delta y)!}{\Delta x!\Delta y!}$。

inline int G(int a,int b,int c,int d){
    return 1ll*fac[abs(a-c)+abs(b-d)]*nfac[abs(a-c)]%mod*nfac[abs(b-d)]%mod;
}

下面设两个点$(a,b)$与$(c,d)$的距离为$G(a,b,c,d)$。

点到矩形/矩形到点

考虑点$(x,y)$到矩形$(a,b)-(c,d)$的方案数，但是直接算$\sum_{i=a}^b\sum_{j=c}^d G(x,y,i,j)$的复杂度太高了，考虑简单地容斥一下就会得到方案数为$G(x,y,c+1,d+1)-G(x,y,a,d+1)-G(x,y,c+1,b)+G(x,y,a,b)$。

矩形到点的方案数是一样的。

矩形到矩形

考虑先把一个矩形转化为四个点，然后再枚举那四个点把另一个矩形转化为四个点，然后照上面做就好了。（貌似和这道题没有关系）

本题要求

本题要求：从矩形$(x_1,y_1)-(x_2,y_2)$中某个点出发，在矩形$(x_3,y_3)-(x_4,y_4)$中某个点休息，然后在矩形$(x_5,y_5)-(x_6,y_6)$中某个点结束。

考虑枚举进入$(x_3,y_3)-(x_4,y_4)$的点$(i_1,j_1)$（也就是这个矩形左/下边缘上的点）与离开矩形的点$(i_2,j_2)$（也就是这个矩形右/上边缘的点），计算方案就枚举第一个矩形的四个关键点和第三个矩形的四个关键点，然后计算关键点与进入点，进入点与离开点，离开点与另一个关键点的方案，乘上进入点到离开点的路径长度（要在这条路径上选择一个点停留），再乘上容斥系数，这样的复杂度是$O(n^2)$的。

考虑分离进入点和离开点的贡献，不难发现关键点到进入点和进入点到离开点的方案数（或者进入点到离开点和离开点到关键点的方案数）是可以合并计算的，而进入点到离开点的路径长度为$(i_2-i_1+j_2-j_1+1)$，我们很显然可以分离这两个部分的贡献。

然后暴力枚举边缘上的点并进行统计就好了，时间复杂度：$O(n)$。

代码

细节很多，同时提供一个较短的代码：

#include<stdio.h>
const int maxn=2000005,mod=1000000007,maxx=2000000;
int X1,X2,X3,X4,X5,X6,Y1,Y2,Y3,Y4,Y5,Y6,ans;
int fac[maxn],nfac[maxn],inv[maxn],xx[9],yy[9],zz[9];
inline void set(int p,int x,int y,int z){
    xx[p]=x,yy[p]=y,zz[p]=z;
}
inline int abs(int x){
    return x<0? -x:x;
}
inline int G(int a,int b,int c,int d){//点到点
    return 1ll*fac[abs(a-c)+abs(b-d)]*nfac[abs(a-c)]%mod*nfac[abs(b-d)]%mod;
}
int calc(int sx,int sy,int x1,int y1,int x2,int y2,int tx,int ty,int f){//(s1,s2)->(x1,y1,x2,y2)->(tx,ty)
    int res=0;
    for(int i=x1;i<=x2;i++)//枚举矩形下边界/上边界
        res=(res-1ll*G(sx,sy,i,y1-1)*G(i,y1,tx,ty)%mod*(i+y1)%mod+1ll*G(sx,sy,i,y2)*G(i,y2+1,tx,ty)%mod*(i+y2+1)%mod)%mod;//减去的是下边界，加上的是上边界
    for(int i=y1;i<=y2;i++)//枚举矩形左边界/右边界
        res=(res-1ll*G(sx,sy,x1-1,i)*G(x1,i,tx,ty)%mod*(x1+i)%mod+1ll*G(sx,sy,x2,i)*G(x2+1,i,tx,ty)%mod*(x2+i+1)%mod)%mod;//减去的是左边界，加上的是右边界
    return (res*f+mod)%mod;//乘上容斥系数f
}
int main(){
    fac[0]=nfac[0]=1;
    for(int i=1;i<=maxx;i++){
        inv[i]=i==1? 1:(mod-1ll*(mod/i)*inv[mod%i]%mod);
        fac[i]=1ll*fac[i-1]*i%mod,nfac[i]=1ll*nfac[i-1]*inv[i]%mod;
    }
    scanf("%d%d%d%d%d%d%d%d%d%d%d%d",&X1,&X2,&X3,&X4,&X5,&X6,&Y1,&Y2,&Y3,&Y4,&Y5,&Y6);
    set(1,X1-1,Y1-1,1),set(2,X1-1,Y2,-1),set(3,X2,Y1-1,-1),set(4,X2,Y2,1);//设置第一个矩形关键点的位置
    set(5,X5,Y5,1),set(6,X5,Y6+1,-1),set(7,X6+1,Y5,-1),set(8,X6+1,Y6+1,1);//设置第三个矩形关键点的位置
    for(int i=1;i<=4;i++)
        for(int j=5;j<=8;j++)
            ans=(ans+calc(xx[i],yy[i],X3,Y3,X4,Y4,xx[j],yy[j],zz[i]*zz[j]))%mod;
    printf("%d\n",(ans+mod)%mod);
    return 0;
}