【AtCoder Grand Contest 018 E】Sightseeing Plan
mrsrz
2月 18, 2020
组合数学。
题目大意：
给定三个矩阵，保证上一个的任意一部分都在下一个矩阵的左上角。
要求找到 $S$ 到 $T$，中间经过 $P$ 的路径，满足 $S,P,T$ 分别在第一、二、三个矩阵中。
只能向下或向右走。
问有多少不同路径。
一条路径不同，当且仅当 $S,P,T$ 有一个不同，或走法不同。
题解：
有式子：
可以画图理解。
相当于我们可以将点到矩形的路径计数，转化为点到线的路径计数，再转化为点到点的路径计数。运用差分思想即可。
那么矩形到矩形的路径计数最终也可以转化为点到点的，只需要枚举 $16$ 种对应情况即可。
考虑第二个矩形的限定。我们要求路径必须经过第二个矩形。
我们枚举它进入第二个矩形的位置（$O(n)$ 个边界），然后每种从 $S$ 出发进入边界，到 $T$ 的路径都经过了第二个矩形。
但这里一种方案的贡献为 $1$，实际上一种方案的贡献为路径在第二个矩形内的长度。
我们考虑入点和出点的坐标分别为 $(x_1,x_2)$ 和 $(y_1,y_2)$ 时，其贡献为 $(x_2-x_1+y_2-y_1+1)$。
我们在入和出时分别计算加和减的贡献即可。
Code：
#include<iostream>
typedef long long LoveLive;
const int md=1e9+7,N=3e6+7;
int X1,X2,X3,X4,X5,X6,Y1,Y2,Y3,Y4,Y5,Y6,ans;
int fac[N],iv[N];
inline int pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LoveLive)a*a%md)if(b&1)ret=(LoveLive)ret*a%md;
return ret;
}
struct point{
int x,y,fh;
}A[4],B[4];
inline int C(int n,int m){return(LoveLive)fac[n]*iv[m]%md*iv[n-m]%md;}
inline int calc(int x,int y){return C(x+y,x);}
int main(){
std::cin>>X1>>X2>>X3>>X4>>X5>>X6>>Y1>>Y2>>Y3>>Y4>>Y5>>Y6;
A[0]=(point){X1-1,Y1-1,1},A[1]=(point){X1-1,Y2,-1},A[2]=(point){X2,Y1-1,-1},A[3]=(point){X2,Y2,1};
B[0]=(point){X6+1,Y6+1,1},B[1]=(point){X5,Y6+1,-1},B[2]=(point){X6+1,Y5,-1},B[3]=(point){X5,Y5,1};
for(int i=*fac=1;i<=3000000;++i)fac[i]=(LoveLive)fac[i-1]*i%md;
iv[3000000]=pow(fac[3000000],md-2);
for(int i=2999999;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
for(int i=X3;i<=X4;++i)
for(int s=0;s<4;++s)
for(int t=0;t<4;++t){
ans=(ans+(LoveLive)calc(i-A[s].x,Y3-A[s].y-1)*calc(B[t].x-i,B[t].y-Y3)%md*(2LL*md-i-Y3)%md*(md+A[s].fh*B[t].fh))%md;
ans=(ans+(LoveLive)calc(i-A[s].x,Y4-A[s].y)*calc(B[t].x-i,B[t].y-Y4-1)%md*(i+Y4+1)%md*(md+A[s].fh*B[t].fh))%md;
}
for(int i=Y3;i<=Y4;++i)
for(int s=0;s<4;++s)
for(int t=0;t<4;++t){
ans=(ans+(LoveLive)calc(X3-A[s].x-1,i-A[s].y)*calc(B[t].x-X3,B[t].y-i)%md*(2LL*md-i-X3)%md*(md+A[s].fh*B[t].fh))%md;
ans=(ans+(LoveLive)calc(X4-A[s].x,i-A[s].y)*calc(B[t].x-X4-1,B[t].y-i)%md*(i+X4+1)%md*(md+A[s].fh*B[t].fh))%md;
}
std::cout<<ans<<'\n';
return 0;
}