Atcoder 的题目就是好 思维难度高到我都不会
题目描述
在网格图上，给 $X_1 \leq X_2 < X_3 \leq X_4 < X_5 \leq X_6$和$Y_1 \leq Y_2 < Y_3 \leq Y_4 < Y_5 \leq Y_6$，需要选择 $(p,q) \in [X_1,X_2]\times[Y_1,Y_2],(s,t) \in [X_3,X_4]\times[Y_3,Y_4],(u,v)\in [X_5,X_6]\times[Y_5,Y_6]$，以及一条从 $(p,q)$ 经过 $(s,t)$ 到达 $(u,v)$ 的只能向上或向右的路径。两个方案不同当且仅当 $(p,q),(s,t),(u,v)$ 选择不同或者路径不同。求方案数
$X,Y \leq 10^6$
题解
我们先分成几个小问题解决：
点到点的方案数
$(0,0) \to (x,y)$:方案数显然是$\binom {x+y}{x}$ 。
点到面的方案数
先看最简单的情形：$(0,0) \to [0,X]\times [0,Y]$
我们先注意到对于组合数的上下指标求和 有这两种形式：
$$ \sum_{i=0}^n \binom{x+i}{x} = \binom{x+n+1}{x+1} $$
$$ \sum_{i=1}^n \binom{x+i}{i} = \binom{x+n+1}{n+1}-1 $$
大概都是用组合数的简单递推形式搞。
$$ \begin{align*}&\sum_{i=0}^X\sum_{j=0}^Y \binom{i+j}{i}\\&= \sum_{i=0}^X \binom{i+Y+1}{i+1}\\&= \binom{X+Y+2}{X+1}-1\end{align*} $$
如果是 $(0,0) \to [X_1,X_2]\times[Y_1,Y_2]$呢？只需要用二维前缀和的思想就好了。
面到面
考虑点到面的情况实际上可以拆成点到四个点的方案数（带权）。所以面到面可以转化为 $16$ 对点到点。
这个题
暴力的想法是把第一个和第三个面化为 $4$ 个点 那么枚举 $16$ 种可能 再枚举中间的点 就可以计算。
考虑我们先随便确定一条经过中间面的路径 发现这个路径对答案的贡献就是和中间面交的长度。
考虑进入的点是 $(x,y)$ 出去的点是 $(a,b)$ 那么贡献 $a-x+b-y+1$ 所以就可以变成枚举每一个入点 考虑这个入点方案会被计算多少次（强制路径经过这个点的方案） 然后有个系数 $-x-y$ 出点类似 系数是 $a+b+1$
不理解可以看看代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 5e6 + 5;
const int ha = 1e9 + 7;
inline int qpow(int a,int n=ha-2){
int res = 1;
while(n){
if(n & 1) res = 1ll*res*a%ha;
a = 1ll*a*a%ha;
n >>= 1;
}
return res;
}
int fac[MAXN],inv[MAXN];
inline void prework(){
fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
inv[MAXN-1] = qpow(fac[MAXN-1]);
ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}
inline int C(int n,int m){
if(n < m) return 0;
if(!m) return 1;
return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}
inline int calc1(int x,int y){// (0,0) 到 (x,y)
if(x < 0 || y < 0) return 0;
return C(x+y,x);
}
inline int calc2(int x,int y){ // (0,0) 到 ([0,x],[0,y])
return (calc1(x+1,y+1)+ha-1)%ha;
}
inline int calc3(int x1,int x2,int y1,int y2){// (0,0) 到 ([x1,x2],[y1,y2])
int res = calc1(x2+1,y2+1);
(res += ha-calc1(x2+1,y1)) %= ha;
(res += ha-calc1(x1,y2+1)) %= ha;
(res += calc1(x1,y1)) %= ha;
return res;
}
inline int calc4(int x,int y,int x1,int x2,int y1,int y2){// (x,y) 到 ([x1,x2],[y1,y2])
return std::min(x1,x2) >= x && std::min(y1,y2) >= y ? calc3(x1-x,x2-x,y1-y,y2-y) : calc3(x-x2,x-x1,y-y2,y-y1);
// 实际应用是要判包含的 但是这个题不会
}
int x[233],y[233];
int main(){
prework();
FOR(i,1,6) scanf("%d",x+i);
FOR(i,1,6) scanf("%d",y+i);
int ans = 0;
FOR(i,x[3],x[4]){
(ans += 1ll*(ha-(i+y[3])%ha)*calc4(i,y[3]-1,x[1],x[2],y[1],y[2])%ha*calc4(i,y[3],x[5],x[6],y[5],y[6])%ha) %= ha;
(ans += 1ll*(i+y[4]+1)%ha*calc4(i,y[4],x[1],x[2],y[1],y[2])%ha*calc4(i,y[4]+1,x[5],x[6],y[5],y[6])%ha) %= ha;
}
FOR(i,y[3],y[4]){
(ans += 1ll*(ha-(i+x[3])%ha)*calc4(x[3]-1,i,x[1],x[2],y[1],y[2])%ha*calc4(x[3],i,x[5],x[6],y[5],y[6])%ha) %= ha;
(ans += 1ll*(x[4]+i+1)%ha*calc4(x[4],i,x[1],x[2],y[1],y[2])%ha*calc4(x[4]+1,i,x[5],x[6],y[5],y[6])%ha) %= ha;
}
printf("%d\n",ans);
return 0;
}
