[AGC 018 E] Sightseeing plan

STO ZKY ORZ

Description

给定一张网格图和三个矩形，每次只能向上或向右走。你需要从矩形 (A) 中的一个点 (S) 出发，到达矩形 (B) 中的一个点 (P) ，在矩形 (C) 中的一个点 (T) 结束旅程。只要 (S,P,T) 不同或者经过的路径不相同均可看作不同的方案。问总方案数。

Solution

一、点到点

如果我们从 ((0,0)) 出发要走到 ((x,y))，那方案数就是 (C(x+y,x))。

二、点到矩形

(F(x,y)) 表示从 ((0,0)) 到 ((x,y)) 的路径条数。

那么有关系 (F(x,y)=sumlimits_{i=0}^y F(x-1,i))

这个可以理解为枚举在第 (x-1) 行的哪个位置向上走了一步，到达第 (x) 行，然后直接向右走到终点。

所以就能得到从 ((0,0)) 到一个矩形 ((x_1,y_1)-(x_2,y_2)) 的路径条数就是

(F(x_2+1,y_2+1)-F(x_2+1,y_1)-F(x_1,y_2+1)+F(x_1,y_1))

证明就是用上面的式子，保留 (F(x_2+1,j)) 和 (F(x_1,j)) 往下消，然后发现最后只有矩形内部统计了一遍。

这里还是自己画图手推比较好。

所以点到矩形的方案被我们转化成了点到四个关键点的方案。

三、矩形到矩形

设 (G) 为路径条数

那枚举第一个矩形中的所有点，用上边点到矩形的结论，答案就是

(sumlimits_{x_1}sumlimits_{y_1}sumlimits_{x}sumlimits_{y} G((x_1,y_1),(x,y)))

其中 ((x,y)) 是第二个矩形的四个关键点。

然后交换求和号可以惊奇的发现，这个式子又变成了关键点到第一个矩形的方案数

所以可以 (O(16)) 的枚举两个关键点然后计算即可。注意符号！

四、一个矩形经过一个矩形到另一个矩形

推广上面结论

猜测答案就是第一个矩形的四个关键点，到第三个矩形的四个关键点，要求经过第二个矩形 的方案数。

发现如果要经过第二个矩形，那么要么从 ((x,y_3)) （下边界）进入，要么从 ((x_3,y)) （左边界）进入。

所以我们枚举进入点。

进入了这个点就一定进入了这个矩形，它到终点的任意路径就都合法了。

注意枚举进入点，以下边界为例，实际上是枚举 ((x,y_3-1)) 这个点，然后强制要求在这个点向上走一步进入矩形，这样才可以做到不重不漏。

这题好像快做完了...

五、我也不知道叫啥

发现题目的要求是在第二个矩形中选择一个点，而不是找路径条数。一个经过第二个矩形的长度为 (len) 的路径对应着 (len) 种 (P) 点互不相同的路径。

怎么把这个 (len) 算进去呢。

把这个 (len) 拆开，假设进入点为 ((x_1,y_1))，离开点为 ((x_2,y_2))，那么 (len=(x_2-x_1+y_2-y_1+1))

诶这样可以把 (len) 的贡献分开计算

那就在枚举进入点和离开点的时候乘一下就吼了。

Code

#include<bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
#define inv(X) ksm(X,zky-2)
const int N=2e6+5;
const int zky=1e9+7;

int x[8],y[8];
int fac[N],ifac[N];

struct Node{
    int x,y,type;
    Node(){}
    Node(int a,int b,int c=0){x=a,y=b,type=c;}
}node[10];

int ksm(int x,int y,int ans=1){
    while(y){
        if(y&1) ans=1ll*ans*x%zky;
        x=1ll*x*x%zky;y>>=1;
    } return ans;
}

int getint(){
    int X=0,w=0;char ch=getchar();
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=X*10+ch-48,ch=getchar();
    if(w) return -X;return X;
}

int C(int n,int m){
    return 1ll*fac[n]*ifac[m]%zky*ifac[n-m]%zky;
}

int G(int x1,int x2,int y1,int y2){
    return C(abs(x2-x1)+abs(y2-y1),abs(x2-x1));
}

int G(Node a,Node b){
    return C(abs(a.x-b.x)+abs(a.y-b.y),abs(a.x-b.x));
}

int cal(Node a,Node b){
    int ans=0;
    for(int i=x[3];i<=x[4];i++){
        ans=(1ll*ans-1ll*G(a,Node(i,y[3]-1))*G(Node(i,y[3]),b)%zky*(i+y[3])%zky+zky)%zky;
        ans=(1ll*ans+1ll*G(a,Node(i,y[4]))*G(Node(i,y[4]+1),b)%zky*(i+y[4]+1)%zky)%zky;
    }
    for(int i=y[3];i<=y[4];i++){
        ans=(1ll*ans-1ll*G(a,Node(x[3]-1,i))*G(Node(x[3],i),b)%zky*(i+x[3])%zky+zky)%zky;
        ans=(1ll*ans+1ll*G(a,Node(x[4],i))*G(Node(x[4]+1,i),b)%zky*(i+x[4]+1)%zky)%zky;
    } return (1ll*ans*a.type*b.type+zky)%zky;
}

signed main(){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=N-5;i++) fac[i]=1ll*fac[i-1]*i%zky;
    ifac[N-5]=inv(fac[N-5]);
    for(int i=N-6;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%zky;
    for(int i=1;i<=6;i++) x[i]=getint();
    for(int i=1;i<=6;i++) y[i]=getint();
    node[1]=Node(x[1]-1,y[1]-1,1);node[2]=Node(x[2],y[1]-1,-1);
    node[3]=Node(x[1]-1,y[2],-1); node[4]=Node(x[2],y[2],1);
    node[5]=Node(x[5],y[5],1);    node[6]=Node(x[6]+1,y[5],-1);
    node[7]=Node(x[5],y[6]+1,-1); node[8]=Node(x[6]+1,y[6]+1,1);
    ll ans=0;
    for(int i=1;i<=4;i++)
        for(int j=5;j<=8;j++)
            ans=((ans+cal(node[i],node[j]))%zky+zky)%zky;
    printf("%lldn",ans);
    return 0;
}